MỞ ĐẦU
1. Tính cấp thiết của đề tài
Chương trình đào tạo và bồi dưỡng học sinh có năng khiếu
Toán, Tin học bậc Trung học phổ thông đã được thực hiện trong
nhiều năm qua. Qua những năm thực hiện nó như là một chu trình
đặc biệt gắn với sự trưởng thành và hoàn thiện một mô hình đào tạo
đặc biệt. Đó là đào tạo mũi nhọn, đào tạo các thế hệ học sinh có năng
khiếu trong lĩnh vực Toán học, Tin học. Lớp lớp các thế hệ thầy và
trò đã dũng cảm đi lên, tìm tòi và sáng tạo để tiếp cận với thế giới
hiện đại, cập nhật thông tin và nghiên cứu các phương pháp. Gắn với
việc đổi mới phương pháp dạy và học của chương trình đào tạo
chuyên, ngành Giáo dục và Đào tạo đang tích cực đổi mới phương
pháp dạy và học để đào tạo những thế hệ học sinh giỏi có kết quả cao
trong các kỳ thi học sinh giỏi cấp Quốc gia và giành được nhiều huy
chương trong các kỳ thi Olympic quốc tế mà trong đó có kỳ thi
Olympic Tin học.
Có thể nói, giáo dục mũi nhọn phổ thông đã thu được những
thành tựu rực rỡ, được Nhà nước đầu tư có hiệu quả, xã hội thừa
nhận và bạn bè quốc tế khâm phục. Các đội tuyển quốc gia tham dự
các kỳ thi olympic quốc tế có bề dày thành tích mang tính ổn định và
có tính kế thừa. Đặc biệt, đội tuyển Tin học quốc gia tham dự thi
Olympic quốc tế đã đạt được nhiều thành tích nỗi bật. Tuy ra đời
muộn hơn hệ chuyên Toán nhưng hệ THPT chuyên Tin học đã sớm
khẳng định vị thế của mình, đang trên đà hoàn thiện và phát triển
đúng hướng.
Để nâng cao chất lượng đào tạo mũi nhọn khối chuyên Tin học
trường THPT Chuyên Quảng Bình các thầy cô giáo luôn luôn cố
1
gắng đổi mới phương pháp, xây dựng các chuyên đề dạy và học các
thuật toán trong tin học để nâng cao chất lượng cũng như hiệu quả
giáo dục. Để giải quyết tốt bài toán thì học sinh cần phải có một số

quan trọng trong việc tiếp cận bài toán, tìm và thiết kế thuật toán.
3. Đối tượng và phạm vi nghiên cứu
Tìm hiểu phương pháp nhánh cận, mục tiêu và kế hoạch dạy
học chương trình chuyên sâu môn tin học để thực hiện việc đổi mới
phương pháp trong việc dạy học thuật toán tại trường THPT Chuyên
Quảng Bình. Trên cơ sở đó tiến phân tích và thiết kế thuật toán và cài
đặt các bài toán tiểu biểu có thể giải được bằng phương pháp nhánh
cận. Các bài toán được cài đặt chương trình bằng ngôn ngữ lập trình
Free Pascal để minh họa quá trình thực hiện thuật toán.
4. Phương pháp nghiên cứu
Bài toán đặt ra trong thực tế yêu cầu tìm ra một nghiệm thỏa
mãn một số điều kiện nào đó và nghiệm đó là tốt nhất theo một chỉ
tiêu cụ thể, đó là lớp bài toán tối ưu. Nghiên cứu lời giải các lớp bài
toán tối ưu thuộc về lĩnh vực quy hoạch toán học.
Tuy nhiên cũng cần phải nói rằng trong nhiều trường hợp
chúng ta chưa thể xây dựng một thuật toán nào thực sự hữu hiệu để
giải bài toán tối ưu, mà cho tới nay việc tìm nghiệm của chúng vẫn
phải dựa trên mô hình liệt kê toàn bộ các cấu hình có thể và đánh giá,
tìm ra cấu hình tốt nhất. Việc tìm cấu hình theo cách này còn có tên
gọi là vét cạn. Chính nhờ kỹ thuật này cùng với sự phát triển của
máy tính điện tử mà nhiều bài toán khó đã tìm thấy lời giải.
Mô hình thuật toán quay lui là tìm kiếm trên một cây phân
cấp. Nếu giả thiết rằng mỗi nút nhánh của cây chỉ có 2 nút con thì
cây có độ cao n sẽ có tới 2
n
nút lá, con số này lớn hơn rất nhiều lần
3
so với kích thước dữ liệu đầu vào n. Chính vì vậy mà nếu như ta có
thao tác thừa trong việc chọn x
i

