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  i1  i2 …..  ik  n,
trong đó: 0 < i1 < i2 < …< ik < n,
Giá vé của xe đi từ thành phố i đến thành phố j là c[i,j]. Tìm một lộ trình từ thành phố 0 đến thành phố n sao cho tổng chi phí về giá vé đạt cực tiểu.
Phân tích bài toán
Gọi P(r) là bài toán du lịch để đi từ thành phố 0 đến thành phố r.
(bài toán ban đầu là P(n))
Các giá trị cần tìm:
d[r]: chi phí cực tiểu của bài toán P(r)
l[r]: thành phố cuối cùng cần đến trước khi đến thành phố r của bài toán P(r)
Giải pháp đệ quy
Nếu r = 1:
d[r] = c[0,1]
l[r] = 0
Nếu r > 1:
d[r] = Min {d[v]+C[v,r]} = d[v’]+C[v’,r]
0 ≤ v ≤ r-1
l[r] = v’
Lập bảng
Procedure LapBang;
Begin
For r:=1 to n do
Tính d[r] và l[r];
End;
Độ phức tạp tính toán: O(n2)
Tổng hợp kết quả
Procedure TongHop;
Begin
i := 0;
r := n;
While r > 0 do
begin i := i+1;
x[i]:= l[r];
r := x[i];
end;
writeln(‘Thứ tự các thành phố trung gian phải đi qua:’);
For k:=i downto 1 do writeln(x[i]);
End;
Độ phức tạp tính toán: O(n)