ทีมวิจัยจากมหาวิทยาลัย Waterloo ประกาศความสำเร็จในการแก้ปัญหา traveling salesman (TSP) ที่ต้องคำนวณหาระยะทางระหว่างบาร์ต่างๆ ในเกาหลีใต้แล้ววางแผนการเดินทางให้สั้นที่สุดเท่าที่เป็นไปได้ โดยจำนวนบาร์ในเกาหลีใต้มีมากถึง 81,998 แห่ง นับเป็นปัญหา TSP ใหญ่ที่สุดที่เคยแก้จนถึงระดับที่ออปติไมซ์ที่สุด
ผลการคำนวณพบว่าหากเดินไม่หยุด จะใช้เวลา 15,386,177 วินาที หรือ 178 วัน 1 ชั่วโมง 56 นาที 17 วินาที แต่หากทำจริงก็น่าจะใช้เวลาพักและแวะร้านต่างๆ ด้วยทำให้ใช้เวลาหลายปี โดยรวมทีมงานใช้ซีพียู Intel Xeon Gold 6238 สองซ็อกเก็ต รวม 48 คอร์ คำนวณ โดยหาเส้นทางเริ่มต้นมาก่อน แล้วใช้กระบวนการ branch-and-bound search แตกเส้นทางออกเป็นส่วนๆ แล้วหาเส้นทางที่ออปติไมซ์ขึ้นเรื่อยๆ
ปัญหา TSP เป็นปัญหา NP ที่ความยากของปัญหาเพิ่มขึ้นอย่างรวดเร็ว หากคำนวณแบบตรงไปตรงมา ปัญหา TSP ขนาด 22 จุดอาจจะใช้เวลานับพันปี แต่ในความเป็นจริงมีอัลกอริทึมที่ออปติไมซ์ได้ดีขึ้นมาก ทำให้เราสามารถแก้ปัญหา TSP ที่ใหญ่ขึ้นในเวลาที่พอใช้งานได้ โดย TSP ที่ใหญ่ที่สุดก่อนหน้านี้คือการเดินชมอนุสาวรีย์ในเนเธอร์แลนด์ 57,912 จุด
ที่มา - University of Waterloo
Topics:
Mathematics
Algorithm
Continue reading...
ผลการคำนวณพบว่าหากเดินไม่หยุด จะใช้เวลา 15,386,177 วินาที หรือ 178 วัน 1 ชั่วโมง 56 นาที 17 วินาที แต่หากทำจริงก็น่าจะใช้เวลาพักและแวะร้านต่างๆ ด้วยทำให้ใช้เวลาหลายปี โดยรวมทีมงานใช้ซีพียู Intel Xeon Gold 6238 สองซ็อกเก็ต รวม 48 คอร์ คำนวณ โดยหาเส้นทางเริ่มต้นมาก่อน แล้วใช้กระบวนการ branch-and-bound search แตกเส้นทางออกเป็นส่วนๆ แล้วหาเส้นทางที่ออปติไมซ์ขึ้นเรื่อยๆ
ปัญหา TSP เป็นปัญหา NP ที่ความยากของปัญหาเพิ่มขึ้นอย่างรวดเร็ว หากคำนวณแบบตรงไปตรงมา ปัญหา TSP ขนาด 22 จุดอาจจะใช้เวลานับพันปี แต่ในความเป็นจริงมีอัลกอริทึมที่ออปติไมซ์ได้ดีขึ้นมาก ทำให้เราสามารถแก้ปัญหา TSP ที่ใหญ่ขึ้นในเวลาที่พอใช้งานได้ โดย TSP ที่ใหญ่ที่สุดก่อนหน้านี้คือการเดินชมอนุสาวรีย์ในเนเธอร์แลนด์ 57,912 จุด
ที่มา - University of Waterloo
Topics:
Mathematics
Algorithm
Continue reading...