ใช้ 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

ค่า Optimal อย่างเป็นทางการของ Ulysses16 คือ 6859 และคำตอบคือ 1 14 13 12 7 6 15 5 11 9 10 16 3 2 4 8

อันนี้ได้จาก Code python ที่เขียนเอง .. Opt. ค่าเดียวกัน .. แต่ คนละเส้นทาง คือ 1 8 4 2 3 16 10 9 11 5 15 6 7 12 13 14 หาได้ในรอบที่ 346,203 (การสร้างคำตอบจาก [1] -> [1 2] ก็นับเป็นหนึ่งรอบการทำงาน.. ถูกหรือเปล่า ?)

result.JPG

ถ้าตาม TSPLIB95.doc แล้วเขาบอกว่า เขาก็ใช้ Branch&Cut ?? กับ Branch&Bound เหมือนกัน แต่ไม่แน่ในว่าตอนขยายกิ่งนั้นมีการเข้าหาคำตอบแบบไหน .. ถ้าที่ทำอยู่คือ DFS .. พยายามให้รากลึกๆถูกเข้าถึงก่อน เพื่อบริหาร Heap ให้ไม่ต้องจำเส้นทางที่รอพิจารณามากเกินไป .. เพราะตอน run แบบอาศัย Bound (Bound คำตอบไหนน้อยกว่า แตกออกมาก่อน) ของคำตอบเป็นหลัก เกิด memory alloc error ใน Heap

Del.icio.us : , ,
Technorati : , ,

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s