Bai toan du lich

28 %
72 %
Information about Bai toan du lich

Published on June 23, 2008

Author: hcdung18

Source: slideshare.net

Description

Bai toan du lich giai bang quy hoach dong

Bài toán du lịch Một người đi từ thành phố 0 đến thành phố n và có thể đi qua n-1 thành phố khác 1, 2,…n-1 theo lộ trình: 0  i 1  i 2  …  i k  n (0 < i 1 < i 2 < … < i k < n) c[i,j]: là giá vé đi từ thành phố i đến j Tìm lộ trình từ thành phố 0  n sao cho tổng chi phí (giá vé) đạt cực tiểu.

Một người đi từ thành phố 0 đến thành phố n và có thể đi qua n-1 thành phố khác 1, 2,…n-1 theo lộ trình:

0  i 1  i 2  …  i k  n

(0 < i 1 < i 2 < … < i k < n)

c[i,j]: là giá vé đi từ thành phố i đến j

Tìm lộ trình từ thành phố 0  n sao cho tổng chi phí (giá vé) đạt cực tiểu.

Ví dụ: Tìm lộ trình đi từ thành phố đến Bài toán du lịch Lộ trình: 0 4 Chi phí: 6 0 1 2 3 4 5 3 4 1 2 8 0 2 3 4 0 1 3 2 4 5 3 4 1 2 8 0 4 8

Ví dụ: Tìm lộ trình đi từ thành phố đến

