เส้นทางเดินที่สั้นที่สุดในการตระเวนบาร์ทั้ง 81,998 แห่งของเกาหลีคือ 178 วัน

xguru · 2025-04-23T09:31:02+09:00

ศาสตราจารย์ William Cook แห่งมหาวิทยาลัยวอเตอร์ลูคำนวณกรณีแรกของโลกที่ใช้ปัญหาพนักงานขายเดินทาง (TSP) กับเส้นทางที่สั้นที่สุดในการเยือน บาร์ 81,998 แห่ง ของเกาหลี ใช้ Open Source Routing Machine (OSRM) คำนวณเวลาเดินประมาณ 3.3 พันล้านคู่ และพิสูจน์ได้ทางคณิตศาสตร์ว่าเป็นคำตอบที่เหมาะที่สุด ผลการคำนวณระบุว่า หากเดินต่อเนื่องไม่หยุดจะใช้เวลา 15,386,177 วินาที หรือ 178 วัน 1 ชั่วโมง 56 นาที 17 วินาที การหาคำตอบเหมาะที่สุดของ TSP ใช้เครื่องมือ LKH และ Concorde พร้อมประยุกต์ใช้ วิธี cutting plane นี่คือ กรณีแก้ปัญหา TSP บนเครือข่ายถนนที่มีขนาดใหญ่ที่สุดในโลก แซงหน้าสถิติเดิมของ เนเธอร์แลนด์ 57,912 จุด ปัญหาพนักงานขายเดินทาง (Traveling Salesman Problem) สำหรับการเดินครบทุกบาร์ในเกาหลี คำนวณเส้นทางที่สั้นที่สุดในการไปเยือน บาร์ 81,998 แห่ง ในเกาหลีให้ครบแล้วกลับมายังจุดเริ่มต้น เป็นการ แก้ปัญหา TSP แบบเหมาะที่สุด ที่มีจำนวนสถานที่มากขนาดนี้ได้เป็น ครั้งแรกของโลก คำนวณเวลาเดินสำหรับจุดจับคู่ทั้งหมด 3,361,795,003 คู่ ระหว่างบาร์ด้วย OSRM - Open Source Routing Machine พิสูจน์ทางคณิตศาสตร์ได้ว่า ไม่มีเส้นทางที่สั้นกว่านี้ ปัญหานี้เป็น TSP ขนาดใหญ่ที่สุดเท่าที่เคยมีมา เมื่อวัดจากจำนวนจุดที่ต้องแวะ เวลาที่ใช้สำหรับเส้นทางสั้นที่สุด หากเดินตามเส้นทางที่เหมาะที่สุดที่คำนวณได้โดยไม่หยุดพัก จะใช้เวลารวม 15,386,177 วินาที คิดเป็น 178 วัน 1 ชั่วโมง 56 นาที 17 วินาที ในความเป็นจริง ระหว่างเดินอาจต้องพักหรือดื่ม จึงแทบเป็นไปไม่ได้ที่จะจบได้ตรงเป๊ะ เป็นเส้นทาง เหมาะที่สุด ที่แม้อิงตามเวลาเดินจาก OSRM ก็ไม่อาจลดลงได้แม้แต่ 1 วินาที บริบททางประวัติศาสตร์ของ TSP และการทำลายสถิติ สถิติเดิมคือ เส้นทางจักรยาน 57,912 จุดในเนเธอร์แลนด์ เส้นทาง korea81998 ครั้งนี้เป็น ตัวอย่างการแก้ปัญหา TSP ที่มีขนาดใหญ่กว่านั้น การคำนวณดำเนินการที่ มหาวิทยาลัยรอสกิลด์ และ มหาวิทยาลัยวอเตอร์ลู ตั้งแต่เดือนธันวาคม 2024 ถึงมีนาคม 2025 รายละเอียดการคำนวณสามารถดูได้จาก หน้าคำนวณ แยกต่างหาก วิธีการแสดงภาพเส้นทาง สามารถดูเส้นทางผ่าน แผนที่อินเทอร์แอ็กทีฟ และสำรวจแบบแยกเป็น 7 ภูมิภาคได้ มีโหมดการแสดงผลหลายแบบ เช่น แผนที่ระยะสีและภาพขาวดำ มีการจัดเตรียมภาพความละเอียดสูงของบางส่วนของเส้นทางไว้ต่างหาก มุมมองขยายรายเมืองมีให้ใน หน้าของแต่ละเมือง กลยุทธ์การแก้ TSP และความเข้าใจผิด สื่อบางแห่งรายงานว่าแค่ “22 เมืองก็ต้องใช้เวลา 1,000 ปี” แต่สิ่งนั้นหมายถึง กรณีลองทุกเส้นทางแบบสุ่มทั้งหมด ในความเป็นจริง จุดจำนวนมากก็สามารถแก้ได้ด้วยเทคนิคการหาค่าเหมาะที่สุดขั้นสูง สำหรับ korea81998 จำนวนเส้นทางที่เป็นไปได้มีขนาดประมาณ เลข 2 ที่ตามด้วยเลข 0 จำนวน 367,308 ตัว การแก้ปัญหาใช้ทั้ง LKH(Lin-Kernighan Heuristic) อัลกอริทึม และ Concorde TSP Solver - วิธี cutting plane ร่วมกัน สรุปแนวคิดของวิธี cutting plane อิงอยู่บนการโปรแกรมเชิงเส้น แทนที่จะระบุว่าใช้ถนนเส้นใดหรือไม่ใช้ จะใช้ ค่าระดับการเชื่อมต่อระหว่าง 0 ถึง 1 แทน เพิ่มเงื่อนไขข้อจำกัดทีละขั้นเพื่อค้นหา เส้นทางที่สั้นที่สุด คำอธิบายเพิ่มเติมดูได้จาก Scientific American และ การบรรยายบน YouTube ปัญหา P กับ NP ปัญหา TSP เป็น ปัญหา NP-สมบูรณ์ และเป็นตัวอย่างสำคัญของประเด็น P กับ NP การอภิปรายที่น่าสนใจเกี่ยวกับเรื่องนี้มีแนะนำไว้ในงานเขียนของ ศาสตราจารย์ Lance Fortnow นี่คือหนึ่งใน ปัญหาที่ยังไม่ถูกแก้ที่มีชื่อเสียงที่สุดของวิทยาการคอมพิวเตอร์ ความหมายของการหาค่าเหมาะที่สุดทางคณิตศาสตร์ โครงการนี้เป็นทั้งการทดลองและฐานสำหรับการพัฒนาวิธีการหาค่าเหมาะที่สุดแบบทั่วไป มีศักยภาพสูงในการประยุกต์ใช้ในภาคอุตสาหกรรม การค้า การแพทย์ และสิ่งแวดล้อม การสร้างแบบจำลองทางคณิตศาสตร์ เป็นเครื่องมือสำคัญในการใช้ทรัพยากรที่มีจำกัดอย่างมีประสิทธิภาพ แนะนำคณะวิจัย William Cook: มหาวิทยาลัยวอเตอร์ลู ประเทศแคนาดา Daniel Espinoza: Alicanto Labs ประเทศชิลี Marcos Goycoolea: มหาวิทยาลัย Adolfo Ibáñez ประเทศชิลี Keld Helsgaun: มหาวิทยาลัยรอสกิลด์ ประเทศเดนมาร์ก คำขอบคุณ IBM CPLEX Optimizer: ขอขอบคุณที่ให้ใช้งานฟรีสำหรับงานวิจัยทางวิชาการ แผนที่สร้างด้วย Leaflet, OpenStreetMap, Carto, Stadia Maps ดร. Eom Sang-il ได้ให้ข้อมูลตำแหน่งบาร์ในเกาหลีที่อ้างอิงจากข้อมูลของสำนักงานตำรวจแห่งชาติเกาหลี การคำนวณเวลาเดินใช้ OSRM ตัวอย่างโครงการ TSP ในประเทศอื่น ญี่ปุ่น: ร้านสะดวกซื้อ 40,426 แห่ง สหราชอาณาจักร: ผับ 49,687 แห่ง สหรัฐอเมริกา: สถานที่ประวัติศาสตร์ 49,603 แห่ง เนเธอร์แลนด์: อนุสาวรีย์ 57,912 แห่ง แหล่งเรียนรู้เพิ่มเติม In Pursuit of the Traveling Salesman: ประวัติและการประยุกต์ใช้ของ TSP Traveling Salesman Problem: งานวิจัยการประยุกต์ใช้วิธี cutting plane The Golden Ticket: บทนำสู่ปัญหา P vs. NP Opt Art: การสร้างภาพศิลปะด้วย TSP Approximation Algorithms: งานวิจัยล่าสุดเกี่ยวกับอัลกอริทึมประมาณค่าสำหรับ TSP Computational Solutions for TSP Applications: หนังสือกรณีศึกษาเชิงประยุกต์ที่ตีพิมพ์ในปี 1994

