Phần 1: ĐẶT VẤN ĐÊ
Kính thưa quý thầy cô giáo!
Tiến sĩ triều Lê, Thân Nhân Trung đã nói “Hiền tài là nguyên khí của
quốc gia, nguyên khí thịnh thì thế nước mạnh mà hưng thịnh, nguyên khí
suy thì thế nước yếu mà thấp hèn”. Vì thế các bậc đế vương thánh minh
luôn coi việc giáo dục nhân tài, kén chọn kẻ sĩ, vun trồng nguyên khí quốc
gia làm công việc hàng đầu..., câu nói bất hủ của Thân Nhân Trung đã cho
thấy từ thời xa xưa các thế hệ ông cha đã rất coi trọng nhân tài và coi
những nhân tài là tương lai của đất nước. Với cương vị là một giáo viên
chuyên ngành Tin học trực tiếp giảng dạy, tôi thấy được những nhiệm vụ
quan trọng phải làm đầu tiên đó là làm thế nào để học sinh thích học và học
giỏi môn Tin. Trong thời đại ngày nay, Tin học có vai trò và vị trí đặc biệt
quan trọng trong khoa học kĩ thuật và đời sống, giúp con người tiếp thu một
cách dễ dàng các môn khoa học khác có hiệu quả.
Có thể nói phát hiện và bồi dưỡng HSG là một trong những hoạt
động chuyên môn chính trong năm học của trường. Bản thân qua tham
khảo các đề thi HSG của tỉnh và quốc gia đã thấy hầu hết các đề thi đều có
các bài toán tối ưu. Để giải các bài toán tôi ưu thì có nhiều phương pháp
giải, trong đó ứng dụng thuật toán quay lui để giải bài toán tối ưu cũng là
một phương pháp được nhiều người sử dụng. Đó cũng chính là lý do để tôi
viết đề tài “Thuật toán quay lui và ứng dụng giải bài toán tối ưu”.
Tôi rất mong được sự góp ý của quý thầy cô để đề tài ngày càng được
hoàn thiện hơn.
Xin chân thành cảm ơn!

Trang 1


Phần 2: NHỮNG BIỆN PHÁP GIẢI QUYẾT VẤN ĐÊ
I. CƠ SỞ LÝ LUẬN CỦA VẤN ĐÊ:
Cũng như trình bày ở trên bài toán tối ưu là một trong những bài toán

lòng nhiệt tình trong công việc. Luôn luôn học tập trau dồi tri thức,
nhằm phục vụ tốt nhất cho sự nghiệp giáo dục.
- Trong quá trình giảng dạy, tuy gặp nhiều khó khăn nhưng
phần lớn các thầy cô giáo đều đặt chữ “tâm” lên hàng đầu, đây là
một trong những thuận lợi góp phần vào sự thành công của ngành
giáo dục.
- Có sự đầu tư vào nghiên cứu khi được giao nhiệm vụ.
*) Hạn chế:
Một số giáo viên không có tâm huyết, chưa tập trung vào công
tác chuyên môn nên kiến thức về ôn luyện học sinh giỏi còn hạn chế.
Việc bồi dưỡng HSG chỉ tập trung cho số ít giáo viên trong tổ.
3) Thực trạng về học sinh
*) Ưu điểm:
- Các em HS ngoan, cần cù chịu khó, có ý thức vươn lên trong
học tập.
- Có trách nhiệm với việc học tập, trong quá trình học tập hăng
say phát biểu, đóng góp nên sự thành công của bài giảng.
*) Hạn chế:
- Kiến thức cơ bản về lập trình còn rất nhiều hạn chế, chỉ có số
ít em học sinh trên địa bàn thị trấn, mới được tiếp cận với lập trình ở
chương trình lớp 8 – THCS.
- Đa số các em học tốt môn Tin học thì lại học tốt các môn
khoa học tự nhiên (Toán, Lí, Hóa), nên đã theo tham gia bồi dưỡng ở
các bộ môn đó.
- Tin học là môn mà không có trong các kỳ thi tốt nghiệp cũng
như đại học hàng năm, nên các em cũng không mặn mà với việc
tham gia học và bồi dưỡng HSG.

Trang 3




