ตัดกิ่งเพื่อให้อยู่รอดในขีดจำกัดเวลา

การย้อนกลับแบบไม่ลดกิ่งอาจสำรวจกิ่งมากเกินไปจนชนขีดจำกัดเวลา การตัดกิ่งจะตัดกิ่งที่หมดหวังตั้งแต่เนิ่น ๆ เพื่อให้ทำงานได้รวดเร็ว ✂️

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

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

ติดตามคำตอบที่ดีที่สุดที่พบจนถึงตอนนี้ หากคำตอบที่ดีที่สุดที่กิ่งหนึ่งอาจทำได้ยังแย่กว่า ก็ให้ตัดกิ่งนั้น นี่คือขอบเขตของกิ่ง

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

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

หลังจากเลือกแล้ว ให้จำกัดสิ่งที่ขั้นตอนถัดไปสามารถทำได้ การนำทางเลือกที่เป็นไปไม่ได้ออกตั้งแต่ต้นเรียกว่าการส่งต่อข้อจำกัด และช่วยลดขนาดต้นไม้

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

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

ตรวจสอบเงื่อนไขการตัดกิ่งก่อนการเรียกซ้ำ ไม่ใช่หลังจากนั้น การตัดกิ่งตั้งแต่ต้นช่วยหลีกเลี่ยงงานที่เสียไปกับการขยายกิ่งที่หมดหวัง

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

เป้าหมายของการตัดกิ่งในการย้อนกลับคืออะไร

ได้เรียนรู้การตัดกิ่งด้วยการตรวจสอบความเป็นไปได้และขอบเขต การจัดลำดับอย่างชาญฉลาด การทำลายสมมาตร และการจดจำผลลัพธ์ เพื่อรับมือกับขีดจำกัดเวลา 🎯