(math.uwaterloo.ca)

23 คะแนน โดย xguru 2025-04-23 | 10 ความคิดเห็น | แชร์ทาง WhatsApp

ศาสตราจารย์ William Cook แห่งมหาวิทยาลัยวอเตอร์ลูคำนวณกรณีแรกของโลกที่ใช้ปัญหาพนักงานขายเดินทาง (TSP) กับเส้นทางที่สั้นที่สุดในการเยือน บาร์ 81,998 แห่ง ของเกาหลี
ใช้ Open Source Routing Machine (OSRM) คำนวณเวลาเดินประมาณ 3.3 พันล้านคู่ และพิสูจน์ได้ทางคณิตศาสตร์ว่าเป็นคำตอบที่เหมาะที่สุด
ผลการคำนวณระบุว่า หากเดินต่อเนื่องไม่หยุดจะใช้เวลา 15,386,177 วินาที หรือ 178 วัน 1 ชั่วโมง 56 นาที 17 วินาที
การหาคำตอบเหมาะที่สุดของ TSP ใช้เครื่องมือ LKH และ Concorde พร้อมประยุกต์ใช้ วิธี cutting plane
นี่คือ กรณีแก้ปัญหา TSP บนเครือข่ายถนนที่มีขนาดใหญ่ที่สุดในโลก แซงหน้าสถิติเดิมของ เนเธอร์แลนด์ 57,912 จุด

ปัญหาพนักงานขายเดินทาง (Traveling Salesman Problem) สำหรับการเดินครบทุกบาร์ในเกาหลี

คำนวณเส้นทางที่สั้นที่สุดในการไปเยือน บาร์ 81,998 แห่ง ในเกาหลีให้ครบแล้วกลับมายังจุดเริ่มต้น
เป็นการ แก้ปัญหา TSP แบบเหมาะที่สุด ที่มีจำนวนสถานที่มากขนาดนี้ได้เป็น ครั้งแรกของโลก
คำนวณเวลาเดินสำหรับจุดจับคู่ทั้งหมด 3,361,795,003 คู่ ระหว่างบาร์ด้วย OSRM - Open Source Routing Machine
พิสูจน์ทางคณิตศาสตร์ได้ว่า ไม่มีเส้นทางที่สั้นกว่านี้
ปัญหานี้เป็น TSP ขนาดใหญ่ที่สุดเท่าที่เคยมีมา เมื่อวัดจากจำนวนจุดที่ต้องแวะ

เวลาที่ใช้สำหรับเส้นทางสั้นที่สุด

หากเดินตามเส้นทางที่เหมาะที่สุดที่คำนวณได้โดยไม่หยุดพัก จะใช้เวลารวม 15,386,177 วินาที
คิดเป็น 178 วัน 1 ชั่วโมง 56 นาที 17 วินาที
ในความเป็นจริง ระหว่างเดินอาจต้องพักหรือดื่ม จึงแทบเป็นไปไม่ได้ที่จะจบได้ตรงเป๊ะ
เป็นเส้นทาง เหมาะที่สุด ที่แม้อิงตามเวลาเดินจาก OSRM ก็ไม่อาจลดลงได้แม้แต่ 1 วินาที

บริบททางประวัติศาสตร์ของ TSP และการทำลายสถิติ

สถิติเดิมคือ เส้นทางจักรยาน 57,912 จุดในเนเธอร์แลนด์
เส้นทาง korea81998 ครั้งนี้เป็น ตัวอย่างการแก้ปัญหา TSP ที่มีขนาดใหญ่กว่านั้น
การคำนวณดำเนินการที่ มหาวิทยาลัยรอสกิลด์ และ มหาวิทยาลัยวอเตอร์ลู ตั้งแต่เดือนธันวาคม 2024 ถึงมีนาคม 2025
รายละเอียดการคำนวณสามารถดูได้จาก หน้าคำนวณ แยกต่างหาก

วิธีการแสดงภาพเส้นทาง

สามารถดูเส้นทางผ่าน แผนที่อินเทอร์แอ็กทีฟ และสำรวจแบบแยกเป็น 7 ภูมิภาคได้
มีโหมดการแสดงผลหลายแบบ เช่น แผนที่ระยะสีและภาพขาวดำ
มีการจัดเตรียมภาพความละเอียดสูงของบางส่วนของเส้นทางไว้ต่างหาก
มุมมองขยายรายเมืองมีให้ใน หน้าของแต่ละเมือง

กลยุทธ์การแก้ TSP และความเข้าใจผิด

สื่อบางแห่งรายงานว่าแค่ “22 เมืองก็ต้องใช้เวลา 1,000 ปี” แต่สิ่งนั้นหมายถึง กรณีลองทุกเส้นทางแบบสุ่มทั้งหมด
ในความเป็นจริง จุดจำนวนมากก็สามารถแก้ได้ด้วยเทคนิคการหาค่าเหมาะที่สุดขั้นสูง
สำหรับ korea81998 จำนวนเส้นทางที่เป็นไปได้มีขนาดประมาณ เลข 2 ที่ตามด้วยเลข 0 จำนวน 367,308 ตัว
การแก้ปัญหาใช้ทั้ง LKH(Lin-Kernighan Heuristic) อัลกอริทึม และ Concorde TSP Solver - วิธี cutting plane ร่วมกัน

สรุปแนวคิดของวิธี cutting plane

อิงอยู่บนการโปรแกรมเชิงเส้น
แทนที่จะระบุว่าใช้ถนนเส้นใดหรือไม่ใช้ จะใช้ ค่าระดับการเชื่อมต่อระหว่าง 0 ถึง 1 แทน
เพิ่มเงื่อนไขข้อจำกัดทีละขั้นเพื่อค้นหา เส้นทางที่สั้นที่สุด
คำอธิบายเพิ่มเติมดูได้จาก Scientific American และ การบรรยายบน YouTube

ปัญหา P กับ NP

ปัญหา TSP เป็น ปัญหา NP-สมบูรณ์ และเป็นตัวอย่างสำคัญของประเด็น P กับ NP
การอภิปรายที่น่าสนใจเกี่ยวกับเรื่องนี้มีแนะนำไว้ในงานเขียนของ ศาสตราจารย์ Lance Fortnow
นี่คือหนึ่งใน ปัญหาที่ยังไม่ถูกแก้ที่มีชื่อเสียงที่สุดของวิทยาการคอมพิวเตอร์

ความหมายของการหาค่าเหมาะที่สุดทางคณิตศาสตร์

โครงการนี้เป็นทั้งการทดลองและฐานสำหรับการพัฒนาวิธีการหาค่าเหมาะที่สุดแบบทั่วไป
มีศักยภาพสูงในการประยุกต์ใช้ในภาคอุตสาหกรรม การค้า การแพทย์ และสิ่งแวดล้อม
การสร้างแบบจำลองทางคณิตศาสตร์ เป็นเครื่องมือสำคัญในการใช้ทรัพยากรที่มีจำกัดอย่างมีประสิทธิภาพ

แนะนำคณะวิจัย

William Cook: มหาวิทยาลัยวอเตอร์ลู ประเทศแคนาดา
Daniel Espinoza: Alicanto Labs ประเทศชิลี
Marcos Goycoolea: มหาวิทยาลัย Adolfo Ibáñez ประเทศชิลี
Keld Helsgaun: มหาวิทยาลัยรอสกิลด์ ประเทศเดนมาร์ก

คำขอบคุณ

IBM CPLEX Optimizer: ขอขอบคุณที่ให้ใช้งานฟรีสำหรับงานวิจัยทางวิชาการ
แผนที่สร้างด้วย Leaflet, OpenStreetMap, Carto, Stadia Maps
ดร. Eom Sang-il ได้ให้ข้อมูลตำแหน่งบาร์ในเกาหลีที่อ้างอิงจากข้อมูลของสำนักงานตำรวจแห่งชาติเกาหลี
การคำนวณเวลาเดินใช้ OSRM

ตัวอย่างโครงการ TSP ในประเทศอื่น

ญี่ปุ่น: ร้านสะดวกซื้อ 40,426 แห่ง
สหราชอาณาจักร: ผับ 49,687 แห่ง
สหรัฐอเมริกา: สถานที่ประวัติศาสตร์ 49,603 แห่ง
เนเธอร์แลนด์: อนุสาวรีย์ 57,912 แห่ง

แหล่งเรียนรู้เพิ่มเติม

In Pursuit of the Traveling Salesman: ประวัติและการประยุกต์ใช้ของ TSP
Traveling Salesman Problem: งานวิจัยการประยุกต์ใช้วิธี cutting plane
The Golden Ticket: บทนำสู่ปัญหา P vs. NP
Opt Art: การสร้างภาพศิลปะด้วย TSP
Approximation Algorithms: งานวิจัยล่าสุดเกี่ยวกับอัลกอริทึมประมาณค่าสำหรับ TSP
Computational Solutions for TSP Applications: หนังสือกรณีศึกษาเชิงประยุกต์ที่ตีพิมพ์ในปี 1994

10 ความคิดเห็น

ep6tri 2025-04-24

หน้าเว็บภาษาอังกฤษคือ https://www.math.uwaterloo.ca/tsp/korea/index.html
ทัวร์นี้ชัดเจนว่าไม่สมจริงอยู่แล้ว ดูเหมือนว่าจะไม่ได้พิจารณาเส้นทางทางเรือเมื่อต้องเดินทางจากแผ่นดินใหญ่ไปยังเกาะเชจูหรืออุลลึงโด ดูรูปนี้ได้เลย: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png

ประเด็นคงไม่ใช่การคำนวณเวลาโดยประมาณที่ต้องใช้ในการไปเยือนให้แม่นยำ แต่ควรให้ความสำคัญกับการที่นำ TSP มาประยุกต์แก้กับข้อมูลจากโลกจริงมากกว่า

skshin 2025-04-23

แล้วการเดินทางไปเกาะล่ะ? เดินเท้าเหรอ?

halfenif 2025-04-23

พอเห็นว่ามีคำว่า walking and ferry ก็เดาว่าคงต้องนั่งเรือด้วยครับ

woalsdnd 2025-04-23

แล้วกรณีที่มีร้านเปิดใหม่หรือปิดกิจการแบบเรียลไทม์ล่ะ ควรจัดการอย่างไร?

majorika 2025-04-23

> ผมมีกำหนดจะสอนวิชา TSP ที่ KAIST ในเมืองแทจอนในเดือนมีนาคม 2024 และกำลังมองหาชุดข้อมูลท้องถิ่นสำหรับทัวร์ TSP ในแทจอนอยู่ ในเดือนธันวาคม 2023 ดร. Eom Sang-il ได้ส่งอีเมลมาว่า "คุณต้องการชุดข้อมูลบาร์ทั่วประเทศที่สำนักงานตำรวจแห่งชาติจัดทำไว้ไหม? ไฟล์ล่าสุดราคา 1,000 วอน และมีรายการอยู่ 90,680 รายการ" ว้าว หลังจากเช็กก่อนว่า 1,000 วอนน้อยกว่า 1 ดอลลาร์จริงหรือไม่ (ซึ่งก็ดีแล้วที่ได้ตรวจว่าอัตราแลกเปลี่ยนไม่ได้สลับกัน) ผมก็ตอบกลับไปว่า "ขอบคุณครับ!"

https://www.math.uwaterloo.ca/tsp/korea/sk_data.html

kimjoin2 2025-04-23

ว้าว มีเบื้องหลังแบบนี้นี่เอง ขอบคุณสำหรับการสรุปและแบ่งปันครับ

kimjoin2 2025-04-23

ผมก็สงสัยเหมือนกันว่าทำไมถึงเลือกเกาหลีเป็นเป้าหมาย 👀

firea32 2025-04-28

การที่สามารถได้ข้อมูลคุณภาพดีในราคา 1,000 วอน ก็น่าจะเป็นอีกปัจจัยหนึ่งด้วย :)