if i=n then <Ghi nhận một cấu hình>
Else try(i+1);
End;
End;
2. Ứng dụng thuật toán quay lui giải một số bài toán cơ bản:
Bài 1: Hãy viết chương trình liệt kê tất cả các dãy nhị phân có độ dài n.
Bài 2: Hãy viết chương trình liệt kê các hoán vị của {1,2,...,n}
Bài 3: Hãy viết chương trình liệt kê các tổ hợp chập m của {1,2,...,n}
Bài 4: Liệt kê tất cả các cách sắp xếp những con hậu trên bàn cờ NxN sao
cho chúng không ăn được nhau.
Bài 5: Hãy viết chương trình liệt kê tất cả các chu trình Haminton của đơn
đồ thị vô hướng. (Chu trình bắt đầu từ đỉnh v nào đó qua tất cả các đỉnh
còn lại, mỗi đỉnh đúng một lần rồi quay trở về đỉnh v được gọi là chu trình
Hamilton).
(*Bài 1: Hãy viết chương trình liệt kê tất cả các dãy nhị phân có độ dài
n.*)
Giải: Biểu diễn dãy nhị phân dưới dạng b 1,b2,...,bn trong đó bi{0,1}. Thủ
tục đệ quy Try(i) xác định bi, trong đó các giá trị đề cử là 0 và 1. Các giá trị
này mặc nhiên được chấp nhận mà không phải thỏa mãn điều kiện gì (vì
vậy bài toán không cần biến trạng thái). Thủ tục Init nhập giá trị n và khởi
gán biến đếm Count. Thủ tục result đưa ra dãy tìm được.
Program Day_nhi_phan;
Uses Crt;
Var b:array[1..20] of 0..1;
n:Integer; count:byte;
Procedure Init;
Begin
Write('Nhap n='); readln(n);

trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy cần được
ghi nhớ đối với mỗi giá trị j xem nó đã được dùng hay chưa. Điều này được
thực hiện nhờ một dãy biến logic b j, trong đó bj bằng True nếu j chưa được
Trang 6


dùng. Các biến này cần được gán giá trị True trong thủ tục Init. Sau khi gán
j cho pi cần ghi nhận False cho b j và phải gán lại giá trị True sau khi thực
hiện xong Result.
Program Liet_ke_hoan_vi;
Uses Crt;
Var n:Integer;
p:array[1..20] of integer;
b:array[1..20] of boolean;
Count:Word;
Procedure Init;
Var i:Integer;
Begin
Write('Nhap n='); readln(n);
For i:=1 to n do b[i]:=true;
count:=0;
End;
Procedure Result;
Var i:integer;
Begin
Count:=count+1;
Write(Count:5,'.');
For i:=1 to n do write(p[i]:3);
Writeln;
End;

Program Liet_ke_to_hop;
Uses Crt;
Var n,m:integer;
c:array[0..20] of integer;
count:word;
Procedure Init;
Trang 8


Begin
Write('n,m='); readln(n,m);
c[0]:=0; Count:=0;
End;
Procedure result;
Var i:integer;
Begin
Count:=count+1;
Write(Count:5,'.');
For i:=1 to m do write(c[i]:3);
writeln;
End;
Procedure Try(i:integer);
Var j:integer;
Begin
For j:=c[i-1]+1 to n do
Begin
C[i]:=j;
if i=m then result Else try(i+1);
End;
End;

con hậu thứ i được chấp nhận xếp vào cột j nếu nó thoả mãn cả ba biến
a[j],b[i+j],c[i-j] đều có giá trị true. Các biến này gán giá trị False khi xếp
xong con hậu thứ i, và trả lại giá trị true sau khi gọi Result hay Try(i+1). Ta
có chương trình Pascal sau:
Program XepHau;
Uses crt;
Var

n : integer;

x:array[1..30] of integer;
a:array[1..30] of boolean;
b:array[2..60]of boolean;
Trang 10


c:array[-19..19] of boolean;
count:word;
Procedure Init;
Var i:integer;
Begin
Write('Cho do rong ban co n= ');
Readln(n);
Count:=0;
For i:=1 to n do a[i]:=true;
For i:=2 to 2*n do b[i]:=true;
For i:=1-n to n-1 do c[i]:=true;
End;
Procedure Result;
Var i:integer;

END.
(*Bài 5: Hãy viết chương trình liệt kê tất cả các chu trình Haminton
của đơn đồ thị vô hướng *)
Giải:
Program Chutrinhhamilton;
Const max=100;
var

f:Text;
a:array[1..max, 1..max] of Boolean;
Chuaxet:array[1..max] of Boolean;
X:array[1..max] of Integer;
n:Integer;

procedure Enter;
var i,u,v,m: Integer;
Begin
FillChar(a,SizeOf(a),False);{tạo ra 1 mảng được gán, in ra là false}
ReadLn(f1,n,m);
for i:=1 to m do
Trang 12


begin
ReadLn(f1,u,v);
a[u,v]:=True; a[v,u]:=True;
end;
end;
procedure PrintResult;
var i:Integer;

x[1]:=1; Chuaxet[1]:=False;
Try(2);
Close(F1);
Close(F2);
END.

Trang 14


3. Phương Pháp Nhánh Cận (Branch and Bound)
(Bài toán cái túi và bài toán người du lịch)
a. Nội dung:
 Đặt vấn đề
 Ý tưởng
 Thuật giải
 Cài đặt
 Đánh giá
 Ví dụ minh họa
b. Đặt vấn đề:
 Bài toán thực tế: Bài toán người giao hàng.
 Một người cần phải giao hàng tại N thành phố T1, T2, …, Tn.
 Cij: chi phí đi từ thành phố Ti đến thành phố Tj (i=1,2,…,N; j = 1,2,
…,N).
 Yêu cầu: xác định hành trình thỏa mãn đi qua tất cả các thành phố,
mỗi thành phố qua đúng 1 lần, rồi quay trở lại thành phố xuất phát.
Chi phí nhỏ nhất.
Cách 1 giải quyết bài toán:
 Phương pháp vét cạn.
 Phương pháp vét cạn quay lui .
 Một số phương pháp khác.

for ( j=1->n ) if ( chấp nhận được j) {Xác định xi theo j; Ghi nhận trạng
thái mới}
if ( i=n ) Cập nhật lời giải tối ưu
Else { Xác định cận g(x1,…,xi); if ( g(x1,…,xi) < f* ) Try(i+1)}}}
f. Đánh giá:
Ưu điểm: Giảm được chi phí: do loại bỏ được những bước đi không cần
thiết (nhờ đánh giá cận).

Trang 16


Nhược điểm:Việc xây dựng hàm g phụ thuộc vào từng bài toán tối ưu tổ
hợp cụ thể. Hàm g phải đảm bảo điều kiện:
 Việc tính giá trị của g phải đơn giản hơn việc giải bài toán tổ hợp tìm
min= min{f (a): a=(a1 ,…,an) thuộc x, xi =ai , i=1,…,n}
 Giá trị của g(a1, a2 ,…, ak) phải sát với các giá trị của min.
g. Ví dụ minh họa:
Bài 1: Bài toán cái túi
Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không
quá b. Có n đồ vât có thể mang theo (số lượng mỗi loại là không hạn chế).
Đồ vật thứ j có trọng lượng aj và giá trị sử dụng cj (j=1,2,...,n). Hỏi nhà
thám hiểm cần đem theo những loại đồ vật nào, số lượng mỗi loại là bao
nhiêu để cho tổng giá trị sử dụng của các đồ vật đem theo là lớn nhất?
Mô hình toán học của bài toán có dạng sau: Tìm
n

n

j 1


Const inf=25000;
Type arrn=array[1..50] of integer;
arrnl=array[1..50] of real;
Var c,a

: arrnl;

x,xopt, ind : Arrn;
n

: Integer;

w,fopt,cost,weight: Real;
Procedure Khoitao;
Var i,j,tg: integer;
t:real;
Begin
Fopt:=0; Weight:=0; {Tong gia tri, trong luong ban dau cua tui la 0 }
For i:=1 to n do ind[i]:=i; {Ghi nhan thu tu ban dau cua cac do vat }
(* Sap xep do vat theo thu tu khong tang cua c[i]/a[i] nham som tim thay
cau hinh tot nhat*)
For i:=1 to n-1 do
Begin
For j:=i+1 to n do
if (c[i]/a[i]
Begin
xopt:=x; {Ghi nhan cau hinh do vat moi}
Fopt:=cost;{Ghi nhan gia tri moi cua tui}
End;
End;
Procedure Nhanh_can(i:integer);
Trang 20


Var j,t:integer;
Begin
t:=trunc((w-weight)/a[i]); {Trong luong con lai cua tui co the chua bao
nhieu do vat thu i}
For j:=t downto 0 do
Begin
x[i]:=j;
weight:=weight+a[i]*x[i];
Cost:=cost+c[i]*x[i];
if i=n then Ghinhan_ky_luc
Else
if cost+c[i+1]*(w-weight)/a[i+1]> fopt then Nhanh_can(i+1);
weight:=weight-a[i]*x[i];
Cost:=cost-c[i]*x[i];
End;
End;
Procedure Inkq;
Var i,j:integer;
Begin
Writeln('********** KET QUA TINH TOAN ***********');
Writeln('Tong gia tri cua cac do vat: ', fopt:4:0);


8

15

3

5

4

6

********KET QUA TINH TOAN*********
Tong gia tri cua cac do vat:

120

Phuong an lay do:
So luong do vat 1 la: 6 lan.
So luong do vat 4 la: 0 lan.
So luong do vat 3 la: 0 lan.
So luong do vat 2 la: 0 lan.
********************************************
Bài 2: Bài toán người du lịch
Một người du lịch muốn đi tham quan n thành phố T1, T2,..., Tn. Xuất
phát từ một thành phố nào đó người du lịch muốn đi qua tất cả các thành
phố còn lại, mỗi thành phố đúng một lần, rồi quay lại thành phố xuất phát.
Cij là chi phí đi từ thành phố T i đến thành phố Tj (i,j=1,2,...,n), hãy tìm một


a,xopt

:array[1..20] of integer;

chuaxet

:array[1..20] of boolean;

n,fopt,cmin,can

:integer;

Procedure readfile;
Var f

:Text;

Name :String;

Trang 23


i,j

:integer;

Begin
Write('Nhap ten file du lieu:');
Readln(Name);
Assign(f,name);

(* Duyet (n-1)! hanh trinh theo nhanh can*)
For j:=2 to n do
if chuaxet[j] then
Begin
a[i]:=j;

{Mang a dung de ghi nhan duong di}

chuaxet[j]:=False;
can:=can+c[a[i-1],a[i]];
if i=n then ghinhan
Else
if Can+(n-i+1)*Cmin