Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Phạm Chí Hiếu

PHÁT TRIỂN
CÁC KĨ THUẬT NHÁNH CẬN VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC:
PGS. TSKH. Nguyễn Xuân Huy


MỞ ĐẦU 1
1. Đặt vấn đề 1
2. Đối tƣợng và phạm vi nghiên cứu 2
3. Hƣớng nghiên cứu của đề tài 2
LỜI CẢM ƠN 3
CHƢƠNG 1. TỔNG QUAN KĨ THUẬT NHÁNH CẬN 4
1.1. Giới thiệu chung 4
1.2. Ý tƣởng của thuật toán 5
1.3. Kĩ thuật tỉa nhánh 10
1.4. Kết hợp thuật toán nhánh cận vào thuật toán quay lui. 11
1.5. Kết luận 13
CHƢƠNG II. ÁP DỤNG KĨ THUẬT NHÁNH CẬN CHO MỘT SỐ BÀI
TOÁN 14
2.1. Các bài toán khó 14
2.2. Bài toán Ba lô 16
2.2.1. Bài toán: 16
2.2.2. Phân tích bài toán Ba lô 17
2.2.3. Chƣơng trình minh họa 22
2.3. Bài toán ngƣời du lịch (TSP) 25
2.3.1. Bài toán 25
2.3.2. Phân tích bài toán TSP 26
2.3.3. Chƣơng trình minh họa 27
2.3.4. Cải tiến 29
2.4. Bài toán đổi tiền (ATM) 35

iii

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

2.4.1. Bài toán 35

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

MỞ ĐẦU
1. Đặt vấn đề
Ngày nay với sự phát triển nhƣ vũ bão của khoa học công nghệ trên thế
giới, mặc dù xuất phát chậm hơn rất nhiều nƣớc nhƣng trong hơn chục năm
qua đất nƣớc chúng ta đã trải qua cuộc cách mạng lớn lao về công nghệ thông
tin. Để đáp ứng những đòi hỏi của sự phát triển đó phải có kế hoạch đào tạo
bồi dƣỡng những cá nhân có niềm say mê và có năng khiếu trong lĩnh vực tin
học đặc biệt học sinh các lớp chuyên tin tạo nguồn, cung cấp cho các trƣờng
đại học các sinh viên đã đƣợc trang bị vốn kiến thức cơ sở vững chắc, giúp
cho mục tiêu đi trƣớc đón đầu, rút ngắn khoảng cách về trình độ tin học giữa
nƣớc ta và thế giới.
Với học sinh phổ thông ở trƣờng chuyên phải đƣợc trang bị các kiến
thức cơ sở về các loại cấu trúc dữ liệu và trang bị các kiến thức tiên tiến nhất
về giải thuật. Việc truyền đạt các kiến thức về một số giải thuật nhƣ: quay lui,
nhánh cận, quy hoạch động, tham lam, các giải thuật trên đồ thị … là rất cần
thiết cho học sinh trƣờng Chuyên cũng nhƣ trong việc bồi dƣỡng học sinh
giỏi các trƣờng THPT (trung học phổ thông) để phát triển tƣ duy và lập trình
giải các bài toán tin học. Hình thành những nét cơ bản của nghệ thuật đoán
nhận giải thuật và nghệ thuật lập trình. Tạo lập và củng cố lòng say mê tìm
hiểu và khám phá cho học sinh khi giải các bài toán tin.
Để giải một bài toán thông thƣờng có nhiều cách tiếp cận. Mỗi cách tiếp
cận khác nhau cho kết quả với độ tối ƣu khác nhau. Với nhiều bài toán việc
tìm ra giải thuật tối ƣu không phải việc đơn giản, do đó một kĩ năng cần thiết
để giải đƣợc một bài toán hoàn chỉnh là phải giải đƣợc bài toán ở kích thƣớc
dữ liệu vừa phải. Đây là sẽ những bộ dữ liệu thử mang tính định hƣớng chiến
lƣợc cho việc giải bài toán. Có rất nhiều bài toán, đặc biệt là bài toán tối ƣu,

2

LỜI CẢM ƠN
n vă , tôi đ
c s h ng ô
. V ơn tôi xin ơ
đ Sau đ Đ Công nghệ
Thông tin và Truyền thông Thái Nguyên đ đ n thu n l
n văn.
ƣ -
Khoa học Nguyễn Xuân Huy, ng n đ
, đ ng viên, đ n thu n l
t n vă p.
Trong quá trình học tập, cũng nhƣ là trong quá trình làm luận văn, khó
tránh khỏi sai sót, rất mong các Thầy, Cô thông cảm, bỏ qua. Đồng thời do
trình độ cũng nhƣ kinh nghiệm thực tiễn còn hạn chế nên luận văn không thể
tránh khỏi những thiếu sót, em rất mong nhận đƣợc ý kiến đóng góp Thầy, Cô
để em học thêm đƣợc nhiều kinh nghiệm và sẽ hoàn thành tốt hơn.
Em xin chân thành cảm ơn!

