news ทีมวิจัย Waterloo แก้ปัญหา Treveling Salesman ใหญ่ที่สุดในโลกสำเร็จ วางแผนเข้าบาร์ในเกาหลีใต้แบบเดินทางสั้นที่สุด

[News News is verified member.]

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