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

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

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

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

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

อัลกอริทึมของเอลเลอร์ได้รับการคิดค้นโดยเดวิด เอลเลอร์

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

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

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

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

ขั้นตอนที่ 1: กำหนดค่าเริ่มต้นให้กับแถวแรก

• กำหนดรหัสชุดที่ไม่ซ้ำกันให้กับแต่ละเซลล์ในแถวนั้น

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

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

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

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

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

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

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

• ดำเนินการประมวลผลทีละแถวต่อไป

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

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

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

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

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