ผู้ใช้:Oatawa1/กระบะทราย

บทนำ

ในด้านวิทยาศาสตร์คอมพิวเตอร์ และ ทฤษฎีกราฟ ขั้นตอนวิธีของเอ็ดมอนด์ คาป(อังกฤษ: Edmonds-Karp algorithm) เป็นขั้นตอนวิธีการแก้ปัญหาการไหลมากสุด (อังกฤษ: Maximum flow) ใน ระบบเครือข่ายการไหล (อังกฤษ: Flow network) โดยการนำเอาวิธีการของฟอร์ด-ฟูเกอร์สัน(อังกฤษ: Ford-Fulkerson method) มาใช้ โดยทำงานได้ในระยะเวลา O(V E^2) หากเปรียบเทียบกันในเชิงเส้นแล้วจะช้ากว่า (อังกฤษ: Relabel-to-front algorithm) ซึ่งทำงานในเวลา O(V^3) แต่ในความเป็นจริงจะพบว่า ขั้นตอนวิธีของเอ็ดมอนด์-คาป จะทำงานได้ดีกว่าหากเป็น กราฟไม่หนาแน่น(อังกฤษ: sparse graphs) ขั้นตอนวิธีแก้ปัญหานี้ถูกเปิดเผยครั้งแรกในปี 1970 โดยนายไดนิก(อังกฤษ: Yefim (Chaim) Dinic) นักวิทยาศาสตร์ชาวรัสเซีย โดยมีชื่อว่าขั้นตอนวิธีของไดนิก(อังกฤษ: Dinic's algorithm)ซึ่งทำงานได้ในเวลา O(V^2 E) 2 ปีต่อมา(1972) นาย แจ๊ค เอ็ดมอนด์(อังกฤษ: Jack Edmonds) และ นาย ริชาร์ด คาป(อังกฤษ: Richard Karp) ได้เสนอวิธีแก้ปัญหานี้ในรูปแบบที่แตกต่างกันออกไปซึ่งถูกเรียกว่า ขั้นตอนวิธีของเอ็ดมอนด์-คาป

ขั้นตอนวิธี

ขั้นตอนวิธีนี้เหมือนขั้นตอนวิธีของฟอร์ด-ฟูเกอร์สัน ยกเว้นในส่วนของการค้นหาวิถีเพิ่มพูน(อังกฤษ: Augmenting path) การค้นหาวิถีเพิ่มพูนในขั้นตอนวิธีนี้นั้น เราจะหาจากวิถีสั่นสุดที่ยังเหลือที่ว่างให้ไหลไปได้ ด้วยการค้นทางกว้าง(lang-en|: Breadth-first search}}) โดยให้แต่ละวิถีมีน้ำหนักของมันเอง โดยจะใช้เวลาทั้งหมดประมาณ O(V E^2) ซึ่งคำนวณจากการที่สามารถหาวิถีเพิ่มพูนในแต่ละครั้งได้ในเวลา O(E) ซึ่งในการทำงานแต่ละรอบนั้นจะต้องมีวิถีที่อิ่มตัว(อังกฤษ: Saturated edge) เกิดขึ้นอีกอย่างน้อย 1 วิถี จากขั้นตอนวิธีดังกล่าวจะส่งผลให้ระยะทางจากต้นกำเนิดถึงวิถีอิ่มตัวล่าสุดจะต้องมากกว่าเดิมเสมอ ขากขั้นตอนวิธีดังกล่าวเราพบว่าระยะทางของวิถีเพิ่มพูนสั้นสุดนั้นเติบโตขึ้นเป็นลำดับทางเดียว โดยอ้างอิงจากบทพิสูจน์ดังนี้

รหัสเทียม

สามารถดูรายละเอียดเชิงลึกได้ที่ ขั้นตอนวิธีของฟอร์ด-ฟูเกอร์สัน(อังกฤษ: Ford-Fulkerson algorithm) 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 และ ความจุ ดังแสดงตามภาพด้านล่าง

ในทุกคู่ $f/c$ ที่ถูกเขียนบนวิถี $f$ และ $c$ คือ อัตราการไหลในปัจจุบัน และ ความจุของวิถีนั้น ตามลำดับ ค่าความจุที่เหลืออยู่จาก $u$ ไป $v$ คือ $c_{f}(u,v)=c(u,v)-f(u,v)$ ส่วนต่างของค่าความจุของวิถีนั้นและอัตราการไหลที่ไหลผ่านวิถีดังกล่าว

ความจุ	วิถี
	ผลลัพธ์ในระบบ
$\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=$ $\min(3-0,2-0,1-0)=$ $\min(3,2,1)=1$	$A,D,E,G$
$\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,6-0,9-0)=$ $\min(2,6,9)=2$	$A,D,F,G$
$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-0,4-0,1-0,6-2,9-2)=$ $\min(3,4,1,4,7)=1$	$A,B,C,D,F,G$
$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,4-1,2-0,0--1,6-3,9-3)=$ $\min(2,3,2,1,3,6)=1$	$A,B,C,E,D,F,G$

อ้างอิง

1. E. A. Dinic (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Soviet Math. Doklady (Doklady) 11: 1277–1280.
2. Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2): 248–264. doi:10.1145/321694.321699.
3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26.2". Introduction to Algorithms (second ed.). MIT Press and McGraw–Hill. pp. 660–663. ISBN 0-262-53196-8.
4. Algorithms and Complexity (see pages 63–69). http://www.cis.upenn.edu/~wilf/AlgComp3.html