4

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

CHƢƠNG 1. TỔNG QUAN KĨ THUẬT NHÁNH CẬN
1.1. Giới thiệu chung
Một trong những bài toán đặt ra trong thực tế là việc tìm ra một nghiệm
thoả 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ể, 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, 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

đó gọi là kỹ thuật đánh giá nhánh cận trong tiến trình quay lui.
Kĩ thuật Nhánh cận (Nhánh và cận – Branch and Bound) giúp chúng ta
đánh giá đƣợc nghiệm, do có thể cắt bỏ đi những phƣơng án (nhánh) không
cần thiết, việc tìm nghiệm tối ƣu sẽ nhanh hơn, cải thiện đƣợc độ phức tạp
thuật toán.
Những bài toán tìm một nghiệm, liệt kê hoặc bài toán tối ƣu là những
lớp bài toán có thể giải bằng Kĩ thuật Nhánh cận.
1.2. Ý tưởng của thuật toán
Nhánh cận là kỹ thuật xây dựng cây tìm kiếm phƣơng án tối ƣu, nhƣng
không xây dựng toàn bộ cây mà sử dụng giá trị cận để hạn chế bớt các nhánh.
Phƣơng án là các khả năng có thể của bài toán, những phƣơng án thỏa
yêu cầu đƣợc gọi là nghiệm của bài toán.
Trong quá trình duyệt qua tất cả các phƣơng án của bài toán, từ một nút
có thể phát sinh ra nhiều nút con khác nhau, mỗi nút con này có thể có nhiều
nút con khác nữa. Do đó, mỗi nút con này sẽ lại là gốc của một cây con. Quá
trình tìm kiếm này sẽ tạo ra một cây tìm kiếm. Nếu ta có thể đánh giá để cắt
bỏ đi một nhánh con không khả thi thì số lƣợng phƣơng án phải duyệt sẽ giảm
đi đáng kể.
Với mỗi nút trên cây ta sẽ xác định một giá trị cận. Giá trị cận là một giá
trị gần với giá của các phƣơng án. Với bài toán tìm Min ta sẽ xác định cận

6

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

dƣới, còn với bài toán tìm Max ta sẽ xác định cận trên. Cận dƣới là giá trị nhỏ
hơn hoặc bằng giá của phƣơng án, ngƣợc lại cận trên là giá trị lớn hơn hoặc
bằng giá của phƣơng án.
 Để giải bài toán tốt ta phải xác định cận càng sớm càng tốt.
Ta sẽ mô tả chi tiết tƣ tƣởng của thuận toán trên mô hình bài toán tối ƣu