4
Chương 3: Sử dụng phương pháp nhánh cận giải một số bài
toán tiêu biểu.
Nội dung của chương là phát biểu các bài toán, phân tích và
thiết kế thuật toán, cài đặt chương trình cho các bài toán.
6. Tổng quan tài liệu tham khảo
Khi triển khai nghiên cứu đề tài tôi đã tham khảo các tài liệu
về toán rời rạc, lý thuyết đồ thị, cấu trúc dữ liệu và giải thuật, toán
ứng dụng, các giải thuật nâng cao và ngôn ngữ lập trình Turbo
Pascal.
5
CHƯƠNG 1
PHƯƠNG PHÁP NHÁNH CẬN
1.1. KỸ THUẬT ĐỆ QUY
1.1.1. Thuật toán quay lui
Thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình.
Thuật toán này làm việc theo cách:
- Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử.
- Mỗi phần tử được chọn bằng cách thử tất cả các khả năng.
Giả sử cấu hình hình cần liệt kê có dạng x
1
, x
2
, … x
n
, khi đó
thuật toán quay lui sẽ xét tất cả các giá trị x
1
có thể nhận, thử cho x
1

«Nếu cần, bỏ ghi nhận việc thử x[i] := v để thử giá
trị khác»;
end;
End;
1.1.2. Giải bài toán bằng cách sử dụng Đệ quy quay lui
1.2. PHƯƠNG PHÁP NHÁNH CẬN
1.2.1. Bài toán tối ưu tổ hợp
Trong rất nhiều vấn đề ứng dụng thực tế của tổ hợp, các cấu
hình của tổ hợp còn được gán cho một giá trị bằng số đánh giá giá trị
sử dụng của cấu hình đối với mục đích sử dụng cụ thể nào đó.
Khi đó xuất hiện bài toán: Hãy lựa chọn trong số các cấu hình
tổ hợp chấp nhận được cấu hình có giá trị sử dụng tốt nhất. Các bài
toán như vậy chúng ta sẽ gọi là bài toán tối ưu tổ hợp.
Dạng tổng quát bài toán tối ưu tổ hợp phát biểu như sau:
Tìm cực tiểu (hay cực đại) của hàm
( )
min(max),f x
→
với
điều kiện
x D
∈
, trong đó
D
là tập hữu hạn các phần tử.
Hàm
( )
f x
được gọi là hàm mục tiêu của bài toán, mỗi phần tử
x D

∈ ⊂
,
trong đó D là tập hữu hạn phần tử, là miền các phương án; x là
một phương án thuộc miền D.
Phương pháp nhánh cận được mô tả như sau:
Từ miền D ta phân nhánh thành hai miền D
1
, D
2
, trên mỗi
nhánh ta xây dựng hàm g xác định trên các miền D
1
, D
2
để tính giá trị
cận dưới.
Gọi
1
β
là cận dưới của nhánh D
1
, gọi
2
β
là cận dưới của
nhánh D
2
.
So sánh giá trị các cận dưới
1

. Tương tự
ta gọi Gọi
11
β
là cận dưới của nhánh D
11
, gọi
12
β
là cận dưới của
nhánh D
12
. Lại tiếp tục so sách các giá trị cận dưới
11
β
và
12
β
để
chọn nhánh cần phát triển trong bước tiếp theo. Quá trình trên cứ lặp
đi lặp lại cho đến khi không thể phân nhánh được nữa, lúc này ta có
phương án tối ưu tạm thời trong quá trình tìm nghiệm của bài toán.
Gọi
*
β
là nghiệm tối ưu tạm thời, lúc này thuật toán nhánh
cận sẽ tiếp tục với những nhánh còn lại sao cho giá trị của hàm g tại
đó nhỏ hơn
*
β

<Cập nhật kỷ lục>
else
if
( )
1 2 k
, , ,g a a a
…
≤
f
then
Try(k+1)
End;
End;
Khi đó thuật toán nhánh cận được thực hiện nhờ thủ tục sau:
Procedure Nhanh_can;
Begin

