ล่าและฆ่าเครื่องกําเนิดเขาวงกต

อัลกอริทึม Hunt and Kill เป็นเวอร์ชันดัดแปลงของ Recursive Backtracker การปรับเปลี่ยนประกอบด้วยการสแกนอย่างเป็นระบบ (หรือ "การล่า") เพื่อหาเซลล์ใหม่เพื่อดําเนินการต่อจากเมื่อไม่สามารถไปต่อได้ซึ่งตรงข้ามกับการค้นหาแบบเรียกซ้ําที่แท้จริงซึ่งจะกลับไปที่เซลล์ก่อนหน้าบนสแต็กเสมอ

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

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

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

เกี่ยวกับอัลกอริทึม Hunt and Kill

อัลกอริทึม Hunt and Kill เป็นวิธีที่ง่ายแต่มีประสิทธิภาพในการสร้างเขาวงกต มันค่อนข้างคล้ายกับการค้นหาที่เน้นความลึกเป็นอันดับแรก (เช่น อัลกอริธึม Recursive Backtracker) ยกเว้นเมื่อไม่สามารถไปไกลจากตําแหน่งปัจจุบันได้มันจะสแกนอย่างเป็นระบบ (หรือ "ล่า") เหนือเขาวงกตเพื่อค้นหาเซลล์ใหม่เพื่อดําเนินการต่อ อัลกอริทึมประกอบด้วยสองขั้นตอนหลัก: การเดินและการล่าสัตว์

อัลกอริทึม Hunt and Kill ทํางานอย่างไรสําหรับการสร้างเขาวงกต

ขั้นตอนที่ 1: เริ่มต้นที่เซลล์แบบสุ่ม

• ค้นหาเซลล์แบบสุ่มในตารางและทําเครื่องหมายว่าเยี่ยมชมแล้ว

ขั้นตอนที่ 2: ระยะเดิน (Random Walk)

• เลือกเพื่อนบ้านที่ยังไม่ได้เยี่ยมชมแบบสุ่ม
• ย้ายไปยังเพื่อนบ้านนั้น ทําเครื่องหมายว่าเยี่ยมชมแล้ว และแกะสลักเส้นทางระหว่างเซลล์ก่อนหน้าและเซลล์ใหม่
• ทําซ้ําจนกว่าจะไม่มีเพื่อนบ้านที่ยังไม่ได้เยี่ยมชมเหลืออยู่

ขั้นตอนที่ 3: ระยะการล่าสัตว์ (ย้อนกลับผ่านการสแกน)

• สแกนตารางแถวทีละแถว (หรือคอลัมน์ต่อคอลัมน์)
• ค้นหาเซลล์แรกที่ยังไม่ได้เยี่ยมชมซึ่งมีเพื่อนบ้านที่มาเยี่ยมอย่างน้อยหนึ่งคน
• เชื่อมต่อเซลล์นั้นกับเพื่อนบ้านที่มาเยี่ยมเพื่อเดินต่อ
• ทําซ้ําจนกว่าจะมีการเยี่ยมชมเซลล์ทั้งหมด