Miklix

เครื่องกําเนิดเขาวงกตอัลกอริทึมของ 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

แชร์บนบลูสกายแชร์บนเฟสบุ๊คแชร์บน LinkedInแชร์บน Tumblrแชร์บน Xแชร์บน LinkedInปักหมุดบน Pinterest

มิคเคล บัง คริสเตนเซ่น

เกี่ยวกับผู้เขียน

มิคเคล บัง คริสเตนเซ่น
ไมเคิล คือผู้สร้างและเจ้าของเว็บไซต์ miklix.com เขามีประสบการณ์เป็นโปรแกรมเมอร์/นักพัฒนาซอฟต์แวร์คอมพิวเตอร์มืออาชีพมากว่า 20 ปี และปัจจุบันทำงานเต็มเวลาให้กับบริษัทไอทีขนาดใหญ่แห่งหนึ่งในยุโรป เมื่อไม่ได้เขียนบล็อก เขาจะใช้เวลาว่างไปกับความสนใจ งานอดิเรก และกิจกรรมต่างๆ มากมาย ซึ่งในระดับหนึ่งอาจสะท้อนให้เห็นได้จากหัวข้อต่างๆ มากมายที่กล่าวถึงในเว็บไซต์นี้