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

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

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

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

อัลกอริทึมการเรียกซ้ำแบบย้อนกลับ (Recursive Backtracker Algorithm) เป็นวิธีการค้นหาเชิงลึก (Depth-First Search) สำหรับสร้างเขาวงกตที่สมบูรณ์แบบ (เขาวงกตที่ไม่มีวงวนและมีเส้นทางเดียวระหว่างจุดสองจุดใดๆ) อัลกอริทึมนี้เรียบง่าย มีประสิทธิภาพ และสร้างเขาวงกตที่สวยงามด้วยทางเดินยาวคดเคี้ยว

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

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

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

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

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

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

อ่านเพิ่มเติม

หากคุณชอบโพสต์นี้ คุณอาจชอบคำแนะนำเหล่านี้ด้วย:

• เครื่องกําเนิดเขาวงกตอัลกอริทึมของ Kruskal
• ตัวสร้างเขาวงกตต้นไม้ที่เติบโต
• เครื่องกําเนิดเขาวงกตอัลกอริทึมของวิลสัน