..

ĐẠ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

Thái Nguyên – 2014

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

i

LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi. Các kết quả
trong luận văn là trung thực, và chƣa từng đƣợc ai công bố trong bất kỳ tài
liệu nào khác.
Tơi xin cam đồn rằng mọi sự giúp đỡ để hoàn thành luận văn này đã
đƣợc cảm ơn. Các thơng tin trích dẫn trong luận văn đã đƣợc ghi rõ nguồn

gốc.

Học viên thực hiện luận văn

Phạm Chí Hiếu

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

ii

MỤC LỤC
LỜI CAM ĐOAN .............................................................................................. i
DANH MỤC CÁC HÌNH ................................................................................ iv
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
TỐN .............................................................................................................. 14
2.1. Các bài tốn khó..................................................................................... 14
2.2. Bài tốn Ba lơ ....................................................................................... 16

2.2.1. Bài tốn: ........................................................................................ 16
2.2.2. Phân tích bài tốn Ba lơ ................................................................ 17
2.2.3. Chƣơng trình minh họa ................................................................. 22
2.3. Bài tốn ngƣời du lịch (TSP) ............................................................... 25
2.3.1. Bài tốn ......................................................................................... 25
2.3.2. Phân tích bài tố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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

iii
2.4.1. Bài tốn ......................................................................................... 35
2.4.2. Phân tích bài ATM ........................................................................ 35
2.4.3. Chƣơng trình minh họa ................................................................. 36
2.5. Bài tốn dãy ABC ............................................................................... 40
2.5.1. Bài tốn ......................................................................................... 40
2.5.2. Phân tích bài tốn .......................................................................... 40
2.5.3. Chƣơng trình minh họa ................................................................. 41
2.6. Kết luận ................................................................................................ 44
CHƢƠNG 3. ỨNG DỤNG PHÁT TRIỂN NHÁNH CẬN ................................ 45
3.1. Thủ tục rút gọn. ...................................................................................... 46
3.2. Thủ tục chọn cạnh phân nhánh (r,c) ......................................................... 50
3.3. Mơ hình thuật toán ............................................................................... 53
KẾT LUẬN ..................................................................................................... 55
TÀI LIỆU THAM KHẢO ............................................................................... 56

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


/>

iv

DANH MỤC CÁC HÌNH

Hình 1. Giải bài tốn ba lơ bằng nhánh cận .................................................... 21
Hình 2. Giải bài tốn ngƣời du lịch ................................................................. 31
Hình 3. Mơ hình phân nhánh........................................................................... 46
Hình 4. Minh họa rút gọn hành trình .............................................................. 49
Hình 5. Minh họa rút gọn hành trình 2 ........................................................... 51

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

1

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 tốn tin học. Hình thành những nét cơ bản của nghệ thuật đố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 tố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 tố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 hồn chỉnh là phải giải đƣợc bài tố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 tốn. Có rất nhiều bài tốn, đặc biệt là bài tốn tối ƣu,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

2
có thể giải ngay bằng thuật tốn duyệt tồn bộ hoặc một phần của một bài
toán lớn. Với phƣơng pháp duyệt tồn bộ, điển hình là thuật tốn quay lui có
một nhƣợc điểm đó là độ phức tạp bài tốn thƣờng lớn, do đó kích thƣớc bài
tốn giải đƣợc rất hạn chế. Để khắc phục nhƣợc điểm chúng ta thƣờng phải áp
dụng kết hợp kĩ thuật nhánh cận (nhánh và cận).
Việc áp dụng kĩ thuật nhánh cận vào các bài tốn bài tốn thƣờng khá
trừu tƣợng và khó hiểu với học sinh THPT. Làm thế nào để có thể xây dựng
được một “cận” để có thể đánh giá được “độ tốt” của “nhánh” đang xét ?
Làm thế nào có thể kết hợp kĩ thuật nhánh cận vào các bài toán duyệt quay
lui hiệu quả ? Do đó tơi thấy việc phân tích, đánh giá và định hƣớng cách

