//
you're reading...
00 - Chủ đề chung, Bài tập huấn luyện, Đề ôn luyện thi học kỳ

Bài tập huấn luyện: Bài toán người du lịch


Đề bài


bai-10


Hướng dẫn


Nhánh và cận

1. Phương pháp

Trong thực tế, có nhiều bài toán yêu cầu tìm ra một phương án thoả mãn một số ñiều kiện nào ñó, và phương án ñó là tốt nhất theo một tiêu chí cụ thể. Các bài toán như vậy ñược gọi là bài toán tối ưu. Có nhiều bài toán tối ưu không có thuật toán nào thực sự hữu hiệu ñể giải quyết, mà cho ñến nay vẫn phải dựa trên mô hình xem xét toàn bộ các phương án, rồi ñánh giá ñể chọn ra phương án tốt nhất.
Phương pháp nhánh và cận là một dạng cải tiến của phương pháp quay lui, ñược áp dụng ñể tìm nghiệm của bài toán tối ưu.
Giả sử nghiệm của bài toán có thể biểu diễn dưới dạng một vector
, , … , , mỗi thành phần 1,2, . . , ‘ ñược chọn ra từ tập . Mỗi nghiệm của bài toán
ñược xác ñịnh “ñộ tốt” bằng một hàm 9% và mục tiêu cần tìm nghiệm có giá trị 9% ñạt giá trị nhỏ nhất (hoặc ñạt giá trị lớn nhất).
Tư tưởng của phương pháp nhánh và cận như sau: Giả sử, ñã xây dựng ñược k thành phần
, , … , & của nghiệm và khi mở rộng nghiệm , , … , &, nếu biết rằng tất cả các nghiệm mở rộng của nó , , … , &, … ñều không tốt bằng nghiệm tốt nhất ñã biết ở thời ñiểm ñó, thì ta không cần mở rộng từ , , … , & nữa. Như vậy, với phương pháp nhánh và cận, ta không phải duyệt
toàn bộ các phương án ñể tìm ra nghiệm tốt nhất mà bằng cách ñánh giá các nghiệm mở rộng, ta có thể cắt bỏ ñi những phương án (nhánh) không cần thiết, do ñó việc tìm nghiệm tối ưu sẽ nhanh hơn. Cái khó nhất trong việc áp dụng phương pháp nhánh và cận là ñánh giá ñược các nghiệm mở rộng, nếu ñánh giá ñược tốt  sẽ giúp bỏ qua ñược nhiều phương án không cần thiết, khi ñó thuật toán nhánh cận sẽ chạy nhanh hơn nhiều so với thuật toán vét cạn.
Thuật toán nhánh cận có thể mô tả bằng mô hình ñệ quy sau:

procedure BranchBound(i);// xây dựng thành phần thứ i
begin
<ðánh giá các nghiệm mở rộng>;
if(các nghiệm mở rộng ñều không tốt hơn
BestSolution)then exit;
<Xác ñịnh S
i>;
for x
i $ Si do begin
<ghi nhận thành phần thứ i>;
if (tìm thấy nghiệm) then <Cập nhật BestSolution>
else BranchBound(i+1);
<loại thành phần i>;
end;
end;

2. Cách giải

1) Hành trình cần tìm có dạng (x1 = 1, x2, …, xn, xn+1 = 1), ở ñây giữa xi và xi+1: hai thành phố liên tiếp trong hành trình phải có ñường ñi trực tiếp; trừ thành phố 1, không thành phố nào ñược lặp lại hai lần, có nghĩa là dãy (x1, x2, …, xn) lập thành một hoán vị của (1, 2, …, n).
2) Duyệt quay lui: x
2 có thể chọn một trong các thành phố mà x1 có ñường ñi trực tiếp tới, với mỗi cách thử chọn x2 như vậy thì x3 có thể chọn một trong các thành phố mà x2 có ñường ñi tới (ngoài x1). Tổng quát: xi có thể chọn 1 trong các thành phố chưa ñi qua mà từ xi-1 có ñường ñi trực tiếp tới.(2 i n).
3) Nhánh cận: Khởi tạo cấu hình BestSolution có chi phí = +
. Với mỗi bước thử chọn xi xem chi phí ñường ñi cho tới lúc ñó có nhỏ hơn chi phí của cấu hình BestSolution không? nếu không nhỏ hơn thì thử giá trị khác ngay bởi có ñi tiếp cũng chỉ tốn thêm. Khi thử ñược một giá trị xn ta kiểm tra xem xn có ñường ñi trực tiếp về 1 không ? Nếu có ñánh giá chi phí ñi từ thành phố 1 ñến thành phố xn cộng với chi phí từ xn ñi trực tiếp về 1, nếu nhỏ hơn chi phí của ñường ñi BestSolution thì cập nhật lại BestSolution bằng cách ñi mới.


Chương trình


(theo Tài liệu giáo khoa chuyên Tin học – quyển 1 – trang 73)

program TSP;
const MAX =20;
oo =1000000;
fi =’d:\TSP.INP’;
fo =’d:\TSP.OUT’;
var c :array[1..MAX,1..MAX]of longint;
x,bestSolution :array[1..MAX]of longint;
d :array[1..MAX]of longint;
n :longint;
sum,best :longint;
procedure input;
var f :text;
i,j,k :longint;
begin
assign(f,fi); reset(f);
read(f,n);
for i:=1 to n do
for j:=1 to n do read(f,C[i,j]);
close(f);
end;
procedure update;
begin
if sum+C[x[n],x[1]]=best then exit;
for j:=1 to n do
if d[j]=0 then begin
x[i]:=j;
d[j]:=1;
sum:=sum + C[x[i-1],j];
if i=n then update
else branchBound(i+1);
sum:=sum – C[x[i-1],j];
d[j]:=0;
end;
end;

procedure init;
begin
fillchar(d,sizeof(d),0);
d[1]:=1;
x[1]:=1;
best:=oo;
end;

procedure output;
var f :text;
i :longint;
begin
assign(f,fo); rewrite(f);
writeln(f,best);
for i:=1 to n do write(f,bestSolution[i],’->’);
write(f,bestSolution[1]);
close(f);
end;
BEGIN
input;
init;
branchBound(2);
output;
END.

Bộ test

4
0 20 35 42
20 0 34 30
35 34 0 12
42 30 12 0

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: