สารบัญ:
คำจำกัดความ - Backtracking หมายถึงอะไร?
Backtracking เป็นอัลกอริทึมสำหรับการจับภาพการแก้ปัญหาบางส่วนหรือทั้งหมดในการคำนวณปัญหา อัลกอริทึมสามารถใช้ได้เฉพาะกับปัญหาที่ยอมรับแนวคิดของ "วิธีการแก้ปัญหาบางส่วน" และอนุญาตให้ทดสอบอย่างรวดเร็วเพื่อดูว่าโซลูชันของผู้สมัครนั้นเป็นโซลูชันที่สมบูรณ์หรือไม่ Backtracking ถือเป็นเทคนิคสำคัญในการแก้ปัญหาข้อ จำกัด และปริศนาความพึงพอใจ มันยังถือว่าเป็นเทคนิคที่ยอดเยี่ยมสำหรับการวิเคราะห์คำและสร้างพื้นฐานของภาษาการเขียนโปรแกรมเชิงตรรกะ
Techopedia อธิบาย Backtracking
Backtracking ช่วยในการแก้ปัญหาโดยรวมโดยค้นหาวิธีแก้ไขปัญหาย่อยแรกแล้วพยายามเรียกใช้ซ้ำเพื่อแก้ไขปัญหาย่อยอื่น ๆ ตามวิธีแก้ปัญหาของปัญหาแรก หากไม่สามารถแก้ไขปัญหาปัจจุบันได้ขั้นตอนจะย้อนรอยและวิธีแก้ไขที่เป็นไปได้ถัดไปจะถูกนำไปใช้กับขั้นตอนก่อนหน้าและดำเนินการต่อไป ในความเป็นจริงหนึ่งในสิ่งสำคัญในการย้อนรอยคือการเรียกซ้ำ นอกจากนี้ยังถือว่าเป็นวิธีการค้นหาที่ละเอียดถี่ถ้วนโดยใช้การหารและพิชิต อัลกอริทึมการย้อนรอยจะสิ้นสุดลงเมื่อไม่มีวิธีแก้ปัญหาสำหรับปัญหาย่อยแรกอีกต่อไป
Backtracking เป็นอัลกอริทึมที่สามารถช่วยให้เกิดการใช้งานของ nondeterminism ใช้เวลาค้นหาเชิงลึกครั้งแรกของพื้นที่ปัญหาที่กำหนด ส่วนใหญ่จะใช้ในภาษาการเขียนโปรแกรมเชิงตรรกะเช่น Prolog ไม่ว่าจะใช้การย้อนรอยใดก็ตามมันเร็วกว่าเทคนิคการบังคับแบบเดรัจฉานเนื่องจากจะกำจัดผู้สมัครจำนวนมากด้วยการทดสอบครั้งเดียว
