บทนำสู่การย้อนรอย

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

อัลกอริทึมการย้อนรอยถูกนำไปใช้กับปัญหาบางประเภท

• ปัญหาการตัดสินใจใช้เพื่อค้นหาวิธีแก้ปัญหาที่เป็นไปได้ของปัญหา

• ปัญหาการเพิ่มประสิทธิภาพที่ใช้เพื่อค้นหาแนวทางแก้ไขที่ดีที่สุดที่สามารถใช้ได้

• ปัญหาการแจงนับใช้เพื่อค้นหาชุดของวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมด

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

ตัวอย่าง

ที่นี่

สีเขียวคือจุดเริ่มต้น สีน้ำเงินคือจุดกึ่งกลาง สีแดงคือจุดที่ไม่มีทางแก้ได้ สีเขียวเข้มคือจุดสิ้นสุด

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

อัลกอริทึม

ขั้นตอนที่ 1 − ถ้า current_position เป็นเป้าหมาย ให้ return SuccessStep 2 − else ขั้นที่ 3 − หาก current_position เป็นจุดสิ้นสุด การกลับล้มเหลวขั้นตอนที่ 4 − มิฉะนั้น หาก current_position ไม่ใช่จุดสิ้นสุด ให้สำรวจและทำซ้ำขั้นตอนข้างต้น 

 ลองใช้ปัญหาย้อนรอยนี้เพื่อหาทางแก้ไข ปัญหา N-Queen .
 

 ในปัญหาของ N-Queen เราได้รับกระดานหมากรุก NxN และเราต้องวางราชินี n ตัวบนกระดานในลักษณะที่ไม่มีราชินีสองตัวโจมตีกัน ราชินีจะโจมตีราชินีอีกตัวหนึ่ง หากวางไว้ในแนวนอน แนวตั้ง หรือแนวทแยงขวางขวางทาง ที่นี่เราจะทำปัญหา 4-Queen
 

 วิธีแก้ไขคือ −
 

 
 

 ที่นี่ เอาต์พุตไบนารีสำหรับปัญหา n ควีนที่มี 1 เป็นควีนไปยังตำแหน่งจะถูกวาง
 
{0 , 1 , 0 , 0}; 0 , 0 , 1}}
 

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

 ขั้นตอนที่ 1 - เริ่มจากตำแหน่งที่ 1 ในอาร์เรย์
 ขั้นตอนที่ 2 - วางราชินีในกระดานและตรวจสอบ ทำ ขั้นตอนที่ 2.1 - หลังจากวางราชินีแล้ว ให้ทำเครื่องหมายตำแหน่งเป็นส่วนหนึ่งของการแก้ปัญหา จากนั้นตรวจสอบซ้ำๆ ว่าจะนำไปสู่การแก้ปัญหาหรือไม่ ขั้นตอนที่ 2.2 - ตอนนี้ ถ้าการวางราชินีไม่ได้นำไปสู่การแก้ปัญหาและการติดตามและไปที่ขั้นตอน (a) และวางราชินีในแถวอื่น ขั้นตอนที่ 2.3 – หากวางราชินีส่งกลับนำไปสู่การแก้ปัญหาส่งคืน TRUE ขั้นตอนที่ 3 - หากวางควีนทั้งหมดกลับ TRUE 

 ขั้นตอนที่ 4 - หากลองแถวทั้งหมดแล้วและไม่พบวิธีแก้ไข ให้คืนค่า FALSE
 
 

 ตอนนี้ ใช้การย้อนรอยเพื่อแก้ หนูในเขาวงกต ปัญหา -
 

 ในหนูที่อยู่ในปัญหาเขาวงกต เราอยู่กับเขาวงกต NxN ในตำแหน่งแรกของเขาวงกต นั่นคือ [0][0] และจะสิ้นสุดที่ตำแหน่ง [n-1][n-1] ของอาร์เรย์ ในเส้นทางนี้มีทางตันบางเส้นทางที่ไม่มีทางแก้ไขได้
 

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

 
 

 ที่นี่เส้นประแสดงเส้นทางที่เดินทาง