ตัวสร้างเขาวงกตอัลกอริธึมของเอลลเลอร์

อัลกอริทึมของ Eller เป็นอัลกอริทึมการสร้างเขาวงกตที่สร้างเขาวงกตที่สมบูรณ์แบบอย่างมีประสิทธิภาพ (เขาวงกตที่ไม่มีลูปและเส้นทางเดียวระหว่างจุดสองจุด) โดยใช้วิธีการแบบแถวต่อแถว มันสร้างเขาวงกตที่คล้ายกับอัลกอริทึมของ Kruskal แต่ทําได้โดยการสร้างเพียงแถวละหนึ่งแถวโดยไม่จําเป็นต้องจัดเก็บเขาวงกตทั้งหมดในหน่วยความจํา นั่นทําให้มีประโยชน์สําหรับการสร้างเขาวงกตขนาดใหญ่มากในระบบที่จํากัดมากและสําหรับการสร้างเนื้อหาตามขั้นตอน

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

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

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

อัลกอริทึมของ Eller ได้รับการแนะนําโดย David Eller

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

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

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

ในทางทฤษฎีสามารถใช้เพื่อสร้างเขาวงกตที่ไม่มีที่สิ้นสุดอย่างไรก็ตามเพื่อให้แน่ใจว่าเขาวงกตที่สร้างขึ้นสามารถแก้ได้จริงจําเป็นต้องเปลี่ยนไปใช้ตรรกะ "แถวสุดท้าย" ในบางจุดเพื่อจบเขาวงกต

ขั้นตอนที่ 1: เริ่มต้นแถวแรก

• กําหนดแต่ละเซลล์ในแถว ID ชุดที่ไม่ซ้ํากัน

ขั้นตอนที่ 2: เข้าร่วมเซลล์ที่อยู่ติดกันในแนวนอน

• สุ่มรวมเซลล์ที่อยู่ติดกันโดยตั้งค่าเป็น ID ที่ตั้งไว้เดียวกัน สิ่งนี้ทําให้มั่นใจได้ว่ามีทางเดินแนวนอน

ขั้นตอนที่ 3: สร้างการเชื่อมต่อแนวตั้งไปยังแถวถัดไป

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

ขั้นตอนที่ 4: ย้ายไปยังแถวถัดไป

• ดําเนินการต่อการเชื่อมต่อแนวตั้งโดยกําหนด ID ชุดเดียวกันให้กับเซลล์ที่เกี่ยวข้องด้านล่าง
• กําหนด ID ชุดใหม่ให้กับเซลล์ที่ไม่ได้กําหนด

ขั้นตอนที่ 5: ทําซ้ําขั้นตอนที่ 2-4 จนกว่าจะถึงแถวสุดท้าย

• ประมวลผลต่อแถว

ขั้นตอนที่ 6: ประมวลผลแถวสุดท้าย

• ตรวจสอบให้แน่ใจว่าเซลล์ทั้งหมดในแถวสุดท้ายอยู่ในชุดเดียวกันโดยการรวมชุดแยกต่างหากที่เหลือ