BÀi tập và thực hành môn học lý thuyết đồ thị

4.1.3Thuật toán tìm đường đi ngắn nhất Floyd- Warshall

Tư tưởng thuật toán như sau:

• 
  Để xác định đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị, thì ta phải xác định tất cả n*(n-1) giá trị, tương ứng với các cặp (u,v) trên đồ thị.
  
• 
  Khi đó ta dùng luôn ma trận trọng số A_nxn làm ma trận lưu kết quả. Khi đó A[i][j] là giá trị khoảng cách ngắn nhất đi từ đỉnh i đến đỉnh j.
  
• 
  Tư tưởng thuật toán này cũng khá đơn giản:
  
  • 
    Chọn 1 đỉnh là trung gian, giả sử là đỉnh k.
    
  • 
    Tối ưu hóa đường đi từ đỉnh u đến đỉnh v theo k. Tức là ta so sánh A[u][v] với tổng A[u][k] và A[k][v]. Nếu đi từ u đến v dài hơn so với đi từ u qua k rồi đến v thì ta sẽ tối ưu giá trị A[u][v].
    
  • 
    Ta thấy có n cách chọn đỉnh k, với mỗi k có n cách chọn đỉnh xuất phát u và với mỗi u ta có n cách chọn đỉnh kết thúc v. Như vậy ta có 3 vòng lặp lồng nhau.
    

• 
  Nếu từ u đế k có đường đi, tức là A[u][k] = 1 và từ k đến v cũng có đường đi, tức là A[k][v] = 1 thì chắc chắn có đường đi từ u đến v  A[u][v] = 1.
  

A

B

C

D

E

F

H

A

I

B

C

Yêu cầu viết các kết quả trung gian trong từng bước lặp, kết quả cuối cùng cần đưa ra tập cạnh và độ dài của cây khung nhỏ nhất.

Rõ ràng 1 đồ thị cho ta nhiều cây khung. Vấn đề là xác định cây khung nào trong đồ thị có trọng số sao cho tổng trọng số là bé nhất.

Tư tưởng của thuật toán này là dựa trên thuật toán tìm đường đi tối ưu Dijsktra.

• 
  Dùng tập S để lưu trữ các đỉnh đã được duyệt. ban đầu S = Ø.
  

• 
  Đối với bài toán tìm đường đi ngắn nhất giữa 2 điểm u,v, thì thuật toán Dijsktra sẽ lần lượt chọn các đỉnh trên đồ thị sao cho giá trị khoảng cách từ đỉnh u đến đỉnh mới duyệt là nhỏ nhất có thể được. Quá trình dừng lại khi đỉnh v được duyệt.
  
• 
  Đối với bài toán xác định cây khung nhỏ nhất, thì quá trình duyệt các đỉnh cũng như trên, nhưng chỉ dừng lại khi không còn duyệt được thêm đỉnh nào nữa.
  
• 
  Chú ý ở đây biến D[v] không phải là khoảng cách đi từ đỉnh u đến v mà là khoảng cách từ v đến S (là khoảng cách ngắn nhất từ v đến 1 đỉnh trong tập S).
  
  • 
    Nếu giá trị khoảng cách tại đỉnh cuối cùng ≠ ∞, thì ta đã có 1 cây khung bé nhất.
    
  • 
    Trong trường hợp ngược lại thì không xác định được cây khung bé nhất.
    

Procedur Prim_Dijsktra; Begin Chọn 1 đỉnh u là gốc của cây. D[u] = 0; D[v] = ∞ với v ≠ u; S = Ø while True do begin Tìm đỉnh k thoả mãn Free[k] = 1 và D[k] nhỏ nhất ; If (không xác định được k OR D[k] = ∞) then Break. Else F := F U (T[k],k), S = S U k ; Free[k] = 0 For v  V do If Free[v] = 1 và D[v]> A[k][v] then // chú ý đk này!!!!! begin D[v]:= A[k][v]; T[v]:=k; end; end; End;

4.1.4Thuật toán Kruskal (thuật toán tham lam – ăn tham)

Tư tưởng của thuật toán như sau:

• 
  Khởi tạo tập các cạnh của cây khung F = Ø.
  
