ขั้นตอนวิธีของเอ็ดมอนส์

จากวิกิพีเดีย สารานุกรมเสรี

ในเรื่องทฤษฎีกราฟ ขั้นตอนวิธีของเอ็ดมอนส์เป็นขั้นตอนวิธีที่ใช้ในการหาการแตกกิ่งที่ต่ำที่สุด หรือสูงที่สุด เมื่อจุดยอดถูกเชื่อมด้วยเส้นเชื่อมถ่วงน้ำหนักแบบมีทิศทาง ขั้นตอนวิธีการหาต้นไม้ทอดข้ามต่ำสุดจึงไม่สามารถนำมาใช้ได้ ดังนั้นจึงต้องใช้ขั้นตอนวิธีการหาการแตกกิ่งต่ำสุด ซึ่งขั้นตอนวิธีนี้ถูกเสนอโดย Yoeng-jin Chu และ Tseng-hong Liu ในปี พ.ศ. 2508 และหลังจากนั้น Edmonds ได้เสนอขั้นตอนวิธีเดียวกันในปี พ.ศ. 2510 ในการหาเส้นทางที่ยาวที่สุด เริ่มจากการหาเส้นเชื่อมที่ถ่วงน้ำหนักมากสุด และรอง ๆ มา ตามลำดับ แต่ถ้าเส้นเชื่อมนั้นสร้างวงวนจะถูกลบทิ้ง ในทางกลับกลันระยะทางที่สั้นที่สุดจะสามารถหาได้โดยการหาเส้นเชื่อมถ่วงน้ำหนักต่ำที่สุดก่อน สำหรับกราฟแบบไม่มีทิศทาง เราจะใช้ขั้นตอนวิธีของครูสกาลในการหาต้นไม้แผ่ขยายต่ำสุด

ประสิทธิภาพ[แก้]

ประสิทธิภาพของขั้นตอนวิธีนี้คือ O(EV) อย่างไรก็ตาม ขั้นตอนวิธีของทาร์จานนั้นมีประสิทธิภาพดีกว่า โดยมีประสิทธิภาพอยู่ที่ O(ElogV) สำหรับกราฟเบาบาง และ O(V2) สำหรับกราฟหนาแน่น โดยที่วิธีดังกล่าวนั้นมีประสิทธิภาพที่ใกล้เคียงกับขั้นตอนวิธีของพริม ในการหาต้นไม้แผ่ทั่วที่น้อยที่สุด และในปี พ.ศ.2529 Gabow Galil Spencer และ Tarjan ได้คิดค้นขั้นตอนที่เร็วกว่า โดยมีประสิทธิภาพอยู่ที่ O(E + VlogV)

ขั้นตอนวิธี[แก้]

1. ลบทุกๆเส้นเชื่อมที่มีทิศทางไปยังปมราก
2. เลือกเส้นเชื่อมที่พุ่งเข้าปมในแต่ละปม โดยเลือกเส้นที่มีน้ำหนักน้อยสุด
3. แต่ละวงจรประกอบด้วย
 :* เส้นเชื่อม m ซึ่งเป็นเส้นเชื่อมในวงจรที่มีน้ำหนักน้อยสุด
 :* เชื่อมทุกปมในวงจรด้วยปมเทียม k ซึ่งเป็นปมที่สมมติขึ้นมา
 :* แต่ละเส้นเชื่อม e ที่มีทิศทางสู่ปม k ของกราฟเดิมนั้นจะต้อง
- มีเส้นเชื่อม n เข้าสู่ปม k ในวงจร
- สร้างทางเดินเชื่อมระหว่างเส้นเชื่อม e โดยให้ทางเดินนั้นมีผลรวมน้ำหนักของเส้นเชื่อมน้อยที่สุด ตามสมการ modWeight = weight("e") - ( weight("n") - weight("m") )
4. เพิ่มเส้นเชื่อม e แล้วลบเส้นเชื่อม n ออก

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


เพิ่มเติม[แก้]