ในเรื่องทฤษฎีกราฟ ขั้นตอนวิธีของเอ็ดมอนส์เป็นขั้นตอนวิธีที่ใช้ในการหาการแตกกิ่งที่ต่ำที่สุด หรือสูงที่สุด เมื่อจุดยอดถูกเชื่อมด้วยเส้นเชื่อมถ่วงน้ำหนักแบบมีทิศทาง ขั้นตอนวิธีการหาต้นไม้ทอดข้ามต่ำสุดจึงไม่สามารถนำมาใช้ได้ ดังนั้นจึงต้องใช้ขั้นตอนวิธีการหาการแตกกิ่งต่ำสุด ซึ่งขั้นตอนวิธีนี้ถูกเสนอโดย 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 ออก
อ้างอิง - AlgoWiki AlgoWiki - Edmond's Algorithm
- การออกแบบและวิเคราะห์อัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
เพิ่มเติม - Implementation of Edmonds's optimum branching algorithm written in C++
- AlgoWiki - Edmond's Algotithm - A public-domain implementation of Edmonds's algorithm written in JAVA
นตอนว, ของเอ, ดมอนส, ในเร, องทฤษฎ, กราฟ, เป, นข, นตอนว, ใช, ในการหาการแตกก, งท, ำท, หร, อส, งท, เม, อจ, ดยอดถ, กเช, อมด, วยเส, นเช, อมถ, วงน, ำหน, กแบบม, ศทาง, นตอนว, การหาต, นไม, ทอดข, ามต, ำส, ดจ, งไม, สามารถนำมาใช, ได, งน, นจ, งต, องใช, นตอนว, การหาการแตกก,. ineruxngthvsdikraf khntxnwithikhxngexdmxnsepnkhntxnwithithiichinkarhakaraetkkingthitathisud hruxsungthisud emuxcudyxdthukechuxmdwyesnechuxmthwngnahnkaebbmithisthang khntxnwithikarhatnimthxdkhamtasudcungimsamarthnamaichid dngnncungtxngichkhntxnwithikarhakaraetkkingtasud sungkhntxnwithinithukesnxody Yoeng jin Chu aela Tseng hong Liu inpi ph s 2508 aelahlngcaknn Edmonds idesnxkhntxnwithiediywkninpi ph s 2510 inkarhaesnthangthiyawthisud erimcakkarhaesnechuxmthithwngnahnkmaksud aelarxng ma tamladb aetthaesnechuxmnnsrangwngwncathuklbthing inthangklbklnrayathangthisnthisudcasamarthhaidodykarhaesnechuxmthwngnahnktathisudkxn sahrbkrafaebbimmithisthang eracaichkhntxnwithikhxngkhruskalinkarhatnimaephkhyaytasud enuxha 1 prasiththiphaph 2 khntxnwithi 3 xangxing 4 ephimetimprasiththiphaph aekikhprasiththiphaphkhxngkhntxnwithinikhux O EV xyangirktam khntxnwithikhxngtharcannnmiprasiththiphaphdikwa odymiprasiththiphaphxyuthi O ElogV sahrbkrafebabang aelaO V2 sahrbkrafhnaaenn odythiwithidngklawnnmiprasiththiphaphthiiklekhiyngkbkhntxnwithikhxngphrim inkarhatnimaephthwthinxythisud aelainpi ph s 2529 Gabow Galil Spencer aela Tarjan idkhidkhnkhntxnthierwkwa odymiprasiththiphaphxyuthi O E VlogV khntxnwithi aekikh1 lbthukesnechuxmthimithisthangipyngpmrak 2 eluxkesnechuxmthiphungekhapminaetlapm odyeluxkesnthiminahnknxysud 3 aetlawngcrprakxbdwy esnechuxm m sungepnesnechuxminwngcrthiminahnknxysud echuxmthukpminwngcrdwypmethiym k sungepnpmthismmtikhunma aetlaesnechuxm e thimithisthangsupm k khxngkrafedimnncatxng miesnechuxm n ekhasupm k inwngcr srangthangedinechuxmrahwangesnechuxm e odyihthangedinnnmiphlrwmnahnkkhxngesnechuxmnxythisud tamsmkar modWeight weight e weight n weight m dd dd 4 ephimesnechuxm e aelwlbesnechuxm n xxkxangxing aekikhAlgoWiki AlgoWiki Edmond s Algorithm karxxkaebbaelawiekhraahxlkxrithum smchay prasiththicutrakul ephimetim aekikhImplementation of Edmonds s optimum branching algorithm written inC AlgoWiki Edmond s Algotithm A public domain implementation of Edmonds s algorithm written inJAVAekhathungcak https th wikipedia org w index php title khntxnwithikhxngexdmxns amp oldid 4703428, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม