เครื่องกําเนิดเขาวงกตอัลกอริทึมของวิลสัน

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

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

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

เกี่ยวกับอัลกอริทึมของวิลสัน

อัลกอริทึมของวิลสันในการสร้างต้นไม้ที่ขยายสม่ําเสมอโดยใช้กําแพงแบบสุ่มที่ลบแบบวนซ้ําถูกสร้างขึ้นโดย David Bruce Wilson

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

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

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

ขั้นตอนที่ 1: เริ่มต้น

• เริ่มต้นด้วยตารางที่เต็มไปด้วยผนัง
• กําหนดรายการเซลล์ข้อความที่เป็นไปได้ทั้งหมด

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

• เลือกเซลล์แบบสุ่มและทําเครื่องหมายว่าเยี่ยมชมแล้ว นี่ทําหน้าที่เป็นจุดเริ่มต้นของเขาวงกตระหว่างการสร้าง

ขั้นตอนที่ 3: เดินแบบสุ่มด้วยการลบลูป

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

ขั้นตอนที่ 4: ทําซ้ําจนกว่าจะมีการเยี่ยมชมเซลล์ทั้งหมด:

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