การบ้าน : Branch & Bound Algorithm
(Travelling Salesperson Problem)

• เลือกก่อนที่ drop-down list ว่าจะสร้าง complete graph กี่ปม
• จากนั้นกดปุ่ม Random เพื่อสุ่มสร้างตำแหน่งของปม (จะนำเมาส์ไปคลิกปมเพิ่มก็ทำได้)
• กดปุ่ม Play ก็จะเิริ่มหาการเดินทางของพนักงานขาย
• ระหว่างการทำงานจะแสดงจำนวนปมในแต่ละระดับของต้นไม้ปริภูมิสถานะ ที่ตัวอัลกอริทึมได้ไปเยี่ยมเยียนเพื่อตรวจสอบสถานะ  เช่นถ้าสร้างกราฟ 5 ปม แล้วระหว่างการค้น ณ ขณะหนึ่งแสดง 1, 4, 10, 2, 1  หมายความว่าได้สำรวจแล้ว 1 ราก  4 ปมในระดับที่หนึ่ง 10 ปมในระดับสอง   2 ปมในระดับสาม  และ 1 ปมในระดับล่างสุดของต้นไม้ เป็นต้น
  
• อัลกอริทึมที่ใช้คือ branch & bound แบบที่ใช้การคำนวณ lower bound ของความยาวรวมของการเดินทางแบบง่าย ๆ ที่นำเสนอในชั้นเรียน
  
• คำเตือน : โปรแกรมนี้ทำงานช้าเมื่อจำนวนปมมีเกิน 15  หรืออาจถึงขั้นทำจนแจ้งเตือนว่าหน่วยความจำไม่พอด้วย (บนเครื่องผม จะเกิดอาการล้นหน่วยความจำที่ jvm จองไว้ เมื่อได้สำรวจปมในต้นไม้ปริภูมิสถานะไปประมาณเกือบสองล้านปม ใช้เวลาทำงานไปประมาณ 4 นาที  และตัว IE แจ้งว่ากินหน่วยความจำไป 131MB !!!)
  

ข้างบนนี้เราถือว่ามี complete graph เราไม่ได้แสดงเส้นเชื่อม เพราะจะแน่นไปหมด) โดยความยาวของเส้นเชื่อมมีค่าเป็นระยะทางระหว่างจุด (หมายความว่าความยาวของเส้นเชื่อมระหว่างจุด i กับ j sqrt( (x_i-x_j)² + (y_i-y_j)²)   จึงมักเรียกปัญหานี้ว่า Euclidean Travelling Salesperson Problem

วิธีส่ง

HW327-03-xxxxxxxxxx ตามด้วยชื่อสกุล

โดยที่ xxxxxxxxxx คือรหัสนิสิต ให้เวลา 10 วัน หมดเขต 16 ก.ย. ศกนี้

ถ้ามีเวลาอีกสักนิด