• 
  Chọn các cạnh của đồ thị theo trọng số từ nhỏ đến lớn, sao cho nó không tạo ra chu trình trong tập F.
  
• 
  Đưa cạnh vừa chọn vào tập F và xóa nó khỏi tập cạnh E của đồ thị.
  
• 
  Quá trình lặp lại cho đến khi trong tập F có đúng n-1 cạnh.
  

Thuật toán mô tả như sau:

Procedure Kruskal; Begin F := Ø; // khởi tạo tập rỗng While |F| < (n-1) and (E ≠ Ø) do // kiểm tra số phần tử của tập F Begin Chọn cạnh {e} sao cho trọng số trên {e} là nhỏ nhất. E:=E\{e}; if (F U {e} không chứa chu trình) then F := T U { e} ; End; if (|T| < n-1) then Đồ thị không liên thông; End; Độ phức tạp của thuật toán là O(m*log2m) với |E| = m.

Bài tập tổng hợp:

1. 
   Cho ma trận kề (trọng số) của một đồ thị như sau
   

1. 
   Vẽ đồ thị tương ứng
   
2. 
   Đồ thị có phải là đồ thị Euler (nửa Euler) hay không? Giải thích. Nếu có,tìm chu trình (đường đi) Euler trong đồ thị.
   
3. 
   Đồ thị có phải là đồ thị Hamilton hay không? Nếu có, tìm chu trình Hamilton trong đồ thị.
   
4. 
   Tìm đường đi ngắn nhất từ đỉnh số 1 đến đỉnh số 8.
   
5. 
   Tìm cây khung nhỏ nhất của đồ thị.
   
1. 
   Cho ma trận kề (trọng số) của một đơn đồ thị vô hướng như sau:
   

1. 
   Vẽ đồ thị, cho biết bậc của các đỉnh. Đây có phải là đồ thị Euler hay không?
   
2. 
   Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại bằng thuật toán Dijkstra.
   
3. 
   Tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Kruskal.
   

17. Cho đồ thị như hình vẽ:

1. 
   Xác định bán bậc ra và bán bậc vào của các đỉnh của đồ thị.
   
2. 
   Đây có phải là đồ thị liên thông mạnh không? Tại sao?
   
3. 
   Xây dựng ma trận kề, trọng số của đồ thị.
   
4. 
   Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3.
   

18. Cho đồ thị như hình vẽ:

1. 
   Xác định bậc của các đỉnh của đồ thị, từ đó cho biết đây có là đồ thị Euler hay nửa Euler hay không?
   
2. 
   Xây dựng ma trận kề trọng số của đồ thị
   
3. 
   Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 5 trong đồ thị.
   
4. 
   Tìm cây khung nhỏ nhất của đồ thị.
   

Bài tập nâng cao:

1. 
   Bài toán truyền tin trên mạng.
   

Một mạng máy tính gồm N máy đánh số từ 1 đến N, và M kênh truyền tin một chiều gữa một số cặp máy trong mạng được đánh số từ 1 đến M. Mạng máy tính là thông suốt, nghĩa là từ một máy có thể truyền tin đến một máy bất kỳ khác bằng các đường nối trực tiếp hoặc thông qua các máy trung gian. Một máy trong mạng là số chẵn nếu số kênh truyền tin trực tiếp từ nó đến các máy khác là chẵn. Một máy trong mạng là số lẻ nếu số kênh truyền tin trực tiếp từ nó đến các máy khác là lẻ. Giả sử s và t là hai máy lẻ trong mạng, hãy đổi hướng truyền tin của một số kênh để biến đổi mạng đã cho thành mạng (không nhất thiết phải thông suốt) mà trong nó hia máy s và t trở thành 2 máy chẵn và không làm thay đổi tính chẵn lẻ của các máy khác trong mạng. Số kênh đổi hướng càng ít càng tốt.

Net.inp	Net.out
6 9 1 6 2 3 3 4 4 1 4 6 6 3 2 5 5 3 5 6	3 1 7 9

Dữ liệu nhập vào từ file văn bản Net.inp:

• 
  Dòng đầu tiên chứa 2 số N, M (N<2000, M<10000).
  
