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

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

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

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

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

อัลกอริทึมของวิลสันสำหรับการสร้างต้นไม้แผ่คลุมสม่ำเสมอโดยใช้ผนังสุ่มที่ลบวงวนออกนั้น คิดค้นโดยเดวิด บรูซ วิลสัน

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

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

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

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

• เริ่มต้นด้วยตารางที่เต็มไปด้วยกำแพง
• กำหนดรายการเซลล์ทางผ่านที่เป็นไปได้ทั้งหมด

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

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

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

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

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

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

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

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

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