f
= +∞;
(* Nếu biết một phương án
x
nào đó thì có thể đặt
f
=
( )
f x
*)
Try(1);
if
f

để học sinh năm bắt được kiến thức thông qua ví dụ.
Khi dạy học sinh lập trình giải các bài toán đưa ra ở chương 3
giáo viên cho học sinh thực hiện quy trình như sau:
- Phát biểu bài toán;
- Học sinh xây dựng thuật toán và cài đặt chương trình trong
một lượng thời gian cụ thể (do giáo viên quy định theo trình độ học
sinh);
10
- Giáo viên chấm bài của học sinh bằng cách tạo ra những bộ
dữ liệu vào và đối sánh kết quả giữa giáo viên và học sinh;
- Nhận xét bài làm của học sinh sau đó trình bày thuật toán
nhánh cận để giải bài toán đặt ra.
- Yêu cầu học sinh cài đặt lại chương trình và tiếp tục chấm
kiểm tra kết quả của học sinh sau khi hoàn thành chương trình.
2.4.2 Tiến trình tự học của học sinh
Ngoài việc học ở lớp học sinh còn có thể tự học phương pháp
nhánh cận thông qua tài liệu và đánh giá chương trình của mình bằng
các bộ dữ liệu vào ra của giáo viên hoặc tự tạo ra các bộ dữ liệu để
đối sánh kết quả khi thực hiện chương trình của mình và chương
trình mẫu của giáo viên.
Kiểm tra bằng các bộ dữ liệu vào ra của giáo viên: Với các bộ
dữ liệu vào giáo viên đã tạo sẵn, học sinh chạy chương trình của
mình để sinh các bộ dữ liệu ra tương ứng. So sánh các bộ dữ liệu ra
của mình với các bộ dữ liệu ra của giáo viên, nếu kết quả giống nhau
thì chương trình cài đặt hoàn thành, còn nếu một bộ dữ liệu ra nào đó
không giống thì cần cải tiến lại chương trình.
Học sinh cũng có thể tạo ra các bộ dữ liệu vào theo yêu cầu
của bài toán, thực hiện chương trình của mình để tạo các bộ dữ liệu
ra, đồng thời cũng thực hiện chương trình mẫu của giáo viên để tạo
các bộ dữ liệu ra tương ứng. Đối sánh kết quả để kiểm chứng chương

cận dưới nhỏ hơn giá trị hàm mục tiêu tìm được.
Kỹ thuật tính cận dưới dựa trên thủ tục rút gọn sau:
a. Thủ tục rút gọn:
Rõ ràng tổng chi phí của một hành trình sẽ chứa đúng một
phần tử trên mỗi dòng và mỗi cột của ma trận chi phí C = (c
ij
). Do
đó nếu ta trừ bớt mỗi phần tử của một dòng (hay một cột) đi cùng
một giá trị thì chi phí của tất cả hành trình sẽ giảm đi một lượng, vì
thế hành trình tối ưu sẽ không thay đổi. Vì vậy nếu tiến hành trừ bớt
các phần tử của mỗi dòng và mỗi cột đi một hằng số sao cho thu
được ma trân không âm và mỗi cột cũng như mỗi dòng chứa ít nhất
một số 0, thì tổng các hằng số trừ đi đó sẽ cho ta cận dưới của mọi
hành trình. Thủ tục trừ bớt này gọi là thủ tục rút gọn, các hằng số trừ
ở mỗi dòng (cột) gọi là hằng số rút gọn dòng (cột), ma trận thu được
gọi là ma trận rút gọn.
Thủ tục rút gọn:
+ Đầu vào : Ma trận chi phí C = (c
ij
)
+ Đầu ra : Ma trận rút gọn và tổng hằng số rút gọn Sum
+ Thuật toán:
i) Khởi tạo :
Sum := 0 ;
(ii) Rút gọn dòng :
Với mỗi dòng r từ 1 đến n của ma trận C thực hiện:
- Tìm phần tử c
rj
= α nhỏ nhất trên dòng.
- Trừ tất cả các phần tử trên dòng đi một lượng α.

