CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

default CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Bài gửi by Admin on Thu Oct 20, 2011 8:07 pm

MSĐT: NL1010
Tên đề tài: TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ CÓ HƯỚNG
GVHD: Phạm Thị Cẩm Tú
Số lượng sv: 03

+ Đối với chủ đề này các bạn sử dụng thuật toán Floyd thay cho Dijkstra vì Floyd là do cho bất kỳ cặp đỉnh nào và đồ thị là có hướng còn Dijkstra thì đồ thì vô hướng .
+ Mình không thể show source code ra đây được các bạn tự làm lấy nhé , mình chỉ chia sẻ thuật toán để các bạn tham khảo làm thôi. Ngoài ra ai còn thuật toán nào hay thì up lên đây chia sẻ cùng anh em nhé . Ngoài cách này các bạn có thể tham khảo thêm tài liệu của thầy Thắng trong quyển Toán rời rạc II chương các bài toán tối ưu về đồ thị có đề cập đến vấn đề này @ .
+ Mọi thắc mắc anh em cứ show soure code lên đây cùng bình luận tham khảo và chỉnh sữa.
+ Còn về tải liệu tham khảo mình up này bạn cứ để là Tham khảo trên forum K4info.forumr.net vì trang forum mình là 1 website bình thường. Mình phải tự tin về forum lớp mình chứ. Forum mình là 1 forum học tập mà .




Sau đây là thuật toán và giải thuật:


Đường đi ngắn nhất giữa tất cả các cặp đỉnh



Bài toán: Cho một đồ thị có trọng số (G, c). Hãy tìm đường đi ngắn nhất giữa tất c
các cặp đỉnh.

Bài toán này thường gặp trong việc xây dựng bảng khoảng cách giữa cá
thành phố, bảng giá cước vận chuyển giữa các nhà ga ...

Bài toán này có thể giải quyết bằng cách sử dụng thuật toán Dijkstra với mỗ
đỉnh của đồ thị lần lượt là các đỉnh xuất phát. Tuy nhiên, ta có thể giải quyết trự
tiếp bài toán nhờ thuật toán Floyd như sau:

Ta sử dụng ma trận Dn x n để tính độ dài đường đi ngắn nhất giữa tất cả cá
cặp đỉnh.
1. Bắt đầu gán D := C - ma trận trọng số.
2. Thực hiện n lần lặp trên D. Sau bước lặp thứ k, D[i,j] chứa độ dài đườn
đi ngắn nhất từ đỉnh i đến đỉnh j mà chỉ đi qua các đỉnh có chỉ số khôn
vượt quá k. Vậy trong bước lặp thứ k ta thực hiện theo công thức sau đây:
D(k)
[i,j] := min (D(k-1)
[i,j] , D(k-1)
[i,k] + D(k-1)
[k,j]) ,
với k = 1, 2, ... , n.
Ví dụ 8.5: Giả sử ta có bản đồ giao thông sau đây:



Thuật toán (Floyd):

Dữ liệu: Ma trận trọng số C của đồ thị.
Kết quả: Ma trận D cho biết khoảng cách của tất cả các cặp đỉnh.


Code:



1  BEGIN
2    for  i  := 1  to  n  do                   
3        for  j  :=  1  to  n  do 
4    begin  D[i,j]  :=  C[i,j]  ; TRUOC[i,j]  :=  0  end ;
5    for  k  :=  1  to  n  do                   
6  for  i  :=  1  to  n  do                   
7    for  j  :=  1  to  n  do 
8    if  D[i,k] + D[k,j]  <  D[i,j]  then
9        begin   
10                            D[i,j]  :=  D[i,k] + D[k,j]  ; 
11  TRUOC[i,j]  :=  k
12        end ;
13  END .
Nếu  TRUOC[i,j] = 0  thì đưòng đi ngắn nhất từ đỉnh  i  đến đỉnh  j  chính là
cạnh  (i, j). 
Để in ra các đỉnh trung gian trên đường đi ngắn nhất từ đỉnh  i  đến đỉnh  j  ta
dùng thủ tục đệ quy sau đây:
 
1  procedure Duong_di( i, j ) ;
2  begin
3  k  :=  TRUOC[i,j]  ;
4 if  k = 0  then  Exit ;
5 Duong_di( i, k ) ;
6 write( k ) ;
7  Duong_di( k, j ) ;
8  end ;





Để xác định đường đi ngắn nhất từ đỉnh 1 đến đỉnh 2 ta lấy k = TRUOC[1,2] = 3.
Vậy đường đi ngắn nhất là: < 1, 3, 2 >.

Chúc các bạn sớm hoàn thành niên luận và đạt điểm số cao nhất
Các bạn có thể tải tập tin đính kèm này về tham khảo.
Attachments
Đường đi ngắn nhất giữa tất cả các cặp đỉnh.doc You don't have permission to download attachments.(112 Kb) Downloaded 6 times

Admin

Posts : 1013
Thanked : 47
Gia Nhập 25/08/2010

Tài Sản
Thú nuôi:

http://k4info.forumr.net

Về Đầu Trang Go down

default Re: CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Bài gửi by shippou777 on Thu Oct 20, 2011 9:35 pm

Mới thi xong là làm tới niên luận hả bác.
Nghỉ ngơi chút đi. Học nhiều quá coi chừng tẩu hoả nhập ma

shippou777

Posts : 460
Thanked : 8
Gia Nhập 11/10/2011

Tài Sản
Thú nuôi:

Về Đầu Trang Go down

default Re: CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Bài gửi by 0951010003 on Fri Oct 21, 2011 12:22 am

Tâm à bữa đó Tâm không đi nên không nghe cô Tú hướng dẫn, bài của mình là sử dụng thuật toán Dijkstra có hướng đó. k có floyd đâu.hihi Ham ngủ

0951010003

Posts : 90
Thanked : 13
Gia Nhập 09/09/2011

Tài Sản
Thú nuôi:

Về Đầu Trang Go down

default Re: CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Bài gửi by Admin on Fri Oct 21, 2011 10:47 am

Ủa? Cố lộn không vậy? Lấy cuốn Toán rồi rạc của ông thầy Thắng ra xem lại coi! Haha đồ thị có hướng. Xem lại đi sẻ rõ hà. Idea

Admin

Posts : 1013
Thanked : 47
Gia Nhập 25/08/2010

Tài Sản
Thú nuôi:

http://k4info.forumr.net

Về Đầu Trang Go down

default Re: CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Bài gửi by Misa_love on Sun Oct 23, 2011 6:54 pm

ông hỏi lại cô chưa z ??? cô có cho làm thuật toán Ford hok ????? Smile

Misa_love

Posts : 9
Thanked : -1
Gia Nhập 01/11/2010

Tài Sản
Thú nuôi:

Về Đầu Trang Go down

default Re: CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Bài gửi by 0951010003 on Mon Oct 24, 2011 8:22 am

haizzzzz mệt ghê vậy đó. cô nói rõ ràng. tui cũng thấy la đây nè

0951010003

Posts : 90
Thanked : 13
Gia Nhập 09/09/2011

Tài Sản
Thú nuôi:

Về Đầu Trang Go down

default Re: CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Bài gửi by Admin on Mon Oct 24, 2011 9:58 am

1 Bài toán có rất nhiều cách giải, mình chọn cách nào mình hiểu và dễ và tối ưu nhất . nói cô như là Ông Chủ vậy , bắt làm cái gì là làm cái đó, không có sự chọn lựa đâu . Anh em đành nguyên cứu giải thuật Dijkstra đi. Cô nói bắt tụi mình làm Dijkstra, làm Dijkstra mà áp dụng trên đồ thị có hướng mới ghê, xác nhận cuối cùng là dùng giải thuật Dijkstra để làm, anh em ngâm cứu đi không có sự chọn lựa đâu.

Admin

Posts : 1013
Thanked : 47
Gia Nhập 25/08/2010

Tài Sản
Thú nuôi:

http://k4info.forumr.net

Về Đầu Trang Go down

default Re: CHỦ ĐỀ NIÊN LUẬN SỐ 10 - CÔ TÚ

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết