เครื่องกําเนิดเขาวงกต Backtracker แบบเรียกซ้ํา

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

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

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

อัลกอริทึมย้อนกลับแบบเรียกซ้ําเป็นวิธีการค้นหาที่เน้นความลึกเป็นอันดับแรกสําหรับการสร้างเขาวงกตที่สมบูรณ์แบบ (เขาวงกตที่ไม่มีลูปและมีเส้นทางเดียวระหว่างจุดสองจุด) มันเรียบง่ายมีประสิทธิภาพและสร้างเขาวงกตที่ดึงดูดสายตาด้วยทางเดินที่ยาวและคดเคี้ยว

แม้จะมีชื่อ แต่ก็ไม่จําเป็นต้องนําไปใช้โดยใช้การเรียกซ้ํา มักถูกนําไปใช้ในวิธีการทําซ้ําโดยใช้คิว LIFO (เช่น สแต็ก) สําหรับเขาวงกตขนาดใหญ่มากการใช้การเรียกซ้ํามีแนวโน้มที่จะส่งผลให้เกิดการล้นสแตกการโทรขึ้นอยู่กับภาษาโปรแกรมและหน่วยความจําที่มีอยู่ คิว LIFO สามารถปรับให้เข้ากับการจัดการข้อมูลจํานวนมากได้ง่ายขึ้น แม้กระทั่งเก็บคิวไว้บนดิสก์หรือในฐานข้อมูลหากหน่วยความจําที่มีอยู่ไม่เพียงพอ

วิธีการทํางาน

อัลกอริทึมทํางานโดยใช้แนวทางการค้นหาแบบ stack-based depth-first นี่คือรายละเอียดทีละขั้นตอน:

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

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

ฉันมีอัลกอริทึมนี้สองเวอร์ชันในการเล่นบนเว็บไซต์นี้: คิว LIFO ที่ใช้คิวสําหรับสร้างเขาวงกตในหน้านี้และคิวแบบเรียกซ้ําสําหรับการแก้เขาวงกต รวมถึงเขาวงกตที่สร้างโดยอัลกอริทึมอื่น ๆ (นั่นคือวิธีการสร้างแผนที่พร้อมวิธีแก้ปัญหา) การมีสองเวอร์ชันที่แตกต่างกันนั้นมีไว้สําหรับกีฬาเท่านั้นเพราะฉันเป็นคนเนิร์ดที่พบว่ามันน่าสนใจ