Bài giảng Toán rời rạc: Một số bài toán tối ưu trên đồ thị - ThS. Hoàng Thị Thanh Hà

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

8
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc - Một số bài toán tối ưu trên đồ thị được biên soạn gồm các nội dung chính sau: Một số bài toán trên đồ thị; Thuật toán dijkstra; Thuật toán floyd tìm khoảng cách của các cặp đỉnh. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Một số bài toán tối ưu trên đồ thị - ThS. Hoàng Thị Thanh Hà

Nội dung 1. MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ Toán rời rạc (5): 2. THUẬT TOÁN DIJKSTRA MỘT SỐ BÀI TOÁN TỐI ƯU 3. THUẬT TOÁN FLOYD TÌM KHOẢNG TRÊN ĐỒ THỊ CÁCH CỦA CÁC CẶP ĐỈNH Ts. Hoàng Thị Thanh Hà Khoa Thống kê –Tin học Trường Đại học Kinh tế 30 October 2012 1 30 October 2012 2 MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ Mở đầu: Có thể coi sơ đồ của đường đi từ A đến B trong Trong đời sống, chúng ta thường gặp những thành phố là một đồ thị, với đỉnh là các giao lộ tình huống như sau: để đi từ địa điểm A đến địa (A và B coi như giao lộ), cạnh là đoạn đường điểm B trong thành phố, có nhiều đường đi, nối hai giao lộ. Trên mỗi cạnh của đồ thị này, ta nhiều cách đi; có lúc ta chọn đường đi ngắn gán một số dương, ứng với chiều dài của đoạn nhất (theo nghĩa cự ly), có lúc lại cần chọn đường, thời gian đi đoạn đường hoặc cước phí đường đi nhanh nhất (theo nghĩa thời gian) và vận chuyển trên đoạn đường đó, ... có lúc phải cân nhắc để chọn đường đi chi phí thấp nhất, v.v... 30 October 2012 3 30 October 2012 4 MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ THUẬT TOÁN DIJKSTRA a) ĐN: Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm e∈E được gán bởi một số thực m(e), gọi là trọng số của khoảng cách d(u0,v) từ một đỉnh u0 cho trước đến một cạnh (hoặc cung) e đỉnh v bất kỳ của G và tìm đường đi ngắn nhất từ u0 đến v. – Ở đây trọng số của mỗi cạnh được xét là một số dương và còn gọi là chiều dài của cạnh đó. Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có – Mỗi đường đi từ đỉnh u đến đỉnh v, có chiều dài là m(u,v), bằng thuật toán do E. Dijkstra, nhà toán học người Hà Lan, đề tổng chiều dài các cạnh mà nó đi qua. Khoảng cách d(u,v) giữa xuất năm 1959. Trong phiên bản mà ta sẽ trình bày, người hai đỉnh u và v là chiều dài đường đi ngắn nhất trong các đường ta giả sử đồ thị là vô hướng, các trọng số là dương. Chỉ đi từ u đến v. cần thay đổi đôi chút là có thể giải được bài toán tìm Có thể xem một đồ thị G bất kỳ là một đồ thị có trọng số đường đi ngắn nhất trong đồ thị có hướng. mà mọi cạnh đều có chiều dài 1. Khi đó, khoảng cách d(u,v) giữa hai đỉnh u và v là chiều dài của đường đi từ u đến v ngắn nhất, tức là đường đi qua ít cạnh nhất. 30 October 2012 5 30 October 2012 6 1
THUẬT TOÁN DIJKSTRA THUẬT TOÁN DIJKSTRA b) Phương pháp của thuật toán Dijkstra: xác định tuần b). Ma tr n kho ng cách. tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn. Cho G=(V,E) V={v1,v2,…,vn}là đơn đ th Trước tiên, đỉnh có khoảng cách đến a nhỏ nhất chính là a, với d(u0,u0)=0. Trong các đỉnh v ≠ u0, tìm đỉnh có khoảng có tr ng s .Ma tr n kho ng cách c a G là ma tr n D= (dij) xác đ nh như sau { cách k1 đến u0 là nhỏ nhất. Đỉnh này phải là một trong các đỉnh kề với u0. Giả sử đó là u1. Ta có: d(u0,u1) = k1. Trong các đỉnh v ≠ u0 và v ≠ u1, tìm đỉnh có khoảng cách 0 nếu i=j k2 đến u0 là nhỏ nhất. Đỉnh này phải là một trong các đỉnh kề với u0 hoặc với u1. Giả sử đó là u2. Ta có: d(u0,u2) = k2. d(ij)= W(vi,vj) khi (vi,vj) ∈ E Tiếp tục như trên, cho đến bao giờ tìm được khoảng cách ∞ khi ∉ E từ u0 đến mọi đỉnh v của G. Nếu V={u0, u1, ..., un} thì: 0 = d(u0,u0) < d(u0,u1) < d(u0,u2) < ... < d(u0,un) 30 October 2012 7 30 October 2012 8 THUẬT TOÁN DIJKSTRA THUẬT TOÁN DIJKSTRA c)Thu t toánDijkstra Bài t p 1. Tìm đư ng đi ng n nh t t u0 đ n các Bư c1. i:=0, S:=V\{u0}, L(u0):=0, L(v):= ∞ v i m i v∈S đ nh còn l i và đánh d u đ nh v b i (∞,-). N u n=1 thì xu t d(u0,u0)=0 =L(u0) Bư c2. V i m i v ∈S và k v i ui (n u đ th có hu ng thì v là đ nh sau c a ui), đ t L(v):=min {L(v),L(ui)+w(ui,v)}, đánh d u v b i (L(v);ui) n u L(v) có s thay đ i. Xác đ nh k =min L(v) (v∈S) N u k=L(vj) thì xu t d(u0,vj)=k và ui+1:=vj S:=S\{ui+1} Bư c3 i:=i+1 N u i = n-1 thì k t thúc (ho c S r ng) , n u không thì quay l i Bư c 2 30 October 2012 9 30 October 2012 10 THUẬT TOÁN DIJKSTRA THUẬT TOÁN DIJKSTRA 30 October 2012 11 30 October 2012 12 2
THUẬT TOÁN FLOYD THUẬT TOÁN FLOYD Sử dụng ma trận Wn x n để tính độ dài đường đi ngắn Dữ liệu vào: Ma trận trọng số M của đồ thị và kết quả: Ma trận Wn chứa khoảng cách của tất cả các cặp đỉnh. nhất giữa tất cả các cặp đỉnh. BEGIN 1) Bắt đầu gán W0 := ma trận trọng số M for i := 1 to n do for j := 1 to n do W[i,j] := M[i,j] 2) Thực hiện n lần lặp trên W. Sau bước lặp thứ for i := 1 to n do W[i,i] := 0 {Khoảng cách từ một điểm đến k, W[i,j] chứa độ dài đường đi ngắn nhất từ đỉnh chính nó = 0} i đến đỉnh j mà chỉ đi qua các đỉnh có chỉ số for k := 1 to n do for i := 1 to n do không vượt quá k: for j := 1 to n do W(k)[i,j] := min ( W(k-1)[i,j] , W(k-1)[i,k] + W(k-1)[k,j] ) , if W[i,j] > W [i,k] + W[k,j] then W[i,j] := W[i,k] + W[k,j] với k = 1, 2, ... , n. {W[i,j] là phần tử dòng i cột j của ma trận Wk } END . 30 October 2012 13 30 October 2012 14 THUẬT TOÁN FLOYD THUẬT TOÁN FLOYD Định lý: Thuật toán Floyd cho ta ma trận W*=Wn Ví dụ: Xét đồ thị G sau: là ma trận khoảng cách nhỏ nhất của đồ thị G. 7 4 v1 v2 v3 2 1 2 1 3 4 2 v4 v5 v6 30 October 2012 15 30 October 2012 16 THUẬT TOÁN FLOYD THUẬT TOÁN FLOYD Áp dụng thuật toán Floyd, ta tìm được (các ô trống là ∞)  7 2  7 11 2 8       4 1   4 1   7 2    3   W1 = 3 W2 =    4 1     4   4 8 5   3 2 M = W0 =   2 9 2 4   9 2 4 10       4     1 5 2  2   1   2   1    30 October 2012 17 30 October 2012 18 3
THUẬT TOÁN FLOYD THUẬT TOÁN FLOYD  7 11 2 8 14   6 10 2 7 13      9 6 9 2 7 12  9 6 9 2 7 12   4 1 7       4 1 7 3 9 3 5 1 6  3 7 3 5 1 6    3  3    3  7 4 7 9 5 3 W3 =   W4 =  4 8 5 11  W5  W* = W6 =    4 8 5 11  7 4 7 9 5 10  7 4 7 9 5 10  2 2 8 2 4 9 5  =  9 2 4 10 5    2  8 2 4 9 5  2  6 2 4 7 5   2 8  4   1 5 2 8   1 5  4  1 4 6 2 7   1 4 6 2 7  30 October 2012 19 30 October 2012 20 4