tiếp cận một bài toán bằng kĩ thuật nhánh cận là rất cần thiết. Từ đó nâng cao
chất lƣợng của việc dạy và học cho học sinh.
Trong khuôn khổ luận văn thạc sĩ, tôi chọn đề tài nghiên cứu: “Phát
triển các kĩ thuật nhánh cận và ứng dụng”.
2. Đối tƣợng và phạm vi nghiên cứu
Kĩ thuật nhánh cận và ứng dụng để giải một số bài tốn liệt kê và tìm
phƣơng án tối ƣu.
3. Hƣớng nghiên cứu của đề tài
- Giới thiệu tổng quan kĩ thuật nhánh cận và các kỹ thuật liên quan.
- Tổ chức bài toàn theo kĩ thuật nhánh cận
- Cách đánh giá cận của các bài toán khác nhau
- Cài đặt chƣơng trình cho một số bài tốn.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

3

LỜI CẢM ƠN
n vă
cs h

ng

, tôi đ

ô
ơn tôi xin


.V
đ

ơ

Sau đ

Đ

Thông tin và Truyền thông Thái Nguyên đ

đ

Công nghệ
n thu n l

n văn.
ƣ Khoa học Nguyễn Xuân Huy, ng
, đ ng viên,
t

đ
n vă

nđ

n thu n l
p.

Trong quá trình học tập, cũng nhƣ là trong q 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!

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

4

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
liệt kê tồ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
liệt kê cấu hình có thể cài đặt bằng các phƣơng pháp liệt kê: Sinh tuần tự và
tìm kiếm quay lui.
Thuật tốn quay lui (backtracking) là chiến lƣợc tìm nghiệm bài tốn
bằng cách xét tất cả các phƣơng án có thể. Đó là một q trình tìm kiếm theo
độ sâu trong một tập hợp các lời giải. Trong quá trình tìm kiếm, nếu ta gặp
một hƣớng lựa chọn khơng thỏa mãn, ta quay lui về điểm lựa chọn nơi có các
hƣớng khác và thử hƣớng lựa chọn tiếp theo. Khi đã thử hết các lựa chọn
xuất phát từ điểm lựa chọn đó, ta quay lại điểm lựa chọn trƣớc đó và thử
hƣớng lựa chọn tiếp theo tại đó. Q trình tìm kiếm thất bại khi khơng cịn

điểm lựa chọn nào nữa. Đây là một thuật tốn có thể áp dụng để giải rất
nhiều bài tốn với kích thƣớc dữ liệu thích hợp. Ƣu điểm của thuật tốn là
đảm bảo tìm ra nghiệm đúng chính xác. Tuy nhiên, hạn chế là độ phức tạp
thƣờng lớn.
Mơ hình thuật tố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 ứng với mỗi nút tƣơng ứng với một giá trị đƣợc chọn cho x[i] sẽ
ứng với chỉ 2 nút tƣơng ứng với 2 giá trị mà x[i+1] có thể nhận thì cây n cấp
sẽ có tới 2n nút lá, con số này lớn hơn rất nhiều lần so với dữ liệu đầu vào n.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

5
Chính vì vậy mà nếu nhƣ ta có thao tác thừa trong việc chọn x[i] thì sẽ phải
trả giá rất lớn về chi phí thực thi thuật tốn bởi q trình tìm kiếm lịng vịng
vơ nghĩa trong các bƣớc chọn kế tiếp x[i+1], x[i+2], … Khi đó, một vấn đề
đặt ra là trong quá trình liệt kê lời giải ta cần tận dụng những thơng tin đã tìm
đƣợc để loại bỏ sớm những phƣơng án chắc chắn không phải tối ƣu. Kỹ thuật
đó 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 tốn tìm một nghiệm, liệt kê hoặc bài tốn tối ƣu là những
lớp bài tố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 tồ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 tốn, những phƣơng án thỏa
yêu cầu đƣợc gọi là nghiệm của bài tốn.

Trong q trình duyệt qua tất cả các phƣơng án của bài tố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 tốn tìm Min ta sẽ xác định cận

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

6
dƣới, cịn với bài tố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 tốn trên mơ hình bài tốn tối ƣu
tổ hợp tổng quát sau:
min {f(x): x

D}

Trong đó D là tập hữu hạn phần tử.
Giả thiết rằng tập D đƣợc mô tả nhƣ sau:
D = {x=(x1, x2, …, xn)

S1


S2

…

Sn : x thỏa mãn tính chất P}

với S1, S2, …, Sn là các tập hữu hạn, cịn P là tính chất trên tích Đêcac S1
…

