ตัวสร้างเขาวงกตต้นไม้ที่เติบโต

อัลกอริทึม Growing Tree นั้นน่าสนใจ เพราะสามารถเลียนแบบพฤติกรรมของอัลกอริทึมอื่นๆ ได้หลายแบบ ขึ้นอยู่กับวิธีการเลือกเซลล์ถัดไปในระหว่างการสร้าง การใช้งานในหน้านี้ใช้วิธีการค้นหาแบบกว้าง (breadth-first) ที่คล้ายกับคิว

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

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

เกี่ยวกับอัลกอริทึมต้นไม้เติบโต

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

วิธีการทำงานของอัลกอริทึมต้นไม้เติบโต

ขั้นตอนที่ 1: การเริ่มต้นใช้งาน

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

ขั้นตอนที่ 2: วงวนการสร้างเขาวงกต

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

ขั้นตอนที่ 3: การยุติ

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

กลยุทธ์การเลือกเซลล์ (ความยืดหยุ่นของอัลกอริทึม)

คุณลักษณะเด่นของอัลกอริทึม Growing Tree คือวิธีการเลือกเซลล์ที่จะประมวลผลต่อไป การเลือกนี้ส่งผลกระทบอย่างมากต่อลักษณะของเขาวงกต:

เซลล์ใหม่ล่าสุด (พฤติกรรมคล้ายสแต็ก) – ตัวติดตามย้อนกลับแบบเรียกซ้ำ:

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

เซลล์สุ่ม (อัลกอริทึม Prim แบบสุ่ม):

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

เซลล์ที่เก่าที่สุด (พฤติกรรมคล้ายคิว):

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

แนวทางแบบผสมผสาน:

ผสมผสานกลยุทธ์ต่างๆ สำหรับลักษณะเขาวงกตที่หลากหลาย ตัวอย่างเช่น:

• 90% ใหม่ล่าสุด 10% สุ่ม: ส่วนใหญ่ดูเหมือนเขาวงกตแบบย้อนกลับซ้ำๆ แต่มีทางแยกบ้างเป็นครั้งคราวที่แบ่งทางเดินยาวๆ ออกเป็นส่วนๆ
• ส่วนที่ใหม่ที่สุด 50% และส่วนที่เก่าที่สุด 50%: สร้างความสมดุลระหว่างทางเดินยาวกับพุ่มไม้ที่หนาแน่น

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

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

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