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

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

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

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

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

เกี่ยวกับอัลกอริทึมการล่าและสังหาร

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

วิธีการทำงานของอัลกอริทึมการล่าและสังหารในการสร้างเขาวงกต

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

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

ขั้นตอนที่ 2: ขั้นตอนการเดิน (การเดินแบบสุ่ม)

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

ขั้นตอนที่ 3: ขั้นตอนการล่า (การติดตามย้อนกลับโดยการสแกน)

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

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

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

• เครื่องกําเนิดเขาวงกต Backtracker แบบเรียกซ้ํา
• ตัวสร้างเขาวงกตอัลกอริธึมของเอลลเลอร์
• เครื่องกําเนิดเขาวงกตอัลกอริทึมของวิลสัน