S2

Sn.
Với giả thiết về tập D ở trên, ta có thể sử dụng thuật tốn quay lui để liệt

kê các phƣơng án của bài tốn. Trong q 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
(a1, a2, …, ak) 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 tố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(a1, a2, …, ak)

min {f(x): x

D, xi = ai, i = 1, 2, …, k}

(*)

với mọi lời giải bộ phận (a1, a2, …, ak) và với mọi k = 1, 2, …

Bât đẳng thức (*) có nghĩa là giá trị của hàm g tại phƣơng án bộ phận
(a1, a2, …, ak) là không vƣợt quá giá trị nhỏ nhất của hàm mục tiêu của bài
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

7
tốn trên tập con các phƣơng án. Hay nói một cách khác, g(a1, a2, …, ak) là
cận dưới của giá trị hàm mục tiêu trên tập D(a1, a2, …, ak). Do đó, hàm g
đƣợc gọi là hàm cận dƣới, và giá trị g(a1, a2, …, ak) đƣợc gọi là cận dƣới của
tập D(a1, a2, …, ak). Do có thể đồng nhất tập D(a1, a2, …, ak) với phƣơng án
bộ phận (a1, a2, …, ak) nên ta cũng gọi g(a1, a2, …, ak) là cận dƣới của
phƣơng án bộ phận (a1, a2, …, ak).
Giả sử rằng đã có hàm g. Ta xét cách sử dụng hàm này để giảm bớt khối
lƣợng duyệt trong quá trình liệt kê các cấu hình tổ hợp (các phƣơng án) của
bài toán theo thuật toán quay lui. Trong q trình liệt kê các phƣơng án có thể
đã thu đƣợc một số phƣơng án của bài toán. Gọi x là phƣơng án với giá trị
hàm mục tiêu nhỏ nhất trong số các phƣơng án đã tìm đƣợc, kí hiệu f = f( x ).
Ta gọi x là phƣơng án tốt nhất hiện có, cịn f là kỷ lục. Giả sử đã có f , khi
đó nếu g(a1, a2,..., ak) > f thì từ bất đẳng thức (*) ta suy ra:

f < g(a1, a2, …, ak)

min {f(x): x

D, xi = ai, i = 1, 2, …, k}

Vì thế tập con các phƣơng án của bài toán D(a1, a2, …, ak) 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 (a1, a2, …, ak), nói cách khác là ta có thể bỏ qua các phƣơng

án trong tập D(a1, a2, …, ak) trong quá trình tìm kiếm.
Để dễ hình dung, ta giả sử nghiệm của bài tốn có thể biểu diễn dƣới
dạng một vectơ (x1, x2, ..., xn), mỗi thành phần xi (i = 1,2,.., n) đƣợc chọn ra từ
tập Si. Mỗi nghiệm của bài toán x = (x1, x2, ...,xn) đƣợc xác định “độ tốt” bằng
một hàm f(x) và mục tiêu cần tìm nghiệm có giá trị f(x) đạt giá trị nhỏ nhất
(hoặc đạt giá trị lớn nhất).

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