Bài toán thực hiện N-2 lệnh gọi TSP. Mỗi TSP có hai thủ tục
chính là Reduce và BestEdge.
Vì 2 thủ tục này thực hiện ở nhánh khác nhau. Do vậy, độ
phức tạp tính toán thời gian của mỗi TSP là:
Áp dụng công thức max, ta có:
T
TSP
= Max(T
Reduce,
T
BestEdge
) = Max(O(n
2
), O(n
3
)) = O(n
3
).
Vậy độ phức tạp tính toán thời gian của bài toán TSP là:
O(K * N * N
3
) K là số lần có thể phân nhánh, 0 <= K <= N
2
3.1.4 Cài đặt thuật toán
Chương trình được cài đặt hoàn thành bằng ngôn ngữ lập trình
Free Pascal bao gồm file chương trình nguồn (TOURISM.PAS), file
14
dữ liệu vào (TOURISM.INP), và file dữ liệu ra (TOURISM.OUT).
Các file dữ liệu vào (*.INP) và file dữ liệu ra (*.OUT) bao gồm 20
bộ dùng để kiểm tra chương trình đã được cài đặt, đồng thời các bộ

Ban đầu: SumW := 0;
SumV := 0;
MaxV := -1;
Sắp xếp các v
i
/w
i
giảm dần.
15
Ta xây dựng hàm UpperBound(k, m): ước lượng xem nếu
chọn trong các sản phẩm từ k tới n với giới hạn trọng lượng m thì
tổng giá trị thu được không thể vượt quá bao nhiêu? Giá trị hàm
UpperBound(k, m) được tính như sau:
Function UpperBound(k: Integer; m: Real): Real;
Var i: Integer; q: Real;
Begin
Result := 0;
For i := k to n do //Xét các sản phẩm từ k tới n
Begin
if w[i] ≤ m then
q := w[i] //Lấy toàn bộ sản phẩm
Else
q := m; //Lấy một phần sản phẩm cho vừa đủ giới hạn
trọng lượng
Result := Result + q / w[i] * v[i]; //Cập nhật tổng giá trị
m := m – q; //Cập nhật giới hạn trọng lượng mới
if m = 0 then Break;
End;
End;
Mỗi khi chuẩn bị ra quyết định chọn hay không chọn sản phẩm

gian duyệt. Tiêu chuẩn này có thể viết bằng hàm Selectable(j, k), (j <
k): Cho biết có thể nào chọn sản phẩm k trong điều kiện ta đã quyết
định chọn hay không chọn trên các sản phẩm từ 1 tới j:
Function Selectable(j, k: Integer): Boolean;
Var i: Integer;
Begin
For i := 1 to j do
If not x[i] and (w[i] ≤ w[k]) and (v[i] ≥ v[k]) //Sản
phẩm i không được chọn và i "không tồi hơn" k then
Exit(False); //Kết luận k chắc chắn không được chọn
Result := True;
End;
17
Hàm Selectable sẽ được dùng trong thủ tục quay lui, đồng thời
tích hợp vào hàm UpperBound để có một đánh giá cận chặt hơn.
Thủ tục chính để chọn phần tử thứ i đưa vào ba lô.
Procedure Attempt(i: Integer);
Begin
// Ước lượng xem các phần tử từ i đến n có vượt quá kết quả tốt nhất
hiện tại hay không.
if SumV + UpperBound(i, m - SumW) <= MaxV then Exit;
// Duyệt xong n phần tử, lưu trạng thái tốt nhất.
if i = n + 1 then Begin Best := x; MaxV :=SumV; Exit; End;
// Nếu phần tử i được chọn
if (SumW + obj[i].w <= m) and Selectable(i - 1, i) then
Begin
X[i] := True; // Đánh dấu phần tử i được chọn
SumW := SumW + obj[i].w; // Tổng trọng lượng trong lần xét hiện
tại
SumV := SumV + obj[i].v; // Tổng giá trị trong lần xét hiện tại

