Bài toán luồng cực đại

Giáo dục đại cương,Toán rời rạc
  Đánh giá    Viết đánh giá
 12      381      0
Phí: Tải Miễn phí
Mã tài liệu
ywvntq
Danh mục
Giáo dục đại cương,Toán rời rạc
Thể loại
Bài toán luồng cực đại, bai toan tang luong cuc dai, thuat toan tang luong, thuat toan Ford-Fulkerson
Ngày đăng
3/1/2014
Loại file
pdf
Số trang
10
Dung lượng
0.34 M
Lần xem
381
Lần tải
12
  DOWNLOAD

Bài toán luồng cực đại và cách giải

HƯỚNG DẪN DOWNLOAD TÀI LIỆU

Bước 1:Tại trang tài liệu thuvienmienphi bạn muốn tải, click vào nút Download màu xanh lá cây ở phía trên.
Bước 2: Tại liên kết tải về, bạn chọn liên kết để tải File về máy tính. Tại đây sẽ có lựa chọn tải File được lưu trên thuvienmienphi
Bước 3: Một thông báo xuất hiện ở phía cuối trình duyệt, hỏi bạn muốn lưu . - Nếu click vào Save, file sẽ được lưu về máy (Quá trình tải file nhanh hay chậm phụ thuộc vào đường truyền internet, dung lượng file bạn muốn tải)
Có nhiều phần mềm hỗ trợ việc download file về máy tính với tốc độ tải file nhanh như: Internet Download Manager (IDM), Free Download Manager, ... Tùy vào sở thích của từng người mà người dùng chọn lựa phần mềm hỗ trợ download cho máy tính của mình  

NỘI DUNG TÀI LIỆU

Bài toán luồng cực đại

 

HÌNH ẢNH DEMO
Tài liệu Bài toán luồng cực đại slide 1

Tài liệu Bài toán luồng cực đại slide 2

Tài liệu Bài toán luồng cực đại slide 3

Tài liệu Bài toán luồng cực đại slide 4

Tài liệu Bài toán luồng cực đại slide 5


