Thuật toán Edmonds–Karp

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong khoa học máy tínhlý thuyết đồ thị, thuật toán Edmonds–Karp là một trường hợp đặc biệt của thuật toán Ford–Fulkerson cho việc tìm luồng cực đại trong mạng. Nó có độ phức tạp tính toán O(V E2). Độ phức tạp tính toán của nó cao hơn của thuật toán gán lại nhãn-lên đầu (O(V3)), nhưng nó thường chạy nhanh hơn trên đồ thị thưa. Thuật toán này được xuất bản lần đầu tiên bởi Yefim (Chaim) Dinic năm 1970[1] và một cách độc lập bởi Jack EdmondsRichard Karp năm 1972[2]. Thuật toán Dinic có thêm một số cải tiến giúp giảm thời gian chạy xuống O(V2E).

Thuật toán[sửa | sửa mã nguồn]

Cấu trúc của thuật toán giống hệt như thuật toán Ford–Fulkerson, chỉ khác cách lựa chọn đường tăng luồng. Đường tăng luồng được chọn là đường tăng có ít cung nhất. Có thể tìm đường tăng này bằng tìm kiếm theo chiều rộng. Có thể chứng minh thời gian chạy của thuật toán là O(VE2) như sau. Thời gian để tìm mỗi đường tăng là O(E). Sau mỗi lần tăng luồng, ít nhất một cung của đồ thị trở thành bão hòa. Mỗi lần một cung trong E trở nên bão hòa (một cung có thể trở thành bão hòa nhiều lần), khoảng cách từ nguồn tới cung bị bão hòa tăng lên ít nhất 1 so với lần cuối cùng nó bị bão hòa trước đó. Khoảng cách này không bao giờ vượt quá V. Một tính chất nữa là khoảng cách từ nguồn tới một đỉnh bất kì là không giảm trong suốt quá trình tăng luồng. Có thể tham khảo một chứng minh đơn giản cho tính chất này ở Cormen et al. (2001). Như vậy số lần tăng luồng là không quá O(VE) và thời gian chạy là O(VE2).

Ví dụ[sửa | sửa mã nguồn]

Xét một mạng gồm bảy đỉnh, đỉnh phát A, đỉnh thu G, và khả năng thông qua được cho trong hình dưới đây:

Edmonds-Karp flow example 0.svg

Trong cặp số f/c trên mỗi cung, f là luồng hiện tại, và c khả năng thông qua. Khả năng thông qua còn dư từ u đến vc_f(u,v)=c(u,v)-f(u,v), hiệu của khả năng thông qua và luồng hiện tại. Nếu luồng từ u đến v là âm, nó làm tăng khả năng thông qua còn dư từ u đến v.

Khả năng thông qua Đường
Mạng thu được
\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
Edmonds-Karp flow example 1.svg
\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
Edmonds-Karp flow example 2.svg
\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
Edmonds-Karp flow example 3.svg
\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
Edmonds-Karp flow example 4.svg

Chú ý là chiều dài đường tăng luồng (màu đỏ) không bao giờ giảm. Đường tăng tìm được luôn là ngắn nhất có thể. Luồng tìm được bằng tổng khả năng thông qua của lát cắt cực tiểu trong đồ thị chia cắt đỉnh phát và đỉnh thu. Có đúng một lát cắt nhỏ nhất trong đồ thị này, chia tập hợp đỉnh thành \{A,B,C,E\}\{D,F,G\}, và có khả năng thông qua

c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\

Ghi chú[sửa | sửa mã nguồn]

  1. ^ Dinic, E. A. (1970). “Algorithm for solution of a problem of maximum flow in a network with power estimation”. Soviet Math. Doklady (Doklady) 11: 1277–1280. 
  2. ^ Edmonds, Jack; Karp, Richard M. (1972). “Theoretical improvements in algorithmic efficiency for network flow problems”. Journal of the ACM (Association for Computing Machinery) 19 (2): 248–264. doi:10.1145/321694.321699. 

Tài liệu tham khảo[sửa | sửa mã nguồn]