Tiểu luận Thiết kế và phân tích thuật toán: luồng cực đại - pdf 14

Download miễn phí Tiểu luận Thiết kế và phân tích thuật toán: luồng cực đại



Mục lục
26. Luồng Cực Đại 2
26.1 Các mạng luồng 3
26.2. Phương pháp Ford - Fulkerson 11
26.3. So khớp hai nhánh cực đại 27
26.4. Các thuật toán đầy luồng trước 33
26.5. Thuật toán nâng tới trước 45
 



Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung:

các cạnh trong mạng thặng dư bao gồm tất cả các cạnh (u, v) của G’ sao cho c(u, v) - [u, v] ≠ 0. Do đó, thời gian để tìm một lộ trình trong một mạng thặng dư là O(E’) = O(E) nếu ta dùng thuật toán tìm kiếm độ sâu đầu tiên hay tìm kiếm độ rộng đầu tiên. Như vậy, mỗi lần lặp lại của vòng lặp while sẽ mất O(E) thời gian, khiến tổng thời gian thực hiện của FORD-FULKERSON trở thành O(E|ƒ*|).
Khi các dung lượng là tích phân và giá trị luồng tối ưu |ƒ*| nhỏ, thời gian thực hiện của thuật toán Ford-Fulkerson tỏ ra thích hợp. Hình 26.7(a) có nêu một ví dụ về nội dung có thể xảy ra trên một mạng luồng đơn giản mà |ƒ*| là lớn. Một luồng cực đại mạng này có giá trị 2,000,000: 1,000,000 đơn vị của luồng băng ngang lộ trình s → u → t, và một 1,000,000 đơn vị khác băng ngang lộ trình s → v → t. Nếu lộ trình tăng cường đầu tiên mà FORD-FULKERSON tìm thấy là s → u → v → t, xem Hình 26.7(a), luồng có giá trị 1 sau lần lặp lại đầu tiên. Mạng thặng dư kết quả được nêu trong Hình 26.7(b). Nếu lần lặp thứ hai tìm thấy lộ trình tăng cường s → v → u → t, như đã nêu trong hình 26.7(b), thì luồng sẽ giá trị 2. Hình 26.7(c) nêu mạng thặng dư kết quả. Ta có thể tiếp tục chọn lộ trình tăng cường s → u → v → t trong các lần lặp lại đánh số lẻ và lộ trình tăng cường s → u → v → t trong các lần lặp lại đánh số chẵn. Ta sẽ thực hiện một tổng 2,000,000 lần tăng cường, mỗi lần chỉ tăng giá trị luồng lên 1 đơn vị.
Có thể cải thiện cận trên FORD-FULKERSON nếu ta thực thi phép tính của lộ trình tăng cường p trong dòng 4 bằng một thuật toán tìm kiếm độ rộng đầu tiên, nghĩa là, nếu lộ trình tăng cường là một lộ trình ngắn nhất từ s đến t trong mạng thặng dư, ở đó mỗi cạnh có một khoảng cách đơn vị (trọng số). Ta gọi phương pháp Ford-Fulkerson đó là đã thực thi thuật toán Edmonds-Karp. Giờ đây ta chứng minh thuật toán Edmonds-Karp chạy trong O(VE2) thời gian.
Phần phân tích tuỳ từng trường hợp vào các khoảng cách đến các đỉnh trong mạng thặng dư . Bổ đề dưới đây sử dụng hệ ký hiệu (u, v) với khoảng cách lộ trình ngắn nhất từ u đến v trong ở đó mỗi cạnh có khoảng cách đơn vị.
Bổ đề 26.8
Nếu thuật toán Edmonds-Karp chạy trên mạng luồng G = (V, E) với nguồn s và bồn t, thì với tất cả các đỉnh v Î V - {s, t}, khoảng cách lộ trình ngắn nhất (s, t) trong mạng thặng dư sẽ tăng đơn điệu với mỗi phép tăng cường luồng.
Chứng minh Vì sự mâu thuẫn, ta giả sữ với một đỉnh v Î V - {s, t}, ta có một phép tăng cường luồng khiến (s, v) giảm. Cho ƒ’ là luồng ngay trước phép tăng cường và cho ƒ là luồng ngay sau đó. Thì,
(s, v) < (s, v)
Ta có thể mặc nhận mà không làm mất tính tổng quát rằng (s, v) ≤ (s, u) với tất cả các đỉnh u Î V - {s, t} sao cho (s, u) < (s, u). Tương đương, ta có thể mặc nhận rằng với tất cả các đỉnh u Î V - {s, t},
(s, u) < (s, v) hàm ý (s, u) ≤ (s, u) (26.7)
Giờ đây ta lấy một lộ trình ngắn nhất p’ trong có dạng s u → v và xét đỉnh u đứng trước v trên lộ trình này. Ta phải có (s, u) = (s, v) -1 theo Hệ luận 26.2, bởi (u, v) là một cạnh trên p’, chính là một lộ trình ngắn nhất từ s đến v. Do đó, theo giả thuyết (26.7) của chúng ta,
(s, u) ≤ (s, u) .
Như vậy, với các đỉnh v và u được thiết lập, ta có thể xát luồng mạng ƒ từ u đến v trước khi phép tăng cường của luồng trong . Nếu ƒ[u, v] < c(u, v), thì ta có
(s, v) ≤ (s, u) + 1 (theo Bổ đề 26.3)
≤ (s, u) + 1
= (s, v),
mâu thuẫn với giả thuyết của chúng ta rằng phép tăng cường luồng giảm khoảng cách từ s đến v.
Như vậy, ta phải có ƒ[u, v] = c(u, v), có nghĩa là (u, v) . Giờ đây, lộ trình tăng cường p đã được chọn trong để tạo ra phải chứa cạnh (u, v) theo hướng từ v đến u, bởi (u, v)Î (theo giả thuyết) và (u, v) như ta vừa nêu. Nghĩa là, việc tăng cường luồng dọc theo lộ trình p đẩy luồng trở lại dọc theo (u, v) và v xuất hiện trước u trên p. Bởi p là một lộ trình ngắn nhất từ s đến t, các lộ trình con của nó là các lộ trình ngắn nhất (Bổ đề 26.1) và như vậy ta có (s, u) = (s, v) + 1. Bởi vậy,
(s, v) = (s, u) - 1
≤ (s, u) - 1
= (s, v) - 2
< (s, v),
mâu thuẫn với giả thuyết ban đầu của chúng ta.
Định lý dưới đây định cận số lần lặp lại của thuật toán Edmonds-Karp.
Định lý 26.9
Nếu thuật toán Edmonds-Karp chạy trên một mạng luồng G = (V, E) với nguồn s và bồn t, thì tổng số lần tăng cường luồng mà thuật toán thực hiện sẽ tối đa là O(VE).
Chứng minh Ta nói một cạnh (u, v) trong một mạng thặng dư là tới hạn trên một lộ trình tăng cường p nếu dung lượng thặng dư của p là dung lượng thăng dư của (u, v), nghĩa là, nếu (p) = (u, v). Sau khi đã tăng cường luồng dọc theo một lộ trình tăng cường, mọi cạnh tới hạn trên lộ trình đều sẽ biến mất khỏi mạng thặng dư. Hơn nữa, ít nhất một cạnh trên bất kỳ lộ trình tăng cường nào đều phải tới hạn.
Cho u và v là các đỉnh trong V được liên thông bởi một cạnh trong E. (u, v) có thể là một cạnh tới hạn bao nhiêu lần trong khi thi hành thuật toán Edmonds-Karp? Bởi các lộ trình tăng cường là các lộ trình ngắn nhất, khi (u, v) tới hạn đầu tiên, nên ta có
(s, v) = (s, u) + 1 .
Một khi luồng được tăng cường, cạnh (u, v) biến mất khỏi mạng thặng dư. Nó không thể tái xuất hiện về sau trên một lộ trình tăng cường khác cho đến sau khi luồng mạng từ u đến v giảm và đều này chỉ xảy ra nếu (v, u) xuất hiện trên một lộ trình tăng cường. Nếu ’ là luồng trong G khi sự kiện này xảy ra, thì ta có
(s, u) = (s, v) + 1
Bởi (s, v) ≤ (s, u) theo Bổ đề 26.8, ta có
(s, u) = (s, v) + 1
(s, v) + 1
= (s, u) + 2.
Kết quả là, từ lúc mà (u, v) trở thành tới hạn đến lúc đó nó trở thành tới hạn sau đó, khoảng cách của u từ nguồn sẽ gia tăng ít nhất 2. Thoạt đầu khoảng cách của u từ nguồn ít nhất là 1 và cho đến khi nó trở thành bất khả dụng từ nguồn, nếu như có thì khoảng cách của nó tối đa là |V| - 2. Như vậy, (u, v) có thể trở thành tới hạn tối đa O(V) lần. Bởi có O(E) cặp đỉnh có thể có một cạnh giữa chúng trong một đồ thị thặng dư, nên tổng các cạnh tới hạn trong nguyên cả tiến trình thi hành thuật toán Edmonds-Karp là O(E). Mỗi lộ trình tăng cường có ít nhất một cạnh tới hạn và do đó định lý đứng vững.
Bởi mỗi lần lặp lại của FORD-FULKERSON có thể được thực thi trong O(E) Thời gian khi thuật toán tìm kiếm độ rộng đầu tiên tìm thấy lộ trình tăng cường, nên tổng thời gian thực hiện của thuật toán Edmonds-Karp là O(VE2). Thuật toán trong đoạn 26.4 cho ta phương pháp để đạt được một thời gian thực hiện O(V2E), lập thành cơ sở cho thuật toán O(V3) thời gian của Đoạn 26.5.
Bài tập
26.2-1
Trong Hình 26.1(b), nêu luồng qua phần cắt ({s, v2, v4} , {v1, v3, t})? Đâu là dung lượng của phần cắt này?
26.2-2
Nêu tiến trình thi hành thuật toán Edmonds-Karp trên mạng luồng của Hình 26.1(a).
26.2-3
Trong ví dụ của Hình 26.6, nêu phần cắt cực tiểu tương ứng với luồng cực đại đã nêu? Trong số các lộ trình tăng cường xuất hiện trong ví dụ, nêu hai lộ trình khử luồng đã được chuyển đi trước đó?
26.2-4
Chứng minh với bất kỳ cặp đỉnh u và v bất kỳ dung lượng và hàm luồng c và ƒ, ta có (u, v) ...
Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status