ทีมวิจัยจากมหาวิทยาลัย 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