Loading AI tools
จากวิกิพีเดีย สารานุกรมเสรี
ในด้านวิทยาศาสตร์คอมพิวเตอร์ และ ทฤษฎีกราฟ ขั้นตอนวิธีของเอ็ดมอนด์-คาป (อังกฤษ: Edmonds-Karp algorithm) เป็นขั้นตอนวิธีการแก้ปัญหาการไหลมากสุด (อังกฤษ: Maximum flow) ใน ระบบเครือข่ายการไหล (อังกฤษ: Flow network) โดยการนำเอาวิธีการของฟอร์ด-ฟูเกอร์สัน (อังกฤษ: Ford-Fulkerson method) มาใช้ โดยทำงานได้ในระยะเวลา หากเปรียบเทียบกันในเชิงเส้นแล้วจะช้ากว่า (อังกฤษ: Relabel-to-front algorithm) ซึ่งทำงานในเวลา แต่ในความเป็นจริงจะพบว่า ขั้นตอนวิธีของเอ็ดมอนด์-คาป จะทำงานได้ดีกว่าหากเป็น กราฟไม่หนาแน่น (อังกฤษ: sparse graphs) ขั้นตอนวิธีแก้ปัญหานี้ถูกเปิดเผยครั้งแรกในปี ค.ศ. 1970 โดยนายดีนิทซ์ (Yefim Dinitz) นักวิทยาศาสตร์ชาวยิว (อดีตเป็นชาวรัสเซีย) โดยมีชื่อว่าขั้นตอนวิธีของดีนิซ (อังกฤษ: Dinic's algorithm) ซึ่งทำงานได้ในเวลา 2 ปีต่อมา คือปี ค.ศ. 1972 แจ๊ค เอ็ดมอนด์ (Jack Edmonds) กับริชาร์ด คาป (Richard Karp) ได้เสนอวิธีแก้ปัญหานี้ในรูปแบบที่แตกต่างกันออกไปซึ่งถูกเรียกว่า ขั้นตอนวิธีของเอ็ดมอนด์-คาป
ขั้นตอนวิธีนี้เหมือนขั้นตอนวิธีของฟอร์ด-ฟูเกอร์สัน ยกเว้นในส่วนของการค้นหาวิถีเพิ่มพูน (อังกฤษ: Augmenting path) การค้นหาวิถีเพิ่มพูนในขั้นตอนวิธีนี้นั้น เราจะหาจากวิถีสั่นสุดที่ยังเหลือที่ว่างให้ไหลไปได้ด้วยการค้นทางกว้าง โดยให้แต่ละวิถีมีน้ำหนักของมันเอง โดยจะใช้เวลาทั้งหมดประมาณ ซึ่งคำนวณจากการที่สามารถหาวิถีเพิ่มพูนในแต่ละครั้งได้ในเวลา ซึ่งในการทำงานแต่ละรอบนั้นจะต้องมีวิถีที่อิ่มตัว (Saturated edge) เกิดขึ้นอีกอย่างน้อย 1 วิถี จากขั้นตอนวิธีดังกล่าวจะส่งผลให้ระยะทางจากต้นกำเนิดถึงวิถีอิ่มตัวล่าสุดจะต้องมากกว่าเดิมเสมอ จากขั้นตอนวิธีดังกล่าวเราพบว่าระยะทางของวิถีเพิ่มพูนสั้นสุดนั้นเติบโตขึ้นเป็นลำดับทางเดียว โดยอ้างอิงจากบทพิสูจน์ดังนี้
สามารถดูรายละเอียดเชิงลึกได้ที่ขั้นตอนวิธีของฟอร์ด-ฟูเกอร์สัน
algorithm EdmondsKarp
ข้อมูลนำเข้า: C[1..n, 1..n] (เมตริกความจุ) E[1..n, 1..?] (รายการผมเพื่อนบ้าน) s (ก๊อก) t (อ่าง) ข้อมูลนำออก: f (ค่าอัตราการไหลสูงสุด) F (เมตริกซึ่งแสดงค่าอัตราการไหลสูงสุดในแต่ละวิถึ) f := 0 (กำหนดค่าเริ่มต้นให้อัตราการไหล) F := array (1..n, 1..n) (ค่าความจุที่เหลือ จาก u ไป v หรือ C[u,v] - F[u,v]) forever m, P := BreadthFirstSearch (C, E, s, t) if m = 0 break f := f + m (การค้นแบบBacktrack และ สร้างวิถีการไหล) v := t while v ≠ s u := P[v] F[u,v] := F[u,v] + m F[v,u] := F[v,u] - m v := u return (f, F)
ขั้นตอนวิธี ค้นทางกว้าง (BreadthFirstSearch) ข้อมูลนำเข้า: C, E, s, t 'ข้อมูลนำออก: M[t] (ความจุของวิถีที่พบ) P (ตารางบรรพบุรุษ) P := array (1..n) for u in 1..n P[u] := -1 P[s] := -2 (ตรวจสอบว่าก๊อกนี้ไม่ถูกค้นพบซ้ำ) M := array (1..n) (ค่าความจุระหว่างวิถีที่ถูกค้นพบกับปม) M[s] := ∞ Q := queue () Q.push (s) while Q.size () > 0 u := Q.pop () for v in E[u] (ถ้ายังมีความจุให้ไหลได้ และ v ยังไม่เคยถูกค้นพบมาก่อน) if C[u,v] - F[u,v] > 0 and P[v] = -1 P[v] := u M[v] := min (M[u], C[u,v] - F[u,v]) if v ≠ t Q.push (v) else return M[t], P return 0, P
กำหนดให้เครือข่ายมี 7 ปม โดยมีจุดเริ่มต้นก๊อก A และ จบที่อ่าง G และ ความจุ ดังแสดงตามภาพด้านล่าง
ในทุกคู่ ที่ถูกเขียนบนวิถี และ คือ อัตราการไหลในปัจจุบัน และ ความจุของวิถีนั้น ตามลำดับ ค่าความจุที่เหลืออยู่จาก ไป คือ ส่วนต่างของค่าความจุของวิถีนั้นและอัตราการไหลที่ไหลผ่านวิถีดังกล่าว
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.