Bài toán du lịch Phân tích bài toán: Gọi p(r,s) là bài toán du lịch, với: r  N là thành phố xuất phát s  N là thành phố cần đến (Bài toán ban đầu là P(0,n) Các giá trị cần tìm : l[r,s]: chi phí nhỏ nhất để đi từ r  s của bài toán p(r,s) u[r,s]: đỉnh kế cuối trên đường đi từ r  s của bài toán p(r,s)

Phân tích bài toán:

Gọi p(r,s) là bài toán du lịch, với:

r  N là thành phố xuất phát

s  N là thành phố cần đến

(Bài toán ban đầu là P(0,n)

Các giá trị cần tìm :

l[r,s]: chi phí nhỏ nhất để đi từ r  s của bài toán p(r,s)

u[r,s]: đỉnh kế cuối trên đường đi từ r  s của bài toán p(r,s)

Bài toán du lịch p(r,s) Giải pháp đệ quy: + Khi r = s: l[r,s] = 0 u[r,s] = -1 (vì không có đỉnh kế cuối) + Khi r < s: l[r,s] = min (l[r,k] + c[k,s]) (r  k<s) = l[r,k’] + c[k’,s] u[r,s] = k’

Giải pháp đệ quy:

+ Khi r = s:

l[r,s] = 0

u[r,s] = -1 (vì không có đỉnh kế cuối)

+ Khi r < s:

l[r,s] = min (l[r,k] + c[k,s])

(r  k<s)

= l[r,k’] + c[k’,s]

u[r,s] = k’

Lập bảng (Bài toán du lịch) Procedure lapbang; Begin r:=0; {thành phố xuất phát} For s:=0 to n do If (r = s) then tính l[r,r] và u[r,r] Else {r < s} tính l[r,s] và u[r,s] End; * Độ phức tạp tính toán: O(n 2 )

Procedure lapbang;

Begin

r:=0; {thành phố xuất phát}

For s:=0 to n do

If (r = s) then

tính l[r,r] và u[r,r]

Else {r < s}

tính l[r,s] và u[r,s]

End;

* Độ phức tạp tính toán: O(n 2 )

Procedure lapbang; Begin r:=0; {thành phố xuất phát} For s:=0 to n do If (r = s) then begin l[r,r] = 0; u[r,r] = -1; end Else {r < s} begin dinhke:=0; min:= giatri_max; for k:=r to s-1 do if (tồn tại cạnh (k,s)) then if (l[r,k] + c[k,s]) < min then begin dinhke:= k; min:= l[r,k] + c[k,s]; end; l[r,s]:= min; u[r,s]:= dinhke; end;End;

Procedure lapbang;

Begin r:=0; {thành phố xuất phát}

For s:=0 to n do

If (r = s) then

begin

l[r,r] = 0; u[r,r] = -1;

end

Else {r < s}

begin

dinhke:=0; min:= giatri_max;

for k:=r to s-1 do

if (tồn tại cạnh (k,s)) then

if (l[r,k] + c[k,s]) < min then

begin

dinhke:= k; min:= l[r,k] + c[k,s];

end;

l[r,s]:= min; u[r,s]:= dinhke;

end;End;

Tổng hợp kết quả (Bài toán du lịch) Procedure tonghop; Begin r: = 0; s:= n; x[1]:=s; {lưu duong di} i:=2; while (r <> s) and (l[r,s]< giatri_max) do begin x[i]:= u[r,s]; s:= x[i]; i:= i + 1; end; If (r<>s) then ‘khong co dd’ else inkq(x); End; * Lập bảng : * Đường đi: (  : giatri_max) 0 1 2 3 4 5 3 4 1 2 8  0 4 3 2 1 0 s r 0 -1 0 2 0 3 2 6 3 0 2 3 4 X

Nhóm 5 : 1. Hoàng Chí Dũng 2. Phạm Hồng Ngự 3. Ngô Quỳnh Như 4. Lê Duy Sử

Add a comment

Related presentations

Related pages

Bài toán người đi du lịch - Documents

Báo cáo bài tập lớn Trí tuệ nhân tạo Bài toán người đi du lịch TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG ...
Read more

Bai Toan Du Lich - scribd.com

CE191: Civil and Environmental Engineering Systems AnalysisLab 2 Integer Programming: Solving the Traveling Salesman Problem Profess...
Read more

Bai Toan Du Lich - es.scribd.com

CE191: Civil and Environmental Engineering Systems AnalysisLab 2 Integer Programming: Solving the Traveling Salesman Problem Profess...
Read more

Was ist Bai toan nguoi du lich.exe und wie kann ich es ...

Bai toan nguoi du lich.exe-Probleme sind z.B. hohe CPU-Auslastung, Anwendungsfehler und eine mögliche Infektion mit Viren . Hier sehen Sie die fünf ...
Read more

Thiết kế và đánh giá thuật toán: Bài toán người du lịch - VOER

Bài toán: Một nguời du lịch muốn tham quan n thành phố T1,.., Tn . Xuất phát từ một thành phố nào đóngười du lịch muốn ...
Read more

Bai Toan Du Lich - pt.scribd.com

CE191: Civil and Environmental Engineering Systems Analysis. Lab 2 Integer Programming: Solving the Traveling Salesman Problem Professor A. Bayen Fall 06
Read more

Bài toán người du lịch và các thuật giải - Luận văn, đồ án ...

Bài toán người du lịch và các thuật giải - Nội dung 1/Giới thiệu lịch sử của bài toán người du lịch 2/Mô tả chi tiết ...
Read more

Du lịch Việt và bài toán 'thu đến đồng tiền cuối cùng của ...

Du lịch Việt và bài toán 'thu đến đồng tiền cuối cùng của du khách'
Read more

Bài toán người đi du lịch - vi.scribd.com

Bai Toan Nguoi Du Lich. Thiết kế thuật toán-vét cạn và tham lam. bài mẫu. XLNNTN. Ung Dung Phuong Phap Phan Loai Van Ban Naive Bayes Vao Viec ...
Read more

Du lịch tưởng thưởng – bài toán đã có lời giải

Du thuyền 5 sao Royal Caribbean là lời ... lo toan hàng trăm việc khác nhau cho ... du lich thai lan, du lich singapore, du lich han ...
Read more