• 
  Dòng thứ 2 chứa 2 số s và t.
  
• 
  Dòng thứ I trong số M dòng tiếp theo chứa 2 số u_i và v_i cho biết kênh truyền tin thứ i truyền tin trực tiếp từ máy u_i đến v_i
  
• 
  Kết quả ghi ra file Net.out
  
  • 
    Dòng đầu ghi số lượng kênh cần thay đổi hướng truyền tin (số q).
    
  • 
    Mỗi dòng trong q dòng tiếp theo ghi chỉ số kênh cần đảo ngược hướng truyền tin.
    
• 
  Ví dụ: (xem bảng số liệu bên cạnh)
  

2. 
   Bài toán thang máy
   

Một tòa nhà gồm N tầng, đánh số từ 1 đến N (0

Dữ liệu nhập vào từ file văn bản Tm.inp

• 
  Dòng đầu ghi 2 số nguyên dương N và M.
  
• 
  M dòng tiếp theo, dòng thứ I ghi 2 số a_i và b_i mô tả yêu cầu thứ i
  

Kết quả ghi ra file văn bản Tm.out

• 
  Dòng đầu là tổng quãng đường tìm được
  
• 
  Dòng thứ 2 mô tả thứ tự thực hiện các công việc bởi một hoán vị của 1, 2, …M.
  

3. 
   Bài toán K đường đi ngắn nhất
   

Vùng đất X có N thành phố (3

• 
  Thành phố xuất phát là thành phố 1 và kết thúc là thành phố N.
  
• 
  Mỗi đội thi đấu có K người dự thi. Khi người thứ nhất đến được thành phố N thì người thứ hai mới bắt đầu rời khỏi thành phố 1, khi người thứ 2 đến thành được thành phố N thì người thứ 3 mới rời khỏi thành phố 1, cứ như vậy cho đến khi người thứ K về tới đích thì được xem như thời điểm tính cho toàn đội.
  
• 
  Đường chạy của các đội viên không được giống nhau hoàn toàn.
  
• 
  Có thể chạy lại đoạn đường đã chạy.
  

Hãy viết chương trình tính thời gian nhỏ nhất để một đội hoàng thành cuộc chạy đua tiếp sức nếu trên nếu các vận động viên có tốc độ chạy như nhau.

Net.inp	Net.out
4 5 8 1 2 1 1 3 2 1 4 2 2 3 2 2 5 3 3 4 3 3 5 4 4 5 6	23 1 1325 135 12125 125

Dữ liệu nhập vào từ file văn bản Kminpath.inp

• 
  Dòng đầu ghi 2 số nguyên dương K, N và M.
  
• 
  M dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, w thể hiện một đường đi trực tiếp giữa hai thành phố i và j mất thời gian chạy là w.
  

Kết quả ghi ra file văn bản Kminpath.out

• 
  Dòng thứ nhất chứa một số nguyên duy nhất là thời gian chạy nhỏ nhất của 1 đội
  
• 
  K dòng tiếp theo, mỗi dòng thể hiện hành trình chạy của một vận động viên trong đội là dãy các thành phố liên tiếp trên hành trình đó.
  

Ví dụ: (xem bảng bên)

4. 
   Bài toán công chúa kén chồng
   

Magachip IV the Splendid, vua của Byteotia, có ý định chọn phò mã cho công chúa Ada của mình. Công chúa thì muốn chồng mình phải là người thông minh, không keo kiệt và không lãng phí quá. Nên nhà vua suy nghĩ mới chọn phương pháp thử tài bằng cách chọn lâu đài của mình làm nơi thi đấu. Lâu đài gồm nhiều phòng trưng bày đồ quí hiếm và nối với nhau bằng dãy các hành lang để thần dân có thể tham quan, phòng cuối cùng là phòng của công chúa, để thăm một phòng phải trả một đồng bytealer và sẽ xuất phát từ phòng đầu tiên. Nhà vua trao cho mỗi chàng trai đến cầu hôn một số đồng tiền chứa trong 1 cái túi và yêu cầu là mỗi người thăm 1 số phòng sao cho đến phòng cuối cùng thì tiêu hết số tiền đã cho, nếu đến phòng cuối cùng mà vẫn còn tiền thì phải thăm lại một số phòng

Zam.inp

5 6 3 4 9 1 2 3 4 5 2 4 5 4 1 5 1 2 2 3 3 1

Zam.out

3 2 4

trưng bày nữa mới quay lại. Hãy lập trình giải quyết vấn đề trên để 1 chàng trai luôn có

thể thực hiện được yêu cầu của nhà vua.

Dữ liệu nhập từ file Zam.inp miêu tả lâu đài, số hiệu phòng công chúa đang ở, tổng số tiền trong túi:

• 
  Dòng đầu tiên có 5 số nguyên dương n(số lượng phòng), m(số hành lang), e(số hiệu phòng xuất phát), p(số hiệu phòng công chúa), b(tổng số tiền vua ban cho).
  
• 
  Dòng 2 có n số nguyên dương c_i, mỗi số là chi phí mỗi lần vào thăm trong phòng i.
  
• 
  Trong m dòng tiếp theo có từng cặp số nguyên dương (x, y), mỗi cặp nối biểu thị một hành lang nối phòng x với phòng y.
  

Tính ra dãy các phòng đi qua đến phòng của công chúa và lưu hành trình vào file Zam.out

Ví dụ: (như bảng dữ liệu bên cạnh)

5. 
   Bài toán chia cắt địch
   

Chiacat.inp	Chiacat.out
10 18 1 2 8 1 4 4 1 7 1 2 3 5 2 4 5 2 9 9 3 4 4 3 6 2 3 9 7 4 5 5 5 6 6 5 7 5 5 8 3 6 8 7 6 10 1 7 8 5 8 10 1 9 10 9	10 1 7 3 6 4 5 6 10 8 10

Cuối năm 1944, quân Liên Xô phản công vào vùng X, nơi có N thành phố bị phát xít Đức chiếm đóng. Dọc theo các con đường giữa 2 thành phố đều có quân Đức canh giữ. Bộ tham mưu quân sự của Liên Xô mới chỉ đạo phản công tiêu diệt địch, bước đầu thực hiện chia cắt quân địch thành 2 vùng tách biệt để chúng không liên lạc được với nhau, nhưng cần tính toán tiêu diệt như thế nào là lợi nhất mà chỉ cần huy động lực lượng ít nhất để giành thắng lợi. Biết rằng đi tiêu diệt quân Đức thì Liên Xô phải bố trí số quân ít nhất bằng với số quân địch chiếm đóng. Hãy viết chương trình giúp bộ tham mưu quân Liên Xô chỉ cần điều ít nhất lực lượng để giành chiến thắng.

Dữ liệu nhập vào từ file Chiacat.inp

• 
  Dòng đầu tiên là 2 số nguyên dương N (số thành phố tối đa 100) và M(số con đường nối các cặp 2 thành phố trong vùng X).
  
• 
  M dòng tiếp theo, mỗi dòng có 3 số nguyên dương i, j và w thể hiện trên con đường nối thành phố i với thành phố j hiện có w lính Đức.
  

Kết quả ghi ra file Chiacat.out

• 
  Dòng đầu là số lượng quân Liên Xô cần điều động
  
• 
  Dòng sau, mỗi dòng có 2 số u và v thể hiện con đường (u, v) mà quân Liên Xô cần chiếm lại trong đợt phản công đầu tiên này.
  

Ví dụ: (xem bảng bên)

Каталог: wp-content -> uploads -> 2017
2017 -> Th ng b¸o thuèc míi
2017 -> Nguyen hoang cuong
2017 -> Curriculum vitae
2017 -> CỤc quản lý DƯỢc cộng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh Phúc
2017 -> Cung cấp giải pháp phần mềm
2017 -> MỘt số kiến thức cơ BẢn dành cho newbie
2017 -> NguyễN ĐĂng thảo vài Nét Chấm Phá Trong Đời Sống Âm Nhạc
2017 -> ĐỀ CƯƠng chi tiết môN: quản trị nguồn nhân lựC
2017 -> Điều Danh mục thuốc đông y, thuốc từ dược liệu và vị thuốc y học cổ truyền

tải về 257.57 Kb.

Chia sẻ với bạn bè của bạn: