Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ในเรื่องทฤษฎีกราฟ ขั้นตอนวิธีของเอ็ดมอนส์เป็นขั้นตอนวิธีที่ใช้ในการหาการแตกกิ่งที่ต่ำที่สุด หรือสูงที่สุด เมื่อจุดยอดถูกเชื่อมด้วยเส้นเชื่อมถ่วงน้ำหนักแบบมีทิศทาง ขั้นตอนวิธีการหาจึงไม่สามารถนำมาใช้ได้ ดังนั้นจึงต้องใช้ขั้นตอนวิธีการหาการแตกกิ่งต่ำสุด ซึ่งขั้นตอนวิธีนี้ถูกเสนอโดย Yoeng-jin Chu และ Tseng-hong Liu ในปี พ.ศ. 2508 และหลังจากนั้น ได้เสนอขั้นตอนวิธีเดียวกันในปี พ.ศ. 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
- [] AlgoWiki - Edmond's Algotithm - A public-domain implementation of Edmonds's algorithm written in JAVA
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
ineruxngthvsdikraf khntxnwithikhxngexdmxnsepnkhntxnwithithiichinkarhakaraetkkingthitathisud hruxsungthisud emuxcudyxdthukechuxmdwyesnechuxmthwngnahnkaebbmithisthang khntxnwithikarhacungimsamarthnamaichid dngnncungtxngichkhntxnwithikarhakaraetkkingtasud sungkhntxnwithinithukesnxody Yoeng jin Chu aela Tseng hong Liu inpi ph s 2508 aelahlngcaknn idesnxkhntxnwithiediywkninpi ph s 2510 inkarhaesnthangthiyawthisud erimcakkarhaesnechuxmthithwngnahnkmaksud aelarxng ma tamladb aetthaesnechuxmnnsrangcathuklbthing inthangklbklnrayathangthisnthisudcasamarthhaidodykarhaesnechuxmthwngnahnktathisudkxn sahrbkrafaebbimmithisthang eracaichkhntxnwithikhxngkhruskalinkarhatnimaephkhyaytasudprasiththiphaphprasiththiphaphkhxngkhntxnwithinikhux 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 khntxnwithi1 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 xxkxangxingAlgoWiki AlgoWiki Edmond s Algorithm lingkesiy karxxkaebbaelawiekhraahxlkxrithum smchay prasiththicutrakul ephimetimImplementation of Edmonds s optimum branching algorithm written in C lingkesiy AlgoWiki Edmond s Algotithm A public domain implementation of Edmonds s algorithm written in JAVA