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

 (math.uwaterloo.ca)
2 คะแนน โดย GN⁺ 2025-04-25 | 2 ความคิดเห็น | แชร์ทาง WhatsApp
  • ปัญหาพนักงานขายเดินทาง (TSP) คือปัญหาการหาเส้นทางที่สั้นที่สุดเพื่อไปเยือน บาร์ 81,998 แห่งในเกาหลี และได้ถูกแก้ด้วย Open Source Routing Machine (OSRM)
  • เส้นทางนี้เป็น เส้นทางที่เหมาะที่สุด ซึ่งใช้เวลามากกว่า 178 วัน และได้รับการพิสูจน์ผ่านการคำนวณของ OSRM
  • ใช้ โค้ด LKH และ โค้ด Concorde พร้อมประยุกต์ cutting-plane method เพื่อแก้ปัญหา TSP ขนาดใหญ่
  • การหาค่าเหมาะที่สุดทางคณิตศาสตร์ และ การวิจัยดำเนินงาน มุ่งเน้นการพัฒนาเครื่องมือเพื่อเพิ่มประสิทธิภาพการใช้ทรัพยากร
  • งานวิจัยดำเนินการที่ Roskilde University และ University of Waterloo โดยใช้ IBM CPLEX Optimizer และไลบรารี Leaflet

เส้นทางที่สั้นที่สุดเพื่อเยือนบาร์ 81,998 แห่งในเกาหลี

  • ปัญหาพนักงานขายเดินทาง (TSP) คือปัญหาการหาเส้นทางที่สั้นที่สุดเพื่อไปเยือน บาร์ 81,998 แห่งในเกาหลี และได้ถูกแก้ด้วย Open Source Routing Machine (OSRM)
  • เส้นทางนี้เป็น เส้นทางที่เหมาะที่สุด ซึ่งใช้เวลามากกว่า 178 วัน และได้รับการพิสูจน์ผ่านการคำนวณของ OSRM
  • ใช้ โค้ด LKH และ โค้ด Concorde พร้อมประยุกต์ cutting-plane method เพื่อแก้ปัญหา TSP ขนาดใหญ่

การแก้ปัญหา TSP ขนาดใหญ่

  • การหาค่าเหมาะที่สุดทางคณิตศาสตร์ และ การวิจัยดำเนินงาน มุ่งเน้นการพัฒนาเครื่องมือเพื่อเพิ่มประสิทธิภาพการใช้ทรัพยากร
  • งานวิจัยดำเนินการที่ Roskilde University และ University of Waterloo และใช้ IBM CPLEX Optimizer กับไลบรารี Leaflet

ทีมวิจัยและคำขอบคุณ

  • ทีมวิจัยประกอบด้วย William Cook, Daniel Espinoza, Marcos Goycoolea, Keld Helsgaun
  • ใช้ CPLEX Optimizer ของ IBM และไลบรารี Leaflet ในการดำเนินงานวิจัย
  • ได้ข้อมูลตำแหน่งของบาร์ในเกาหลีจากฐานข้อมูลของ สำนักงานตำรวจแห่งชาติเกาหลี

บทความที่เกี่ยวข้อง

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

 
xguru 2025-04-25

ผมได้โพสต์บทความ เส้นทางเดินที่สั้นที่สุดในการตระเวนบาร์ทั้ง 81,998 แห่งของเกาหลี ลงบน Hacker News ด้วยแอ็กเคานต์ของ GeekNewsครับ
ได้รับโหวตเยอะจนขึ้นอันดับบนสุดอยู่ 6 ชั่วโมง และกลายเป็นโพสต์ยอดนิยม เลยถูกนำกลับเข้ามาใน GN+ อีกครั้งหนึ่ง

บทความนั้นมีเวอร์ชันภาษาอังกฤษรวมอยู่ด้วย ผมเลยลองทำแบบนั้นดู และต่อไปก็ตั้งใจว่าจะลองโพสต์บทความที่มีภาษาอังกฤษรวมอยู่เป็นครั้งคราวไปทาง Hacker News ครับ
 
GN⁺ 2025-04-25
ความคิดเห็นจาก Hacker News
  • โซลูชัน TSP ที่มีดาว 133 ล้านดวงนั้นน่าประทับใจ
    • ทัวร์นี้มีความยาว 1.0038 เท่าของเส้นทางที่สั้นที่สุด
    • อยากรู้ว่าผลลัพธ์จะแย่ลงแค่ไหนหากใช้อัลกอริทึมเชิงความน่าจะเป็นของ Bell Labs
  • คำอธิบายแนวทาง TSP แบบคลาสสิก
    • เชื่อมทุกโหนดเข้าด้วยกันด้วยเส้นทางแบบสุ่ม
    • ตัดเส้นทางออกสองจุดเพื่อให้กลายเป็นสามส่วน
    • จัดเรียงสามส่วนนั้นใหม่ในหกวิธีที่เป็นไปได้ แล้วเลือกแบบที่สั้นที่สุด
    • ทำซ้ำขั้นตอนที่ 2-3 จนกว่าจะไม่มีการปรับปรุง
    • ไม่ได้รับประกันว่าจะได้ผลลัพธ์ที่ดีที่สุด แต่สำหรับปัญหาในโลกจริงส่วนใหญ่ มักได้คำตอบที่ดีที่สุดหรือใกล้เคียงมาก
  • แปลกที่ไม่มีการพูดถึงระยะทางรวม
    • แม้เป้าหมายคือการแก้เรื่องเวลาเดินทาง แต่การรู้ระยะทางที่เดินจริงก็น่าสนใจเช่นกัน
    • สามารถคำนวณการเผาผลาญแคลอรี หรือดูว่าเบี่ยงเบนจากเส้นทางระยะสั้นที่สุดไปมากแค่ไหนได้
  • รู้สึกท่วมท้นเมื่อคิดว่าประเทศขนาดพอ ๆ กับรัฐโอไฮโอมีบาร์เกือบ 82,000 แห่ง
  • ช่วง COVID ตั้งเป้าหมายว่าจะเดินทุกถนนในเมืองโดยใช้ CityStrides
    • มันติดตามระยะทางที่เดิน และบอกว่าเราเดินไปแล้วกี่เปอร์เซ็นต์ของเมือง
    • แม้จะไม่ได้ปรับเส้นทางให้เหมาะที่สุด แต่การพยายามเดินให้ได้ระยะมากที่สุดโดยไม่ซ้ำก็เป็นปริศนาทางความคิดที่สนุก
    • เครื่องมืออัตโนมัติก็คงสนุกได้เหมือนกัน แต่การทำด้วยมือต่างหากที่เป็นส่วนหนึ่งของการเดินทาง
    • ถ้าเข้าไปดูเว็บไซต์ CityStrides ก็จะเห็น LifeMaps ของผู้คนได้
    • บางคนเดินในปริมาณที่น่าทึ่งมาก
  • ทำให้นึกถึงคำถามที่กองทัพไอร์แลนด์ในยุค 60 เคยถาม
    • "จะไปจาก Bachelor's Walk ถึง Collins Barracks โดยไม่ผ่านบาร์ได้อย่างไร?"
    • คำตอบคือ "เข้าไปทุกบาร์"
  • การหาชุดข้อมูลนี้เจอน่าประทับใจ แต่ก็ไม่ได้ยากกว่าเดิมมากนัก
    • มันเป็นสมดุลที่ละเอียดอ่อนระหว่างการทำลายสถิติสูงสุดล่าสุดของปัญหาพนักงานขายเดินทางกับการคำนวณไม่เสร็จ
  • NP ดูเหมือน P อีกครั้ง
    • ตอนเรียนเคยเรียนมาว่า 13 คือค่าสูงสุด และในยุค 80 อาจารย์พัฒนาไปถึง 15
    • หลังจากนั้นก็เป็น 20, 20,000 และครั้งนี้พิสูจน์ได้ถึง 80,000
    • หน้า World TSP ระบุว่าสถิติอยู่ที่ 1 ล้าน
    • ค่าที่เหมาะที่สุดที่พิสูจน์ได้ซึ่งใหญ่ที่สุดในปัจจุบันคือ 3,178,031
    • ต้องทำด้วย CUDA ไม่ใช่ C ทั่วไป
  • Branch-and-bound เป็นอัลกอริทึมแบบ "หลุดมาจากตำรา"
    • ถ้ามอง LP solver เป็นกล่องดำ มันเรียบง่ายมากในระดับพื้นฐาน แต่มีประโยชน์อย่างยิ่ง
  • ดูเหมือนจะมีบาร์ใหม่เปิดเพิ่มขึ้นหลายแห่ง และบางแห่งก็ปิดไปแล้ว
    • ได้เวลาคำนวณใหม่แล้ว