Với giả thiết về tập D ở trên, ta có thể sử dụng thuật toán quay lui để liệt
kê các phƣơng án của bài toán. Trong quá trình liệt kê theo thuật toán quay
lui, ta sẽ xây dựng dần các thành phần của phƣơng án. Một bộ k thành phần
(a
1
, a
2
, …, a
k
) xuất hiện trong quá trình thực hiện thuật toán sẽ gọi là phƣơng
án bộ phận cấp k – Tiền tố của phƣơng án.
Thuật toán nhánh cận có thể áp dụng để giải bài toán đặt ra nếu nhƣ có
thể tìm đƣợc một hàm g xác định trên tập tất cả các phƣơng án bộ phận của
bài toán thỏa mãn bất đẳng thức sau:
g(a
1
, a
2
, …, a
k
) min {f(x): x D, x
i
= a
i
, i = 1, 2, …, k} (*)
với mọi lời giải bộ phận (a
1
, a
2
, …, a

1
, a
2
, …, a
k
) đƣợc gọi là cận dƣới của
tập D(a
1
, a
2
, …, a
k
). Do có thể đồng nhất tập D(a
1
, a
2
, …, a
k
) với phƣơng án
bộ phận (a
1
, a
2
, …, a
k
) nên ta cũng gọi g(a
1
, a
2
, …, a

2
, , a
k
) >
f
thì từ bất đẳng thức (*) ta suy ra:
f
< g(a
1
, a
2
, …, a
k
) min {f(x): x D, x
i
= a
i
, i = 1, 2, …, k}
Vì thế tập con các phƣơng án của bài toán D(a
1
, a
2
, …, a
k
) chắc chắn không
phải là phƣơng án tối ƣu. Trong trƣờng hợp này ta không cần tiếp tục phát
triển phƣơng án (a
1
, a
2

(hoặc đạt giá trị lớn nhất).

8

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

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 (x
1
, x
2
, ,x
k
) của nghiệm và khi mở rộng nghiệm (x
1
, x
2
,
,x
k+1
), nếu biết rằng tất cả các nghiệm mở rộng của nó (x
1
, x
2
, ,x
k+1,
…)
đề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ừ (x
1

<Xác định S
i
>;
for X
iS
i
do begin

9

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

<ghi nhận thành phần thứ i>;
if (tìm thấy nghiệm) then
<Cập nhật BestSol>
else
BranchBound(i+1);
<loại thành phần i>;
end;
end;
Trong thủ tục trên, BestSol là nghiệm tốt nhất đã biết ở thời điểm đó.
Thủ tục <cập nhật BestSol> sẽ xác định “độ tốt” của nghiệm mới tìm thấy,
nếu nghiệm mới tìm thấy tốt hơn BestSol thì BestSol sẽ đƣợc cập nhật lại là
nghiệm mới tìm đƣợc.
Hoặc với một cách khác nhƣ sau: [2]
Procedure Init;
Begin

nếu tại bƣớc thứ i, giá trị thử gán cho x[i] không có hi vọng tìm thấy cấu hình
tốt hơn cấu hình BestSolution thì thử giá trị khác ngay mà không cần phải gọi
đệ quy tìm tiếp hay ghi nhận kết quả làm gì. Nghiệm của bài toán sẽ đƣợc làm
tốt dần, bởi khi tìm ra một cấu hình mới (tốt hơn BestSolution ), ta không in
kết quả ngay mà sẽ cập nhật BestSolution bằng cấu hình mới vừa tìm đƣợc
1.3. Kĩ thuật tỉa nhánh
Để có thể tỉa bớt nhánh (loại bỏ những hƣớng đi, trƣờng hợp) của một
bài toán liệt kê bằng đệ quy ta có nhiều phƣơng pháp khác. Nhƣng chủ yếu là
dựa vào những dữ liệu đã biết, kết hợp với việc phán đoán để có thể định
lƣợng cho các giá trị cụ thể trong từng trƣờng hợp.
Định lƣợng để đánh giá độ tối ƣu của một hƣớng đi (một nhánh) là một
việc khó của kĩ thuật nhánh cận. Ngƣời lập trình chỉ có thể đánh giá đƣợc cận

11

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

của nhiều bài toán khi đã làm nhiều bài tập, từ đó đúc rút kinh nghiệm trong
quá trình tìm cận.
Trong chƣơng 2, một số bài toán sẽ đƣợc đƣa ra để phân tích, tìm hiểu
cách đánh giá cận và phƣơng pháp cài đặt. Nhƣng bài toán này sẽ mang tính
định hƣớng phƣơng pháp đánh giá cận cho nhiều bài toán sau.
1.4. Kết hợp thuật toán nhánh cận vào thuật toán quay lui.
Mô hình chung của kỹ thuật cài đặt đệ quy quay lui [1]
Procedure Try(i); //xây dựng thành phần thứ i
Begin
<xác định tập S
i
– tập các khả năng có thể của x
i

. Để tránh việc rẽ nhánh quá trình mà không hiệu quả ta hoàn toàn có thể
tìm cách đánh giá việc đi tiếp (điền giá trị cho x
i+1
) có hiệu quả không tại vị trí
trƣớc dòng lệnh (1) hoặc trƣớc dòng lệnh (2). Cụ thể nhƣ sau:

12

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

Procedure Try(i); //xây dựng thành phần thứ i [1]
Begin
If <việc mở rộng nghiệm không khả quan> then exit;
<xác định tập S
i
– tập các khả năng có thể của x
i
> (1)
For x
i
S
i
do begin
<ghi nhận thành phần thứ i>;
If <tìm thấy nghiệm> then <đưa ra nghiệm>
Else
Try(i+1); (2)
<loại thành phần thứ i>;
End;
Hoặc

14

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

CHƢƠNG II. ÁP DỤNG KĨ THUẬT
NHÁNH CẬN CHO MỘT SỐ BÀI TOÁN
2.1. Các bài toán khó
Hiện này có nhiều bài toán có thể giải bằng các thuật toán trong thời gian đa
thức theo kích thƣớc dữ liệu. Ví dụ nhƣ:
- Bài toán Tìm cây khung ngắn nhất, giải bằng thuật toán Prim có độ phức
tạp thuật toán là O(n
2
).
- Bài toán Tìm đƣờng đi ngắn nhất trong đồ thị, giải bằng thuật toán
Dijkstra có độ phức tạp là O(n
2
).
- Bài toán tìm ƣớc chung lớn nhất của 2 số nguyên dƣơng m và n, giải
bằng thuật toán Euclid có độ phức tạp O(m+n).
Tuy nhiên còn rất nhiều các bài toán khó mà hiện nay chúng ta mới chỉ giải
đƣợc bằng các thuật toán với độ phức tạp là hàm mũ theo kích thƣớc dữ liệu vào
của bài toán.
Hàm mũ có dạng: a
n
với a>1 và n là kích thƣớc dữ liệu của bài toán.
Với những bài toán phải giải bằng các thuật toán với độ phức tạp là hàm mũ
thì thời gian giải tăng rất nhanh theo kích thƣớc dữ liệu của bài toán.
Mặc dù bất kì lời giải nào cho mỗi bài toán đều có thể đƣợc kiểm chứng
nhanh chóng, nhƣng hiện chƣa có cách nào tìm ra đƣợc lời giải đó một cách hiệu
quả. Thời gian thực thi của tất cả các thuật toán hiện tại cho những bài toán khó

những bài toán có thể áp dụng các kĩ thuật nhánh cận.
2.2. Bài toán Ba lô
Bài toán Ba lô (Knapsack Problem) hay còn gọi là bài toán cái túi đã
đƣợc biết đến hơn một thế kỷ. Nhƣng đến thập niên 50 của thế kỷ XX, bài
toán này mới đƣợc nhà toán học Tobias Dantzig (1884–1956) định nghĩa đầy
đủ. [7]
Bài toán này là một bài toán khó, chƣa có thuật toán giải trong thời gian
đa thức theo kích thƣớc của bài toán.
2.2.1. Bài toán:
Cho một cái ba lô có thể đựng một trọng lƣợng b. Có n đồ vật, mỗi đồ
vật i có một số lƣợng không hạn chế, một trọng lƣợng a
i
nhất định và một giá
trị c
i
nào đó. Tìm một cách chọn lựa các đồ vật sao cho tổng trọng lƣợng của
các đồ vật không vƣợt quá b và có tổng giá trị là lớn nhất.
Dữ liệu: cho từ tệp văn bản BAG.INP
- Dòng đầu chứa 2 số nguyên dƣơng n và b (n<100, b<32000)
- Dòng thứ hai chứa n số nguyên lần lƣơt là c
1
, c
2
, …, c
n

- Dòng thứ ba chứa n số nguyên lần lƣợt là a
1
, a
2

, (1)
Trong đó :
Z
+
là tập các số nguyên không âm.
1
n
jj
j
cx
: là tổng giá trị của các đồ vật đƣợc chọn.
1
n
jj
j
ax
: là tổng trọng lƣợng của các đồ vật đƣợc chọn.
Kí hiệu D là tập hợp các phƣơng án của bài toán (1)
n
1 2 n j
j=1
{x=(x ,x , ,x ) : a , , 1,2, , }
jj
D x b x Z j n
.

18

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/


n
x x x x
với các thành
phần đƣợc xác định bởi công thức:
1 2 3
1
, 0
n
b
x x x x
a
.
và giá trị tối ƣu
*
1
1
c
gb
a

Chứng minh:
Thực vậy, xét x=(x
1
,x
2
,…,x
n
) là một phƣơng án tùy ý của bài toán (3).
Khi đó từ bất đẳng thức (2) và do x
j

2
, …, u
k
). Khi đó
giá trị sử dụng của các đồ vật đang có trong ba lô là:

1 1 2 2

k k k
cu c u c u

Và trọng lƣợng còn lại của ba lô là:

1 1 2 2

k k k
b b au a u a u

Ta có:

max{ ( ): , , 1,2, , }
jj
f x x D x u j k

=
11
max{ : , , 1, 2, , }
nn
k j j j j k j
j k j k

k j j j j k j
j k j k
k
kk
k
c x a x b x j k k n
c
b
a20

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/

Vậy ta có thể tính cận cho phƣơng án bộ phận với k thành phần của
phƣơng án đã đƣợc xây dựng (u
1
, u
2
, …, u
k
) bởi công thức sau:
1
12
1
( , , , )
k
k k k
k

6
a
i
5
3
2
4
Mô hình toán học:
f(x) = 10x
1
+ 5x
2
+ 3x
3
+ 6x
4
→ max,
5x
1
+ 3x
2
+ 2x
3
+ 4x
4
≤ 8,
x
j
Z
+