Chỉ xem 5 trang đầu, hãy download Miễn Phí về để xem toàn bộ
PHẦN
PHỤ
LỤC
Phụ lục 2
Bài toán luồng cực đại
Cho mạng G=(V,E). Hãy tìm luồng f* trong mạng với giá trị luồng val(f*) là
lớn nhất. Luồng như vậy ta sẽ gọi là luồng cực đại trong mạng.
Bài toán như vậy có thể xuất hiện trong rất nhiều ứng dụng thực tế. Chẳng hạn
khi cần xác định cường độ lớn nhất của dòng vận tải giữa hai nút của một bản đồ giao
thông. Trong thí dụ này lời giải của bài toán luồng cực đại sẽ chỉ cho ta các đoạn
đường xe đông nhất và chúng tạo thành chỗ hẹp tương ứng của dòng giao thông xét
theo hai nút đã chọn. Một thí dụ khác là nếu xét đồ thị tương ứng với một hệ thống
đường ống dẫn dầu, trong đó các ống tương ứng với các cung, điểm phát có thể coi là
tàu chở dầu, điểm thu là bể chứa, còn các điểm nối giữa các ống là các nút của đồ thị,
khả năng thông qua của các cung tương ứng với tiết diện các ống. Cần phải tìm luồng
dầu lớn nhất có thể bơm dầu từ tàu chở dầu vào bể chứa.
Định lý: Các mệnh đề dưới đây là tương đương:
(i) f là luồng cực đại trong mạng.
(ii) Không tìm được đường tăng luồng f.
(iii) Val(f)=c(X,X*) với một lát cắt (X,X*) nào đó.
(Ta gọi lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của mạng ra thành hai tập X
và X*=V\X, trong đó sX và t  X*.)
Định lý trên là cơ sở để xây dựng thuật toán lặp sau đây để tìm luồng cực đại
trong mạng: Bắt đầu từ luồng trên tất cả các cung bằng 0 (ta sẽ gọi luồng như vậy là
luồng không), và
lặp lại bước lặp sau đây cho đến khi thu được luồng mà đối với nó
không còn đường tăng:
Bước lặp tăng luồng (Ford – Fulkerson): Tìm đường tăng P đối với luồng hiện có, tăng
luồng dọc theo đường
P.
Khi đã có luồng cực đại, lát cắt hẹp nhất có thể tìm theo thủ tục mô tả trong
việc chứng minh định lý trên. Thuật toán Ford-Fulkerson được mô tả trong thủ tục sau
đây:
Procedure Luongcucdai;
Begin
Stop := false;
While not Stop do
If then
Else
Stop := true;
End;
158
Để tìm đường tăng luồng trong G(f) có thể sử dụng thuật toán tìm kiếm theo
chiều rộng (hay tìm kiếm theo chiều sâu), bắt đầu từ đỉnh s trong đó không cần xây
dựng tường minh đồ thị G(f). Ford-Fulkerson đề nghị thuật toán gán nhãn chi tiết sau
đây để giải bài toán luồng cực đại trong mạng. Thuật toán bắt đầu từ luồng chấp nhận
được nào đó trong mạng (có thể bắt đầu từ luồng không) , sau đó ta sẽ tăng luồng bằng
cách tìm các đường tăng luồng. Để tìm đường tăng luồng ta sẽ áp dụng phương pháp
gán nhãn cho các đỉnh. Mỗi đỉnh trong quá trình thực hiện thuật toán sẽ ở một trong ba
trạng thái: chưa có nhãn, có nhãn chưa xét, có nhãn đã xét. Nhãn của một đỉnh v gồm
hai phần và có một trong hai dạng sau : [p(v) ,(v)] hoặc [p(v),(v)]. Phần thứ nhất
+p(v) (-p(v)) chỉ ra là cần tăng giảm luồng theo cung (p(v),v)( cung (v,p(v)) còn phần
thứ hai (v) chỉ ra lượng lớn nhất có thể tăng hoặc giảm luồng theo cung này. Đầu tiên
chỉ có đỉnh s được khởi tạo nhãn và nhãn của nó là chưa xét, còn tất cả các đỉnh còn lại
đều chưa có nhãn. Từ s ta gán nhãn cho tất cả các đỉnh kề với nó và nhãn của đỉnh s sẽ
trở thành đã xét. Tiếp theo, từ một đỉnh v có nhãn chưa xét ta lại gán nhãn cho tất cả
các đỉnh chưa có nhãn kề với nó và nhãn của đỉnh v trở thành đã xét. Quá trình sẽ
được lặp lại cho đến khi hoặc là đỉnh t trở thành có nhãn hoặc là nhãn của tất cả các
đỉnh có nhãn đầu là đã xét nhưng đỉnh t vẫn không có nhãn. Trong trường hợp thứ nhất
ta tìm được đường tăng luồng, còn trong trường hợp thứ hai đối với luồng đang xét
không tồn tại đường tăng luồng (tức là luồng đã cực đại). Mỗi khi tìm được đường
tăng luồng, ta lại tăng luồng theo đường tìm được, sau đó xoá tất cả các nhãn và đổi
với luồng mới thu được lại sử dụng phép gán nhãn các đỉnh để tìm đường tăng luồng.
Thuật toán sẽ kết thúc khi nào đối với luồng đang có trong mạng không tìm được
đường tăng luồng.
Hai thủ tục tìm đường tăng luồng có thể mô tả như sau :
Procedure Find-path;
{
Thủ tục gán nhãn đường tăng luồng
p[v],  [v] là nhãn của đỉnh v;
VT
là danh sách các đỉnh có nhãn chưa xét ;
c[u,v] là
khả năng thông qua của cung (u,v),u,v V;
f[u,v] là luồng trên cung (u,v), (u,v  V);
}
BEGIN
p[s] := s ;
 [s] :=;
VT := {s};
Pathfound := true;
While
VT {}
do
159
BEGIN
u  VT ;( * lấy u từ VT *)
For vV do
If (v chưa có nhãn)
then
Begin
If (c[u,v] >0) and
(f[u,v]
Begin
P[v] := u ;
 [v] := min { [u],c[u,v]-f[u,v] };
VT:=VT {v};(* nạp v vào danh sách các đỉnh có nhãn *)
If v = t then exit;
End
Else
If (c[v,u] > 0) and (f[v,u]
Begin
P[v] := u ;
 [v] := min { [u] , f[u,v] };
VT:=VT {v};(* nạp v vào danh sách các đỉnh có nhãn *)
If v = t then exit;
End;
End;
End;
PathFound :=false;
End;
Procedure Inc_flow ;
{ thuật toán tăng luồng theo đường tăng }
Begin
v := t ;
u := t ;
tang := [t];
while u s do
egin
v := p[u];
if v > 0 then
f[v,u] := f[v,u] + tang
else
egin
v := -v;
f[u,v] :=f[u,v] –tang;
end;
u :=v ;
160

Nguồn: thuvienmienphi

 

Bạn phải gởi bình luận/ đánh giá để thấy được link tải

Nếu bạn chưa đăng nhập xin hãy chọn ĐĂNG KÝ hoặc ĐĂNG NHẬP
 
 

BÌNH LUẬN


Nội dung bậy bạ, spam tài khoản sẽ bị khóa vĩnh viễn, IP sẽ bị khóa.
Đánh giá(nếu muốn)
 BÌNH LUẬN

ĐÁNH GIÁ


ĐIỂM TRUNG BÌNH

0
0 Đánh giá
Tài liệu rất tốt (0)
Tài liệu tốt (0)
Tài liệu rất hay (0)
Tài liệu hay (0)
Bình thường (0)
Thành viên
Nội dung đánh giá

 
LINK DOWNLOAD

Bai-toan-luong-cuc-dai.pdf[0.34 M]

File đã kiểm duyệt
     Báo vi phạm bản quyền
Pass giải nén (Nếu có):
thuvienmienphi.com
DOWNLOAD
(Miễn phí)

Tài liệu tương tự