8
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 (x1, x2, ...,xk) của nghiệm và khi mở rộng nghiệm (x1, x2,
...,xk+1), nếu biết rằng tất cả các nghiệm mở rộng của nó (x1, x2, ...,xk+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ừ (x1, x2, ...,xk) nữa. [4]
Nhƣ vậy, với phƣơng pháp nhánh và cận, ta khơng phải duyệt tồ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 tốn
nhánh cận sẽ chạy nhanh hơn nhiều so với thuật toán vét cạn.
Việc đánh giá các nghiệm mở rộng đề cập ở trên chính là việc ta xây
dựng hàm g trong bất đẳng thức (*). Việc xây dựng này sẽ phụ thuộc vào từng
bài tốn tối ƣu tổ hợp cụ thể. Thơng thƣờng ta sẽ cố gắng xây dựng nó sao
cho:
- 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ối ƣu tổ
hợp ở về phải của (*).

- Giá trị của g(a1, a2, …, ak) phải sát với giá trị vế phải của (*)
Thuật tốn nhánh cận có thể mơ tả bằng mơ hình đệ quy sau:
procedure BranchBound (i);
begin
<Đánh giá khả năng mở rộng các nghiệm>;
If (các phương án mở rộng đều không tốt hơn BestSol) then exit;
<Xác định Si>;
for Xi

Si do begin

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

9
<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
<Khởi tạo một cấu hình xuất phát>;
end;
{Thủ tục này thử chọn cho x[i] tất cả các giá trị nó có thể nhận}
procedure Try(i: Integer);
begin
for <Mọi giá trị V có thể gán cho x[i]>do
begin
<Thử cho x[i] := V>;
If <Việc thử trên vẫn còn hi vọng tìm ra cấu hình tốt hơn BestSol> then
If <x[i] là phần tử cuối cùng trong cấu hình> then
<Cập nhật BestSol>
else begin
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

10
<Ghi nhận việc thử x[i] = V nếu cần>;
Try(i + 1); {Gọi đệ quy, chọn tiếp x[i+1]}
<Bỏ ghi nhận việc thử cho x[i] = V (nếu cần)>;
end;
end;
end;
begin
Init;
Attempt(1);
<Thơng báo cấu hình tối ƣu BestSol> ;
end.
Với cấu trúc của kỹ thuật nhánh cận nhƣ trên, ta có thể dễ thấy Kỹ thuật

này đã thêm vào cho thuật toán quay lui khả năng đánh giá theo từng bƣớc,
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 tố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 đố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

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

11
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
q 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 tố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 Si – tập các khả năng có thể của xi>
For xi


(1)

Si 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;
Với mơ hình đệ quy quay lui nhƣ trên ta có thể dễ dàng nhận ra đây là
mơ hình liệt kê tất cả các cấu hình nghiệm có thể của nghiệm X = (x 1, x2, … ,
xn), với mỗi thành phần xi thuộc tập Si. Sau khi thực hiện thử giá trị cho thành
phần xi, mơ hình trên sẽ tiến hành thử tiếp tất cả các giá trị cho thành phần
xi+1. Để tránh việc rẽ nhánh quá trình mà khơng hiệu quả ta hồn tồn có thể
tìm cách đánh giá việc đi tiếp (điền giá trị cho xi+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:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

12
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 Si – tập các khả năng có thể của xi>

For xi

(1)

Si 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
Procedure Try(i); //xây dựng thành phần thứ i
Begin
<xác định tập Si – tập các khả năng có thể của xi>
For xi

(1)

Si do begin

<ghi nhận thành phần thứ i>;
If <tìm thấy nghiệm> then <đưa ra nghiệm>
Else
If <việc mở rộng nghiệm khả quan> then Try(i+1);


(2)

<loại thành phần thứ i>;
End;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

13

1.5. Kết luận
Kĩ thuật nhánh cận, cũng nhƣ nhiều kĩ thuật khác trong lập trình nó chỉ
mang tính định hƣớng chiến lƣợc để giải bài tốn. Đây là khơng phải là một
cơng cụ siêu việt để có thể giải tất cả các bài tốn tìm nghiệm tối ƣu hay liệt
kê. Do đó, khi áp dụng, địi hỏi ngƣời lập trình phải linh hoạt kết hợp thêm
nhiều kĩ thuật, thuật toán khác nhau thì mới có thể đem lại kết quả tốt nhất.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

14

CHƢƠNG II. ÁP DỤNG KĨ THUẬT
NHÁNH CẬN CHO MỘT SỐ BÀI TỐN
2.1. Các bài tốn khó
Hiện này có nhiều bài tốn có thể giải bằng các thuật tốn trong thời gian đa
thức theo kích thƣớc dữ liệu. Ví dụ nhƣ:
- Bài tốn Tìm cây khung ngắn nhất, giải bằng thuật tốn Prim có độ phức
tạp thuật tốn là O(n2).

- Bài tốn Tìm đƣờng đi ngắn nhất trong đồ thị, giải bằng thuật tốn
Dijkstra có độ phức tạp là O(n2).
- Bài tốn tìm ƣớc chung lớn nhất của 2 số ngun dƣơng m và n, giải
bằng thuật tốn Euclid có độ phức tạp O(m+n).
Tuy nhiên cịn rất nhiều các bài tố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 tốn.
Hàm mũ có dạng: an 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 tố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 tốn.
Mặc dù bất kì lời giải nào cho mỗi bài tố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 tốn khó
đều tăng rất nhanh theo kích thƣớc bài tốn. Vì vậy ngay cả những trƣờng hợp có
kích thƣớc tƣơng đối lớn đã đòi hỏi thời gian hàng tỷ năm để giải. Do đó, việc xác
định xem những bài tốn này có thể đƣợc giải quyết nhanh chóng hay khơng là
một trong những bài tốn mở của khoa học máy tính hiện nay.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

15
Một số bài tốn khó tiêu biểu với độ phức tạp là hàm mũ nhƣ:
1. Bài toán bè cực đại (MaxClique): Cho một đồ thị vô hƣớng G = (V, E). V
là tập các đỉnh, E là tập các cạnh tƣơng ứng các đỉnh trong V. Cần tìm bè lớn nhất
của G. Bè là tập các đỉnh trong đồ thị mà đơi một có cạnh nối với nhau (là một đồ
thị con đầy đủ trong đồ thị G).
2. Bài toán tập độc lập (Independent set): Cho đồ thị vô hƣớng G = (V, E) và
số nguyên K, hỏi có thể tìm đƣợc tập độc lập S với |S| ≥ K. Tập độc lập là tập các

đỉnh trong đồ thị mà chúng đơi một khơng có cạnh nối với nhau.
3. Bài toán phủ đỉnh (Vertex cover): Ta gọi một phủ đỉnh của đồ thị vô
hƣớng G = (V, E) là một tập con các đỉnh của đồ thị S V sao cho mỗi cạnh của
đồ thị có ít nhất một đầu mút trong S. Bài toán đặt ra là: Cho đồ thị vô hƣớng G =
(V, E) và số nguyên k. Hỏi G có phủ đỉnh với kích thƣớc k hay khơng?

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

16

Sau đây là cách áp dụng các kĩ thuật nhánh cận và tổ chức dữ liệu cho một số
bài toán điển hình. Những bài tốn dƣới đây mang tính chất tiêu biểu cho lớp bài
tốn mà nó đại diện. Từ đó giúp minh họa việc áp dụng các kĩ thuật nhánh cận vào
các bài toán thực tế. Hơn nữa, giúp chúng ta sẽ có cái nhìn tổng qt hơn cho
những bài tốn có thể áp dụng các kĩ thuật nhánh cận.
2.2. Bài tốn Ba lơ
Bài tốn Ba lơ (Knapsack Problem) hay cịn gọi là bài tố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 tốn khó, chƣa có thuật tốn giải trong thời gian
đa thức theo kích thƣớc của bài tốn.
2.2.1. Bài tố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 ai nhất định và một giá
trị ci 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à c1, c2, …, cn
- Dòng thứ ba chứa n số nguyên lần lƣợt là a1, a2, …, an
Các số trên cùng dòng cách nhau ít nhất 1 dấu cách.
Kết quả: ghi ra tệp văn bản BAG.OUT gồm 2 dòng
- Dòng đầu ghi 1 số nguyên dƣơng là tổng giá trị các đồ vật trong ba lơ

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

17
- Dòng thứ hai ghi n số nguyên lần lƣợt là số lƣợng các đồ vật 1, 2, …,
n.
2.2.2. Phân tích bài tốn Ba lơ
Nếu chấp nhận một kết quả gần đúng, ta hồn tồn có thể giải bài tốn
này theo phƣơng pháp tham lam. Và rất dễ thấy, tiêu chuẩn để chọn là giá đơn
vị cao. Ta duyệt cao vật theo giá đơn vị từ cao xuống thấp. Vật đƣợc chọn ta
sẽ lấy tối đa. [3]
Với cách giải nhƣ trên, tùy vào từng trƣờng hợp của dữ liệu, đôi khi ta
sẽ thu đƣợc kết quả tuyệt đối của bài tốn.
Sau đây ta sẽ phân tích bài tốn để tìm phƣơng án áp dụng kĩ thuật nhánh
cận:
Mơ hình tốn học của bài tốn có dạng sau: Tìm
n

f

*


max{ f ( x)

n

cjxj :
j 1

ajxj

b, x j

Z , j 1,2,..., n} ,

(1)

j 1

Trong đó :
Z+ là tập các số ngun khơng âm.
n

c j x j : là tổng giá trị của các đồ vật đƣợc chọn.

j 1
n

a j x j : là tổng trọng lƣợng của các đồ vật đƣợc chọn.

j 1


Kí hiệu D là tập hợp các phƣơng án của bài toán (1)
n

D {x=(x1 ,x 2 ,...,x n ) :

a jx j

b, x j

Z , j 1,2,..., n} .

j=1

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

18
Để đảm bảo tính tổng quát ta giả thiết rằng các đồ vật đƣợc đánh số sao
cho bất đẳng thức sau đƣợc thỏa mãn:

c1
a1

c2
a2

cn
an


...

(2)

(Sắp xếp giảm theo giá của một đơn vị đồ vật)
Để dễ dàng xây dựng hàm tính cận trên của bài tốn (1), ta xét bài tốn
có biên liên tục sau: Tìm
n

g

*

max{ f ( x)

n

cjxj :
j 1

Trong đó: (xj ≥ 0, xj
Mệnh đề:

ajxj

b, x j

0, j 1,2,..., n}

(3)


j 1

R)

[5]

Phƣơng án tối ƣu của bài toán (3) là vectơ x

( x1, x2 ,..., xn ) với các thành

phần đƣợc xác định bởi công thức:

x1

b
, x2
a1

x3 ... xn

và giá trị tối ƣu g *

0.

c1
b
a1

Chứng minh:

Thực vậy, xét x=(x1,x2,…,xn) là một phƣơng án tùy ý của bài tốn (3).
Khi đó từ bất đẳng thức (2) và do xj

cjxj

0, ta suy ra:

c1
a j x j , j 1,2,..., n
a1

Suy ra:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

19
n

n

cjxj
j 1

j

c1
ajxj
1 a1


n

c1
a1

ajxj
j 1

c1
b
a1

g*

Mệnh đề đã đƣợc chứng minh.
Bây giờ, giả sử ta có phƣơng án bộ phận cấp k: (u1, u2, …, uk). Khi đó
giá trị sử dụng của các đồ vật đang có trong ba lơ là:

c1u1 c2u2 ... ck uk

k

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

bk

b a1u1 a2u2 ... ak uk

Ta có:


max{ f ( x) : x D, x j

u j , j 1,2,..., k}

n

= max{

n

cjxj :

k

bk , x j

Z ,j

ajxj

bk , x j

0, j

bk , x j

0, j

k 1, k


j k 1

j k 1

n

n

max{

k

ajxj

cjxj :
j k 1

k 1, k

k 1, k

2,..., n}

2,..., n}

j k 1

Theo Mệnh đề thì:
n


max{

n

cjxj :
j k 1

ajxj

2,..., n}

j k 1

ck 1
bk
ak 1

Suy ra:
n

max{

k

cjxj :
j k 1

k


n

ajxj

bk , x j

0, j

k 1, k

2,..., n}

j k 1

ck 1
bk
ak 1

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

20
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 (u1, u2, …, uk) bởi công thức sau:

g (u1 , u2 ,..., uk )

ck 1
bk

ak 1

k

Khi tiếp tục xây dựng thành phần thứ k+1 cho lời giải, các giá trị đề cử
cho xk+1 sẽ là 0, 1, …,

bk
. Do đã có kết quả của mệnh đề, khi chọn các giá
ak 1

trị cho xk+1 ta sẽ duyệt các giá trị đề cử theo giá trị giảm dần.
Ví dụ: Giải bài tốn ba lơ theo thuật tốn nhánh cận ở trên vừa trình bày
với dữ liệu nhƣ sau:
n = 4, b = 8,
i

1

2

3

4

ci

10

5


3

6

ai

5

3

2

4

Mơ hình tốn học:
f(x) = 10x1 + 5x2 + 3x3 + 6x4 → max,
5x1 + 3x2 + 2x3 + 4x4 ≤ 8,
xj

Z+, j = 1,2,3,4.

Giải ví dụ:
Q trình giải bài tốn đƣợc mơ tả trong cây bên dƣới. Thơng tin về một
phƣơng án bộ phận trên cây đƣợc ghi các các nút (các hình chữ nhật) tƣơng
ứng theo thứ tự nhƣ sau:
- Các thành phần của phƣơng án theo đúng thứ tự.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


/>