Latest topics
» Tự học lập trình IOS trong vòng 24hby kenanh 27/1/2014, 22:28
» xin tài liệu một số môn học
by nguyentvvan 21/8/2013, 21:34
» [Thảo luận] Bài toán đong nước
by giathinh9x 9/1/2013, 22:39
» Học Marketing Online, Học Chuyên viên Internet Marketing Online tại iNET
by NIIT-iNET 19/6/2012, 14:23
» Học PHP nâng cao, Học lập trình web với PHP nâng cao tại học viện iNET
by NIIT-iNET 19/6/2012, 14:22
» Học PHP, học lập trình web với PHP tại iNET vào ngày 19/07/2012
by NIIT-iNET 19/6/2012, 14:20
» PHIÊN BẢN MỚI CHO THIÊN ĐƯỜNG CÁ Ô LA LA !!!
by todaytv 13/3/2012, 15:35
» [hot] game khu vườn địa đàng phiên bản mobile của KVTM
by trantinh1713 3/1/2012, 15:20
» Đề tham khảo (update phút 90)
by ndc_2209 29/12/2011, 10:26
» Học bổng Lời Dịch tuần này.
by tienganh123 1/11/2011, 13:13
» [Thảo luận] Quản lý phân công giảng dạy PTTH
by huyquang0510 5/10/2011, 09:52
» Học tiếng Nhật - Top Globis
by tuquynh 21/9/2011, 10:35
» Học tiếng Nhật - Top Globis
by tuquynh 8/8/2011, 11:19
» Order Imitrex Online
by Khách viếng thăm 4/8/2011, 18:46
» Speeds Caffeine Metabolism Up
by Khách viếng thăm 4/8/2011, 18:12
» Skin For Good Caffeine
by Khách viếng thăm 3/8/2011, 14:54
» Cheap Pvc Figures
by Khách viếng thăm 1/8/2011, 19:32
» Action Rapid Onset Zolpidem Of
by Khách viếng thăm 31/7/2011, 01:13
» TUYỂN NHÂN VIÊN KINH DOANH ( làm việc tại văn phòng )
by canhkientp 5/7/2011, 14:59
» Demo + Vài điểm thảo luận về LINQ - Nhóm 7
by ChuongTienPhat 3/7/2011, 12:19
Thuật toán Dijkstra
2 posters
..:: Diễn đàn lớp 07CK2 - ĐH.KHTN - TP.HCM ::.. :: [ GÓC HỌC TẬP ] :: CÁC MÔN ĐÃ HỌC :: TRÍ TUỆ NHÂN TẠO
Trang 1 trong tổng số 1 trang
Thuật toán Dijkstra
Ở Silde thứ 30 trong bài Tìm Kiếm môn Trí Tuệ Nhân Tạo, có nhận xét là thuật toán tìm kiếm theo chiều rộng trong bài giống với thuật toán Dijkstra, vậy thuật toán Dijkstra là gì? Mời các bạn cùng tìm hiểu.
===========================================
Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm.
Bài toán
Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị.
Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và
các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh
có thể xem như độ dài của các con đường (và do đó là không âm). Chúng
ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra
sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.
Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn
khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh
A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C.
Thuật toán
Thuật toán Dijkstra có thể mô tả như sau:
Ta quản lý một tập hợp động S. Ban đầu S={s}.
Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v.
Trong các đỉnh ngoài S, chúng ta chọn đỉnh u có nhãn d[u] bé nhất, bổ sung vào tập S. Tập S được mở rộng thêm một đỉnh, khi đó chúng ta cần cập nhật lại các nhãn d cho phù hợp với định nghĩa.
Thuật toán kết thúc khi toàn bộ các đỉnh đã nằm trong tập S, hoặc
nếu chỉ cần tìm đường đi ngắn nhất đến một đỉnh đích t, thì chúng ta
dừng lại khi đỉnh t được bổ sung vào tập S.
Tính chất không âm của trọng số các cạnh liên quan chặt chẽ đến tính
đúng đắn của thuật toán. Khi chứng minh tính đúng đắn của thuật toán,
chúng ta phải dùng đến tính chất này.
Chứng minh
Ý tưởng của chứng minh như sau.
Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v.
Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v.
Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy.
Đường đi của ta có dạng s - ... - w - ... - v. Nhưng do trọng số các
cạnh không âm nên đoạn s - ... - w có độ dài không lớn hơn hơn toàn bộ
đường đi, và do đó có giá trị bé hơn d[v]. Mặt khác, do cách chọn w của ta, nên độ dài của đoạn s - ... - w chính là d[w]. Như vậy d[w] < d[v], trái với cách chọn đỉnh v. Đây là điều mâu thuẫn. Vậy điều giả sử của ta là sai. Ta có điều phải chứng minh.
Mã giả
Phân tích
Với giải thuật đã mô tả ta dễ dàng thực hiện trực tiếp trên các đồ
thị kích thước nhỏ,để có thể mã hóa và cài đặt hệ quả cần đưa thêm các
cấu trúc dữ liệu để sử dụng trong giải thuật.
Dữ liệu
.
Mã
Procedure Dijkstra {
For each v of V do {
d(v)=M
COLOR(v)=WHITE
d(s)=0
InsertHeap(Q,s)
k=1
While Q khác rỗng do {
u=Head(Q)
Push(Q,u)
k=k-1
COLOR(u)=BLACK
For each v of Ajd(u) {
if COLOR(v)=WHITE then {
k=k+1
HeapIndex(v)=k
InsertHeap(Q,v)
COLOR(v)=GRAY
PRE(v)=u
dv=d(u)+w(u,v)
}
if (COLOR(v)=GRAY) and d(v)>d(u)+w(u,v) then{
d(v)=d(u)+w(u,v)
PRE(v)=u
UpHeap(Q,HeapIndex(v))
}
}
}
Các thủ tục InsertHeap và UpHeap xem trong thuật toán Prim (Tìm cây bao trùm nhỏ nhất)Thêm một thủ tục mô phỏng dễ hiểu hơn cho thuật toán này như sau:
Dijkstra(G, s) {
Khởi tạo tập S chỉ chứa đỉnh ban đầu s;
for (mỗi đỉnh v thuộc G) {
D[v] = C(s, v); // C(s, v)=vô cùng nếu s và v không nối với nhau
}
D[s] = 0;
while ( (V-S) != Φ ) {
Chọn đỉnh u thuộc (V-S) sao cho D[u] ngắn nhất;
S = S U {u};
for ( mỗi v thuộc (V-S) ) {
if (D[u] + C(u, v) < D[v]) {
D[v] = D[u] + C(u, v);
}
}
}
}
Ví dụ
Thời gian chạy
Thuật toán Dijkstra bình thường sẽ có độ phức tạp là O( n^2+m ). Tuy
nhiên ta có thể sử dụng kết hợp với cấu trúc heap, khi đó độ phức tạp
sẽ là O( (n+m)*log2(n) ).
===========================================
Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm.
Bài toán
Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị.
Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và
các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh
có thể xem như độ dài của các con đường (và do đó là không âm). Chúng
ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra
sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.
Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn
khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh
A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C.
Thuật toán
Thuật toán Dijkstra có thể mô tả như sau:
Ta quản lý một tập hợp động S. Ban đầu S={s}.
Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v.
Trong các đỉnh ngoài S, chúng ta chọn đỉnh u có nhãn d[u] bé nhất, bổ sung vào tập S. Tập S được mở rộng thêm một đỉnh, khi đó chúng ta cần cập nhật lại các nhãn d cho phù hợp với định nghĩa.
Thuật toán kết thúc khi toàn bộ các đỉnh đã nằm trong tập S, hoặc
nếu chỉ cần tìm đường đi ngắn nhất đến một đỉnh đích t, thì chúng ta
dừng lại khi đỉnh t được bổ sung vào tập S.
Tính chất không âm của trọng số các cạnh liên quan chặt chẽ đến tính
đúng đắn của thuật toán. Khi chứng minh tính đúng đắn của thuật toán,
chúng ta phải dùng đến tính chất này.
Chứng minh
Ý tưởng của chứng minh như sau.
Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá trị của đường đi ngắn nhất từ nguồn s đến v.
Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v đến v.
Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu tiên như vậy.
Đường đi của ta có dạng s - ... - w - ... - v. Nhưng do trọng số các
cạnh không âm nên đoạn s - ... - w có độ dài không lớn hơn hơn toàn bộ
đường đi, và do đó có giá trị bé hơn d[v]. Mặt khác, do cách chọn w của ta, nên độ dài của đoạn s - ... - w chính là d[w]. Như vậy d[w] < d[v], trái với cách chọn đỉnh v. Đây là điều mâu thuẫn. Vậy điều giả sử của ta là sai. Ta có điều phải chứng minh.
Mã giả
Phân tích
Với giải thuật đã mô tả ta dễ dàng thực hiện trực tiếp trên các đồ
thị kích thước nhỏ,để có thể mã hóa và cài đặt hệ quả cần đưa thêm các
cấu trúc dữ liệu để sử dụng trong giải thuật.
Dữ liệu
- Hàm d(u) dùng để lưu trữ độ dài đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh u. Rõ ràng d(s)= 0. Ký hiệu X − (u) là tập tất cả các đỉnh có cạnh đi tới đỉnh u. Nếu với mọi đã xác định được d(v) thì:
.
- Để tính được giá trị nhỏ nhất này, như thông thường khi khởi tạo ta phải gán cho d(v)=, sau đó gặp giá trị nhỏ hơn thì thay thế lại.
- Những đỉnh đã tính được d(v)hữu hạn được cho vào một hàng đợi có ưu
tiên. Hàng đợi này luôn được bổ sung và sắp xếp lại nên một cấu trúc
hợp lý là cấu trúc đống nhị phân (heap). - Để theo dõi trạng thái của các đỉnh trong quá trình xét, ta dùng hàm COLOR(u) xác định với mọi .
Lúc đầu các đỉnh được tô màu trắng (WHITE), khi cho vào hàng đợi nó
được tô màu xám (GRAY), khi đã tính xong khoảng cách nó được tô màu
đen(BLACK). - Nếu cần ghi lại đường đi ta sẽ phải dùng một hàm con trỏ PRE(u) để
chỉ đỉnh đứng ngay trước đỉnh u trên đường đi ngắn nhất từ s tới u.
Mã
Procedure Dijkstra {
For each v of V do {
d(v)=M
COLOR(v)=WHITE
d(s)=0
InsertHeap(Q,s)
k=1
While Q khác rỗng do {
u=Head(Q)
Push(Q,u)
k=k-1
COLOR(u)=BLACK
For each v of Ajd(u) {
if COLOR(v)=WHITE then {
k=k+1
HeapIndex(v)=k
InsertHeap(Q,v)
COLOR(v)=GRAY
PRE(v)=u
dv=d(u)+w(u,v)
}
if (COLOR(v)=GRAY) and d(v)>d(u)+w(u,v) then{
d(v)=d(u)+w(u,v)
PRE(v)=u
UpHeap(Q,HeapIndex(v))
}
}
}
Các thủ tục InsertHeap và UpHeap xem trong thuật toán Prim (Tìm cây bao trùm nhỏ nhất)Thêm một thủ tục mô phỏng dễ hiểu hơn cho thuật toán này như sau:
Dijkstra(G, s) {
Khởi tạo tập S chỉ chứa đỉnh ban đầu s;
for (mỗi đỉnh v thuộc G) {
D[v] = C(s, v); // C(s, v)=vô cùng nếu s và v không nối với nhau
}
D[s] = 0;
while ( (V-S) != Φ ) {
Chọn đỉnh u thuộc (V-S) sao cho D[u] ngắn nhất;
S = S U {u};
for ( mỗi v thuộc (V-S) ) {
if (D[u] + C(u, v) < D[v]) {
D[v] = D[u] + C(u, v);
}
}
}
}
Ví dụ
Thời gian chạy
Thuật toán Dijkstra bình thường sẽ có độ phức tạp là O( n^2+m ). Tuy
nhiên ta có thể sử dụng kết hợp với cấu trúc heap, khi đó độ phức tạp
sẽ là O( (n+m)*log2(n) ).
Re: Thuật toán Dijkstra
chua hoc bo sao ma em chay duoc ha bac, cai nay kho hieu wa
nguyenminhtan-
Tổng số bài gửi : 18
Age : 35
Registration date : 24/04/2009
Re: Thuật toán Dijkstra
nguyenminhtan đã viết:chua hoc bo sao ma em chay duoc ha bac, cai nay kho hieu wa
Post anh em đọc tham khảo thôi, thì từ từ mà học, phải phấn đấu đi lên chứ
Re: Thuật toán Dijkstra
pac post bài thi phai để nguồn chứ, với lại khơi khơi vậy y như ở trang khác ai ma hiểu. Nếu vậy chỉ đường link cho người khác xem là dc rùi cần gì phải post vậy chi cho mệt . Dù sao cũng thanks. Có lòng tốt thì lần sau xem rùi chỉ dẫn lại cho a e nha pác
Khách v- Khách viếng thăm
Similar topics
» Sổ tay kỹ thuật phần cứng
» Thuật toán A*
» Một số thủ thuật máy tính
» Thi Giữa Kỳ
» cho hỏi môn kỹ thuật lập trình
» Thuật toán A*
» Một số thủ thuật máy tính
» Thi Giữa Kỳ
» cho hỏi môn kỹ thuật lập trình
..:: Diễn đàn lớp 07CK2 - ĐH.KHTN - TP.HCM ::.. :: [ GÓC HỌC TẬP ] :: CÁC MÔN ĐÃ HỌC :: TRÍ TUỆ NHÂN TẠO
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|