ใช้ Branch&Bound เอาชนะ Ulysses16

จาก http://garnet.cpe.ku.ac.th/~g5065386/?p=341 ก็รู้จาก TSP, TSPLIB และ Ulysses16 ไปแล้ว ทีนี้ลองเขียน B&B แก้ปัญหา แล้วมาดูผลกันว่า ถูกต้องตาม Official Record หรือเปล่า

แต่อย่างไรก็ดีอยากเกริ่นให้ทราบว่า ถ้าหากเราไม่ Bound คำตอบที่ไม่จำเป็นเสียบ้าง .. search space ของเราจะมีขนาดเท่ากับ 15! = 1,307,674,368,000 เลยทีเดียว!!!

ผลที่ได้จาก Branch & Bound

อ่านเพิ่มเติม

เรื่องเล่าของ Travelling Salesman Problem (TSP) และ Ulysses16

เข้าใจว่าถ้าที่ปรึกษาได้แอบมาอ่าน Blog ก็จะคิดในใจว่า .. “ทำไมทำ (มัน) Thesis ไปไม่ถึงไหนสักที (วะ) ?” .. ก็พอจะเข้าใจได้เพราะก็แวะเวียนทุกที่ที่คิดว่าน่าสนใจ ตั้งแต่ 2 เดือนก่อนแล้ว DFS, BFS, Backtracking, Greedy, Dynamic Programming, Branch & Bound, .. และตอนนี้ ก็ถึง GA เสียที (หากมีเวลาจะกลับมาเก็บ Local Search, 2-OPT, Simulated Annealing, TABU อีกนะ)

แต่แน่นอน ไม่ว่าจะแนวคิดไหน Concept ใดก็ต้องมีที่มาที่ไป และข้อดีข้อเสียด้วยกันทั้งนั้น ก็เลยลองเขียน Branch & Bound สู้กับ GA (อ่อนๆ) สักตั้ง .. ดูซิว่าจะเป็นอย่างไร … ซึ่งก็แน่นอนว่าจะสู้กัน ก็ต้องมี Input เหมือนกัน ก็เลยหยิบ Ulysses16 มาลองเล่นดู … แต่เอ คุณ ‘อุลัย’ แกเป็นใคร ???? … เปิด wiki ก็พอได้ Idea ว่า อ้าว.. เทพนิยายมหากาพย์ Odessey นั่นเอง

อ่านเพิ่มเติม

Multiple Travelling Salesman Problem (mTSP)

ปัญหาที่สืบเนื่องจาก Travelling Salesman Problem ที่ว่า ถ้ามี Salesman มากกว่าหนึ่งคน แล้วต้องการให้แต่กระจายกันเข้าถึงทุก Node เพียงครั้งเดียวเท่านั้น จะสามารถออกแบบเส้นทาง (Tour) ของ Salesman ทุกคน ได้อย่างไร

แล้วมี Variations อะไรบ้าง ?

รวมถึงมีการเสนอวิธีการแก้ปัยหาอย่างไรบ้าง ?

Variations in Travelling Salesman Problem (TSP)

Simple TSP เราทราบกันแล้วว่า คือปัญหา “Shortest Hamiltonian Cycle” กล่าวคือ พยายามหาเส้นทางที่สั้นที่สุด จากจุดเริ่มต้นเดินทางผ่านทุกจุด แล้วกลับมายังจุดเริ่มต้นอีกครั้ง โดยให้สามารถผ่านแต่ละจุดได้เพียงครั้งเดียวเท่านั้น .. เปรียบได้กับในชีวิตจริง เช่น ปัญหาการผูกเชือกรองเท้า “The Shorlace Problem” เป็นต้น

แต่หากเปลี่ยนข้อกำหนดใหม่ เช่น ให้สามารถผ่านแต่ละจุดได้ซ้ำกันมากกว่า หนึ่งครั้ง ประเด็นของปัญหาก็จะเปลี่ยนไป … และเป็นเหตุให้ ได้รูปแบบของ TSP ที่หลากหลายต่างออกไป

อ่านเพิ่มเติม

Travelling Salesman Problem (TSP)

TSP เป็น “Combinatorial Optimization” ที่ศึกษากันใน “Operations Research” และ “Theoretical Computer Science” โดยให้กลุ่มของเมือง และกลุ่มเส้นทางที่เชื่อมถึงกัน จากนั้นตั้งคำถามว่า ควรเลือกใช้เส้นทางใด ที่จะผ่านทุกเมือง โดยใช้เส้นทางสั้นที่สุด

อ่านเพิ่มเติม