cài đặt của học sinh trong quá trình dạy - học.
3.3. BÀI TOÁN ĐỒ THỊ CON ĐẦY ĐỦ CỰC ĐẠI
3.3.1 Phát biểu bài toán
Định nghĩa: Đồ thị đầy đủ có hướng là đơn đồ thị mà hai
đỉnh bất kỳ được nối với nhau bằng một cung (theo chiều nào cũng
được). Đồ thị đầy đủ vô hướng là đơn đồ thị mà hai đỉnh bất kỳ
được nối với nhau bằng một cạnh. Ta có số cạnh của đồ thị đầy đủ
vô hướng với N đỉnh là N*(N-1)/2 cạnh.
19
Bài toán tìm đồ thị con đầy đủ cực đại là một bài toán có rất
nhiều ứng dụng trong các mạng xã hội, tin sinh học, mạng truyền
thông, nghiên cứu cấu trúc phân tử…
Ta có thể phát biểu bài toán như sau:
Có n người và mỗi người có quen biết một số người khác. Giả
sử quan hệ quen biết là quan hệ hai chiều, tức là nếu người i quen
người j thì người j cũng quen người i và ngược lại.
Yêu cầu: Hãy chọn ra một tập gồm nhiều người nhất trong số
n người đã cho để hai người bất kỳ được chọn phải quen biết nhau.
3.3.2 Thuật toán
Ta xây dựng thuật toán như sau:
A[i, j] = True ⇔ Người i và người j có quan biết với nhau.
deg[i] là số người quen của người i
count[i] là số người quen của người i mà đã được chọn.
X[i] = True ⇔ Người i được chọn trong lần xét hiện tại.
best[i] = True ⇔ Người i được chọn trong kết quả tốt nhất.
k số người được chọn trong lần xét hiện tại.
kbest là số người được chọn trong kết quả tốt nhất.
Các quan hệ quen biết nhau được biểu diễn bởi ma trận A =
{a
ij

trí x
i
= True.
20
Phương án tối ưu được lưu trữ bởi mảng best[1 n] với kbest
là số người được chọn tương ứng với dãy best. Để đơn giản, ta khởi
tạo mảng best[1 n] bởi giá trị False và kbest := 0, sau đó phương án
best và biến kbest sẽ được thay bằng những phương án tốt hơn trong
quá trình duyệt.
Mô hình duyệt được thiết kế như mô hình liệt kê các dãy nhị
phân bằng thuật toán quay lui: Thử hai giá trị True/False cho x
1
, với
mỗi giá trị vừa thử cho x
1
lại thử hai giá trị của x
2
…
Giá trị deg[i] được xác định ngay từ đầu còn giá trị count[i]
sẽ được cập nhật ngay lập tức mỗi khi ta thử quyết định chọn hay
không chọn một người j quen với người i (j < i). Mảng deg[1 n] và
count[1 n] được sử dụng trong hàm cận để hạn chế bớt không gian
duyệt.
+ Hàm cận:
Thuật toán nhánh cận được thực hiện thông qua thử tục
Attempt(i): Thử hai giá trị có thể gán cho x
i
. Thuật toán được bắt đầu
bằng thủ tục Attempt(1) và khi thủ tục Attempt(i) được gọi thì ta đang
có một phương án chọn trên tập những người từ 1 tới i - 1 và số

// Tăng số lượng người quen của các người có quen người i
For j := i + 1 to n do
if a[i, j] then Inc(count[j]);
Attempt(i + 1); // Duyệt kiểm tra người tiếp theo
X[i] := False; // Loại bỏ người i ra khỏi kết quả hiện tại
Dec(k);
// Giảm số lượng người được chọn
// Giảm số lượng người quen của các người có quen người i
For j := i + 1 to n do
22
if a[i, j] then Dec(count[j]);
End;
End;
3.3.3 Độ phức tạp của thuật toán
Từ thuật toán nêu trên ta đi đi tìm độ phức tạp tính toán của
bài toán như sau:
Lần gọi chương trình con Attempt(1): Có N-1 cách chọn.
Lần gọi chương trình con Attempt(2): Có N-2 cách chọn.
Lần gọi chương trình con Attempt(i): Có N-i+1 cách chọn.
Lần gọi chương trình con Attempt(N): Có 1 cách chọn.
Gọi T(i) là độ phức tạp tính toán thời gian ở lần gọi
Attempt(i). T(i) = N – i + 1;
Gọi T là độ phức tạp tính toán thời gian của bài toán.
Theo nguyên lý nhân, ta có:
T = T(2) * T(3) * * T(N) = (N – 1) * (N – 2) * * 1 = (N – 1)!
Vậy độ phức tạp tính toán thời gian của bài toán là O((N-1)!)
3.3.4 Cài đặt thuật toán
Chương trình được cài đặt hoàn thành bằng ngôn ngữ lập trình
Free Pascal bao gồm file chương trình nguồn (SUBGRAPH.PAS),
file dữ liệu vào (SUBGRAPH.INP), và file dữ liệu ra