อัลกอริทึมการแตกกิ่งและกำหนดขอบเขตสำหรับปัญหาการเดินทางของพนักงานขายภายใต้ความน่าจะเป็นที่กลับไปยังจุดเริ่มเดินทาง

บทคัดย่อ

งานวิจัยนี้ได้นำหลักการของการแตกกิ่งและกำหนดขอบเขตมาสร้างอัลกอริทึมที่ใช้สำหรับแก้ปัญหาการเดินทางของพนักงานขายภายใต้ความน่าจะเป็นที่กลับไปยังจุดเริ่มเดินทาง   กระบวนการประกอบด้วย 3 ขั้นตอนหลัก    ขั้นตอนการแตกกิ่งเป็นขั้นแรกของการดำเนินการเกี่ยวข้องกับการแบ่งแยกปัญหาออกเป็นปัญหาย่อยขนาดเล็กลงเพื่อช่วยให้แก้ไขปัญหาได้ง่ายและรวดเร็วขึ้น  คำตอบของแต่ละปัญหาย่อยจะถูกตรวจสอบความสมเหตุสมผลต่อไปโดยเปรียบเทียบกับขีดจำกัดบนและขีดจำกัดล่าง  ขั้นที่สองคือการกำหนดค่าขอบเขตทั้งขอบเขตบนและขอบเขตล่างจะได้รับการปรับค่าให้ดีขึ้นกว่าเดิม โดยคำตอบที่เป็นไปได้จะอยู่ในช่วงขอบเขตบนและขอบเขตล่างเท่านั้น    ขั้นที่สามคือการเลือกโหนดด้วยวิธีการโดดข้ามกิ่งไปแก้ปัญหาย่อยที่ให้ผลลัพธ์ดีที่สุดก่อน อัลกอริทึมจะทำงานไปเรื่อยๆ ผ่านการคำนวณหลายรอบจนกระทั่งค้นพบคำตอบที่เหมาะสมที่สุด  คำตอบดังกล่าวคือลำดับการเดินทางที่ให้เส้นทางที่สั้นที่สุด  ขั้นตอนข้างต้นยังได้ถูกนำไปพัฒนาต่อเป็นโปรแกรมคอมพิวเตอร์ที่สามารถหาผลเฉลยได้ในเวลาที่ยอมรับได้ เช่น ขนาดเมือง 15 เมืองใช้เวลาประมวลผลไม่ถึงวินาทีและจำนวนเมือง 800 เมืองใช้เวลาคำนวณประมาณ 30 นาที