การย้อนรอย (Backtracking) และการแยกและขอบเขต (Branch and Bound)

การย้อนรอยและการแยกและขอบเขตเป็นกระบวนทัศน์การค้นหาอย่างเป็นระบบที่สำรวจพื้นที่ของคำตอบที่เป็นไปได้ในรูปแบบของต้นไม้ โดยจะตัดกิ่งย่อยที่ไม่สามารถนำไปสู่คำตอบที่ถูกต้องหรือเหมาะสมที่สุดออก เพื่อให้การค้นหาที่มีความซับซ้อนแบบเอ็กซ์โพเนนเชียลสามารถจัดการได้ในทางปฏิบัติ

Definition

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

Scope

หัวข้อนี้ครอบคลุมเทคนิคการค้นหาแบบละเอียดที่จัดโครงสร้างรอบต้นไม้การค้นหา ได้แก่ การย้อนรอย ซึ่งจะละทิ้งตัวเลือกบางส่วนทันทีที่ละเมิดข้อจำกัด และการแยกและขอบเขต ซึ่งใช้ขอบเขตของวัตถุประสงค์ที่ดีที่สุดที่ทำได้เพื่อตัดกิ่งย่อยในการหาค่าที่เหมาะสมที่สุด โดยรวมถึงตัวอย่างการแก้ปัญหาข้อจำกัด (ปัญหา N-queens, การระบายสีกราฟ, ซูโดกุ) และตัวอย่างการหาค่าที่เหมาะสมที่สุดเชิงการจัดหมู่ (ปัญหาพนักงานขายเดินทาง, การโปรแกรมจำนวนเต็ม) และอภิปรายว่าเหตุใดวิธีการเหล่านี้จึงยังคงมีคุณค่าสำหรับปัญหา NP-hard แม้จะมีค่าใช้จ่ายแบบเอ็กซ์โพเนนเชียลในกรณีที่เลวร้ายที่สุด

Core questions

• พื้นที่คำตอบของปัญหาถูกจำลองเป็นต้นไม้การค้นหาของการกำหนดค่าบางส่วนได้อย่างไร?
• การตรวจสอบข้อจำกัดใดที่ช่วยให้การย้อนรอยสามารถตัดกิ่งที่ไม่สามารถทำได้ตั้งแต่เนิ่นๆ?
• มีการคำนวณขอบเขตล่างและขอบเขตบนเพื่อตัดกิ่งในการหาค่าที่เหมาะสมที่สุดได้อย่างไร?
• ลำดับของการแยกและขอบเขตส่งผลต่อประสิทธิภาพในทางปฏิบัติอย่างไร?
• เหตุใดวิธีการเหล่านี้จึงถูกนำมาใช้สำหรับปัญหา NP-hard แม้จะมีกรณีที่เลวร้ายที่สุดเป็นแบบเอ็กซ์โพเนนเชียล?

Key concepts

• ต้นไม้การค้นหา
• การสำรวจแบบเจาะลึก
• การเผยแพร่ข้อจำกัด
• การตัดกิ่ง
• ฟังก์ชันขอบเขต
• คำตอบปัจจุบัน
• ปัญหา N-queens
• การผ่อนคลายการโปรแกรมจำนวนเต็ม

Key theories

การตัดกิ่งของต้นไม้การค้นหา

ทั้งสองกระบวนทัศน์จัดเรียงคำตอบที่เป็นไปได้เป็นต้นไม้ที่สำรวจแบบเจาะลึก ความถูกต้องมาจากการสำรวจอย่างละเอียด ในขณะที่ประสิทธิภาพมาจากการตัดกิ่งย่อยที่ไม่สามารถมีคำตอบที่ถูกต้องหรือดีขึ้นได้

ฟังก์ชันขอบเขตในการแยกและขอบเขต

การแยกและขอบเขตจะรักษาคำตอบที่ดีที่สุดที่พบมาแล้วและขอบเขต (เช่น การผ่อนคลาย LP) ของค่าที่ดีที่สุดที่สามารถทำได้ในแต่ละกิ่งย่อย กิ่งย่อยจะถูกละทิ้งเมื่อขอบเขตของมันไม่สามารถปรับปรุงคำตอบปัจจุบันได้

Clinical relevance

การแยกและขอบเขตเป็นแกนหลักของการหาค่าที่เหมาะสมที่สุดเชิงการจัดหมู่ที่แม่นยำในการวิจัยดำเนินงาน รวมถึงตัวแก้ปัญหาการโปรแกรมจำนวนเต็มและจำนวนเต็มผสมที่ใช้สำหรับการจัดตารางเวลา การกำหนดเส้นทาง และการวางแผน การย้อนรอยเป็นพื้นฐานของตัวแก้ปัญหาข้อจำกัด การค้นหาแบบ SAT การแก้ปริศนา และตัวแยกวิเคราะห์ ซึ่งการค้นหาอย่างเป็นระบบพร้อมการตัดกิ่งเป็นแนวทางปฏิบัติในการหาคำตอบที่แม่นยำ

History

การย้อนรอยได้รับการจัดระบบให้เป็นเทคนิคทั่วไปในช่วงทศวรรษ 1950 และ 1960 โดยเฉพาะอย่างยิ่งที่อธิบายโดย Golomb และ Baumert ส่วนการแยกและขอบเขตถูกนำเสนอโดย Ailsa Land และ Alison Doig ในปี 1960 สำหรับการโปรแกรมเชิงเส้นจำนวนเต็ม และตั้งแต่นั้นมาก็กลายเป็นหัวใจสำคัญของการหาค่าที่เหมาะสมที่สุดเชิงการจัดหมู่ ซึ่งเป็นรากฐานของตัวแก้ปัญหาการโปรแกรมจำนวนเต็มผสมสมัยใหม่

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

ความแตกต่างระหว่างการย้อนรอยและการแยกและขอบเขตคืออะไร?

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

หากวิธีการเหล่านี้มีความซับซ้อนแบบเอ็กซ์โพเนนเชียลในกรณีที่เลวร้ายที่สุด เหตุใดจึงยังใช้?

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