เครื่องกําเนิดเขาวงกตอัลกอริทึมของ Kruskal
ที่ตีพิมพ์: 16 กุมภาพันธ์ 2025 เวลา 18 นาฬิกา 01 นาที 21 วินาที UTC
เครื่องกําเนิดเขาวงกตโดยใช้อัลกอริทึมของ Kruskal เพื่อสร้างเขาวงกตที่สมบูรณ์แบบ อัลกอริทึมนี้มีแนวโน้มที่จะสร้างเขาวงกตที่มีทางเดินยาวปานกลางและทางตันจํานวนมากรวมถึงวิธีแก้ปัญหาที่ค่อนข้างตรงKruskal's Algorithm Maze Generator
อัลกอริทึมของ Kruskal เป็นอัลกอริทึมต้นไม้สแปนนิ่งขั้นต่ําที่สามารถปรับให้เข้ากับการสร้างเขาวงกตได้ มีประสิทธิภาพโดยเฉพาะอย่างยิ่งในการสร้างเขาวงกตที่สมบูรณ์แบบ อีกทางเลือกหนึ่งสําหรับอัลกอริทึมของ Kruskal คืออัลกอริทึมของ Prim ซึ่งเป็นอัลกอริทึมต้นไม้สแปนนิ่งขั้นต่ํา แต่เนื่องจากพวกเขาสร้างเขาวงกตที่เหมือนกันและ Kruskal ทํางานเร็วขึ้นฉันจึงไม่ได้รบกวนการใช้ Prim's
เขาวงกตที่สมบูรณ์แบบคือเขาวงกตที่มีเส้นทางเดียวจากจุดใดก็ได้ในเขาวงกตไปยังจุดใดก็ได้ นั่นหมายความว่าคุณไม่สามารถวนไปวนมาได้ แต่บ่อยครั้งที่คุณจะเจอทางตัน ซึ่งบังคับให้คุณต้องหันหลังกลับและเดินกลับไป
แผนที่เขาวงกตที่สร้างขึ้นที่นี่มีเวอร์ชันเริ่มต้นโดยไม่มีตำแหน่งเริ่มต้นและจุดสิ้นสุด ดังนั้นคุณจึงตัดสินใจเองได้: จะมีทางออกจากจุดใดก็ได้ในเขาวงกตไปยังจุดอื่นๆ หากคุณต้องการแรงบันดาลใจ คุณสามารถเปิดใช้งานตำแหน่งเริ่มต้นและจุดสิ้นสุดที่แนะนำได้ และดูทางออกระหว่างทั้งสองตำแหน่งได้ด้วย
เกี่ยวกับอัลกอริทึมของ Kruskal
อัลกอริทึมของ Kruskal ถูกสร้างขึ้นโดย Joseph Bernard Kruskal, Jr. นักคณิตศาสตร์ นักสถิติ และนักวิทยาศาสตร์คอมพิวเตอร์ชาวอเมริกัน เขาอธิบายอัลกอริทึมครั้งแรกในปี 1956 ในบทความของเขา "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem"
อัลกอริทึมได้รับการออกแบบมาเพื่อค้นหาต้นไม้สแปนซ์ขั้นต่ํา (MST) ของกราฟ เพื่อให้มั่นใจว่าจุดยอดทั้งหมดเชื่อมต่อกับน้ําหนักขอบรวมที่น้อยที่สุดเท่าที่จะเป็นไปได้ในขณะที่หลีกเลี่ยงวัฏจักร
อัลกอริทึมของ Kruskal ทํางานอย่างไรสําหรับการสร้างเขาวงกต
ขั้นตอนที่ 1: เริ่มต้น
- ถือว่าแต่ละเซลล์ในเขาวงกตเป็นชุดแยกต่างหาก (ส่วนประกอบเฉพาะ)
- แสดงรายการผนังทั้งหมดระหว่างเซลล์ที่อยู่ติดกันเป็นขอบที่เป็นไปได้
ขั้นตอนที่ 2: จัดเรียงผนัง
- สับเปลี่ยนหรือสุ่มเรียงลําดับกําแพง หากใช้เป็นอัลกอริทึมของ Kruskal ที่แท้จริง ให้จัดเรียงกําแพงตามลําดับแบบสุ่ม (เนื่องจากการสร้างเขาวงกตไม่ต้องการน้ําหนัก)
ขั้นตอนที่ 3: ผนังกระบวนการ
- ทําซ้ําผ่านกําแพงที่สับเปลี่ยน
- หากเซลล์สองเซลล์ที่หารด้วยผนังเป็นของชุดที่แตกต่างกัน (เช่น ยังไม่ได้เชื่อมต่อในเขาวงกต) ให้ถอดผนังออกและรวมชุด
- หากอยู่ในชุดเดียวกันอยู่แล้ว ให้ข้ามกําแพง (เพื่อหลีกเลี่ยงวงจร)
ขั้นตอนที่ 4: ดําเนินการต่อจนกว่าจะเสร็จสิ้น
- ทําซ้ําขั้นตอนนี้จนกว่าเซลล์ทั้งหมดจะเชื่อมต่อกัน
- ในตอนท้าย ทุกเซลล์จะเชื่อมต่อกับเซลล์อื่นๆ โดยไม่มีลูปหรือส่วนที่แยกจากกัน
เนื่องจากอัลกอริทึมของ Kruskal อาศัยการรวมชุด จึงสามารถปรับให้เหมาะสมได้โดยใช้อัลกอริทึม Union-Find ซึ่งเป็นวิธีที่มีประสิทธิภาพในการติดตามเซลล์ที่เชื่อมต่อระหว่างการสร้างเขาวงกต คุณสามารถดูการใช้งาน PHP ของฉันของอัลกอริทึม Union-Find ได้ที่นี่: Disjoint Set (Union-Find Algorithm) ใน PHP