ต้นไม้แบบทอดข้ามน้อยสุดแบบยุคลิด

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา
ต้นไม้แบบทอดข้ามเล็กสุดของยูคลิด ที่มีจุด 25 จุด ในระนาบ

ต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด หรือ ต้นไม้แผ่ทั่วที่น้อยที่สุดแบบยุคลิด (อังกฤษ: Euclidean minimum spanning tree) เป็นปัญหาทางทฤษฎีกราฟเกี่ยวกับการหาต้นไม้ทอดข้ามที่น้อยที่สุดบนระนาบแบบยูคลิด หรือก็คือวิธีเชื่อมโยงจุดต่าง ๆ บนระนาบสองมิติ ให้เป็นต้นไม้และมีระยะทางรวมระหว่างจุดต่าง ๆ น้อยที่สุด โดยมองจุดต่าง ๆ เป็นจุดยอดและ ระยะทางระหว่างจุดยอดเป็นเส้นเชื่อม

ขั้นตอนวิธีในการคำนวณต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด[แก้]

ขั้นตอนวิธีที่ง่ายที่สุดในการคำนวณต้นไม้ทอดข้ามที่น้อยที่สุดแบบยุคลิด เมื่อมีจุดทั้งหมด n จุด ถ้ากราฟเป็นกราฟแบบบริบูรณ์ที่มีจุดยอด n จุด จะมีเส้นเชื่อม n (n-1) /2 เส้น คำนวณน้ำหนักของเส้นเชื่อมแต่ละเส้นด้วยการหาระยะห่างระหว่างคู่จุดยอดนั้น ๆ แล้วจึงใช้ขั้นตอนวิธีแบบพื้นฐานในการคำนวณต้นไม้แบบทอดข้ามเล็กสุด (เช่น ขั้นตอนวิธีของพริม (อังกฤษ: Prim's Algorithm) หรือ ขั้นตอนวิธีของครูสกาล (อังกฤษ: Kruskal's algorithm) ) แต่ถ้ากราฟเป็นกราฟใด ๆ ที่มีจุดยอด n จุด และมีเส้นเชื่อม Θ (n2) เส้น เราจะต้องการเวลา Ω (n2) และใช้พื้นที่ Ω (n2) ในการเก็บเส้นเชื่อมทุกเส้นในกราฟ

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

  1. คำนวณสามเหลี่ยมเดอลันเนย์ ซึ่งจะใช้เวลาเพียง O (n log n) และใช้พื้นที่เพียง O (n) เนื่องจากสามเหลี่ยมเดอลันเนย์เป็นกราฟเชิงระนาบ
  2. แบ่งแต่ละเส้นเชื่อมด้วยความยาว
  3. ดำเนินการตามขั้นตอนวิธีบนกราฟนี้ เพื่อหาต้นไม้แบบทอดข้ามเล็กสุด เมื่อมีเส้นเชื่อม O (n) เส้น จะใช้เวลา O (n log n) ในการใช้ขั้นตอนวิธีแบบพื้นฐานในการคำนวณต้นไม้แบบทอดข้ามเล็กสุด เช่น ขั้นตอนวิธีของโบรุฟกา (อังกฤษ: Borůvka's algorithm), ขั้นตอนวิธีของพริม หรือ ขั้นตอนวิธีของครูสกาล

สุดท้ายแล้ว ขั้นตอนวิธีนี้จะใช้เวลาเป็น O (n log n) และใช้พื้นที่เป็น O (n)

ขนาดที่คาดหวัง[แก้]

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

เมื่อ คือ ค่าคงที่ที่ขึ้นกับ ซึ่งเราไม่ทราบค่าที่แน่นอนของค่าคงที่นี้ แต่สามารถประมาณได้จากหลักฐานการทดลอง

อ้างอิง[แก้]

Eppstein, David (1999), "Spanning trees and spanners", ใน Sack, J.-R.; Urrutia, J. (บ.ก.), Handbook of Computational Geometry, Elsevier, pp. 425–461

Mareš, Martin (2004), "Two linear time algorithms for MST on minor closed graph classes" (PDF), Archivum mathematicum, 40 (3): 315–320

ดูเพิ่ม[แก้]