PHƯƠNG PHÁP NHÁNH C

1. LÝ THUYẾ
T CHUNG
Xét bài toán tối ưu tổ hợp t
ổ
trong đó
D = {x= (x
A
1
, A
2
, , A
n
là các tập hữ
u h
Ta gọi bộ n thành phần
x= (x
đầy đủ của bài toán, bộ
k<n thành ph
phận hay lời giải bộ phậ
n. Ta s
bộ phận, tức là sẽ phát triể
n d
Ký hiệu ܦሺݔ
ଵ
,…,ݔ
௞
ሻ là tậ
p h
phương án bộ phận ሺݔ

݂ሺݔ̅ሻ . Ta gọi ܨ là giá trị kỷ

suy ra
min
NG PHÁP NHÁNH C
ẬN GIẢI CÁC BÀI TOÁN TỐ
I Ư
T CHUNG

ổ
ng quát sau:
Min{f(x): x D},

D = {x= (x
1
, x
2
, , x
n
) A
1
A
2
A
3
A
n
},
u h
ạn.

௞
ሻ. Để giảm thờ
i gian tính toán chúng ta s
ộ
phận mà chỉ phát triển nhữ
ng phương án ti
,
…,ݔ
௞
ሻ mà ܦ
ሺ
ݔ
ଵ
,…,ݔ
௞
ሻ
có khả
năng ch
n các phương án b
ộ phận ሺݔ
ଵ
,…,ݔ
௞
ሻ mà ܦ
ሺ
ݔ
i gi
ải tối ưu. Vấn đề đặt ra là phải có dấu hi
ệ
m năng.

ã duy

lục hiện thời. Thế thì, nếu ݃
ሺ
ݔ
ଵ
,…,ݔ
௞
ሻ
൐
min
ሼ
݂
ሺ
ݔ
ሻ
,ݔ∈ܦ
ሺ
ݔ
ଵ
,…,ݔ
௞
ሻሽ
൐ܨ.
I ƯU T
Ổ HỢP

ủ
hay lời giải
là phương án b

ሺ
ݔ
ଵ
,…,ݔ
௞
ሻ

không th
ሺݔ
ଵ
,…,ݔ
௞
ሻ không cầ
n phát tri
Như vậy, để thực hiện tố
t ý t
• Xác định được hàm c
ậ
bài toán tối ưu ở vế
ph
• Xác định và cập nhậ
t đư
Chú ý. Khi bài toán tố
i ưu đ
phải xét hàm cận trên thỏ
a mãn
݃ሺݔ
ଵ
,
Gọi ܨ là giá trị kỷ lục hiệ
không th
ể chứa lời giải tố
i ưu, và phương án b
n phát tri
ển tiếp.
t ý t
ưởng trên cần:
ậ
n dưới ݃ሺݔ
ଵ
,…,ݔ
௞
ሻ một cách dễ
dàng hơ
ph
ải của (1).
t đư
ợc giá trị kỷ lục.
ưu đ
ặt ra là Max{f(x): x D}
thì thay cho hàm c
a mãn

,
…,ݔ

ሻ
,ݔ∈ܦ
ሺ
ݔ
ଵ
,…,ݔ
௞
ሻሽ
൏ܨ.
không th
ể chứa lời giải tố
i ưu, và phương án b
n phát tri
ển tiếp.
a bài toán xây d
ựng lời giải (hay cấ
u hình/ph
ế
m thì đối với mỗi nút (hay mỗ
i nhánh) c
i bài toán c
ực tiểu hóa hoặc cận trên đối vớ
i bài toán c
n các nhánh ti
ềm năng chứa lời giải tối ưu.
ng án b
ộ phận
dàng hơn vi
ệc giải
thì thay cho hàm c

bestsofar = ∞ (giá trị kỷ lục)
Repeat while S is nonempty:
choose a subproblem (partial solution) ܲ∈ܵ and remove it from S;
expand it into smaller subproblems ܲ
ଵ
,ܲ
ଶ
,…,ܲ
௞
.

For each ܲ
௜
:
If ܲ
௜
is a complete solution: update bestsofar
else if lowerbound(ܲ
௜
) < bestsofar: add P
i
to S
return bestsofar
tức là
Bắt đầu bởi bài toán P
0

Đặt Sൌ
ሼ
P

→
qua một số đỉnh thuộc tập
S V
⊆
, trong đó
S
chứa cả
a
và
b
. Ta ký hiệu lời giải bộ phận này là bộ ba
[ , , ]
a S b
. Đỉnh
a
ta cố định và coi như là đỉnh xuất phát. Bài toán con tương ứng là
tìm phần bù tốt nhất, tức là đường đi
b a
→
qua các đỉnh
V S
−
. Trên mỗi bước
tìm một đỉnh
x
và đường đi cập nhật là
[ , , ]
a S x x
+
.

Đồ thị và đường đi tối ưu Tìm kiếm theo nhánh cận thực hiện từ trái sang phải.
Các số trong hộp là cận dưới của chi phí

3. ỨNG DỤNG 2: BÀI TOÁN NGƯỜI BÁN HÀNG RONG (TSP)
Bài toán: Cho ݊ thành phố ܶ
ଵ
,ܶ
ଶ
,…,ܶ
௡
. Xuất phát từ một thành phố nào đó người
bán hàng muốn đi qua tất cả các thành phố còn lại, mỗi thành phố một lần, rồi lại
quay về thành phố xuất phát. Biết ܥሺ݅,݆ሻ chi phí đi từ thành phố ܶ
௜
đến thành phố
ܶ
௝
. Tìm cách đi với tổng chi phí bé nhất.
Giải: Cố định thành phố xuất phát là ܶ
ଵ
và ký hiệu
ሼ
ݔ
ଶ

1,ݔ
ଶ
ሻ
+ܥ
ሺ
ݔ
ଶ
,ݔ
ଷ
ሻ
+⋯+ܥ
ሺ
ݔ
௡ିଵ
,ݔ
௡
ሻ
+ܥ
ሺ
ݔ
௡
,1
ሻ
.
Bài toán TSP được phát biểu dưới dạng bài toán tối ưu
݉݅݊
ሼ
݂
ሺ
ݔ

,…,ݑ
௞
ሻ, trong đó (ݑ
ଶ
,…,ݑ
௞
) là một tổ hơp ݇ phần tử
của
ሼ
2,…,݊
ሽ
. Phương án này tương ứng với hành trình
ܶ
ଵ
→ܶ
௨
మ
→⋯→ܶ
௨
ೖ

và chi phí của nó là
ܵൌܥ
ሺ
1,ݑ
ଶ
ሻ
+ܥ
ሺ
ݑ

௞
ሻ
ൌܵ+ሺ݊−݇+1ሻܥ
௠௜௡
.

Thí dụ: Giải bài toán người bán hàng rong với ma trận chi phí sau
C=
ۏ
ێ
ێ
ێ
ۍ
0
3
17
6
9

3
0
9
3
15

14
4

4. ỨNG DỤNG 3: BÀI TOÁN CÁI TÚI TỔNG QUÁT
Bài toán: Có ݊ loại đồ vật và số lượng mỗi loại đồ vật là không hạn chế. Ký hiệu
trọng lượng của đồ vật ݆ là ܽ
௝
và giá trị sử dụng là ܿ
௝
. Cần chất các đồ vật vào túi
với trọng lượng là ܾ sao cho tổng giá trị sử dụng của các đồ vật trong túi là lớn
nhất.
Mô hình toán học:
ቊ
݂
ሺ
ݔ
ሻ
ൌ
∑
ܿ
௝
ݔ
௝
→݉ܽݔ
௡
௝ୀଵ
∑
ܽ
௝
ݔ
௝
൑ܾ,

൑ܾ, ݔ
௝
∈ܼ
ା
, ݆ൌ1,…,݊
௡
௝ୀଵ
ൟ

Không giảm tính tổng quát ta giả sử rằng các đồ vật được đánh số sao cho
௖
భ
௔
భ
൒
௖
మ
௔
మ
൒⋯൒
௖
೙
௔
೙
(4)
Để xây dựng hàm cận dưới ta xét bài toán cái túi với các biến liên tục:
Tìm
݃∗ൌ݉ܽݔ
൛
݂

ൌ⋯ൌݔ̅
௡
ൌ0
và giá trị tối ưu là
݃∗ൌ
ܿ
ଵ
ܾ
ଵ
ܽ
ଵ
.
Chứng minh. Từ (4) suy ra
ܿ
௜
ݔ
௜
ൌ
ܿ
௜
ܽ
௜
∗ܽ
௜
ݔ
௜
൑
ܿ
ଵ
ܽ

ܽ
ଵ
ݔ
ଵା⋯ା
ܽ
௡
ݔ
௡
ሻ
൑
௖
భ
௔
భ
ܾൌ݂ሺݔ̅ሻ.
Điều đó có nghĩa ݔ̅ là phương án tối ưu.
Xây dựng hàm cận trên:
Giả sử đã có phương án bộ phận cấp k là ሺݑ
ଵ
,…,ݑ
௞
ሻ. Khi đó giá trị của các đồ vật
trong túi là
ߪ
௞
ൌܿ
ଵ
ݑ
ଵ
+⋯+ܿ

ൌ݉ܽݔ
ቐ
ߪ
௞
+
෍
ܿ
௝
ݔ
௝
:
௡
௝ୀ௞ାଵ

෍
ܽ
௝
ݔ
௝
൑ܾ
௞
;ݔ
௝
∈ܼ
ା
, ݆ൌ݇+1,…,݊
௡
௝ୀ௞ାଵ
ቑ


௞
+
௖
ೖశభ
௕
ೖ
௔
ೖశభ
(theo Mệnh đề 1).
Do đó có thể tính cận trên cho phương án bộ phận
ሺ
ݑ
ଵ
,…,ݑ
௞
ሻ
như sau:
݃
ሺ
ݑ
ଵ
,…,ݑ
௞
ሻ
ൌߪ
௞
+
௖
ೖశభ
௕


Trong hình vẽ trên ߪ là giá trị của các đồ vật đã có trong túi, ݓ là khả năng chứa
còn lại của túi và ݃ là cận trên của nút.

5. ỨNG DỤNG 4: BÀI TOÁN CÁI TÚI 0-1
Bài toán: Có ݊ đồ vật với trọng lượng là ܽ
௝
và giá trị sử dụng là ܿ
௝
ሺ݆ൌ1,…,݊ሻ.
Cần chất các đồ vật vào túi với trọng lượng là ܾ sao cho tổng giá trị sử dụng của
các đồ vật trong túi là lớn nhất.
Mô hình toán học:
ቊ
݂
ሺ
ݔ
ሻ
ൌ
∑
ܿ
௝
ݔ
௝
→݉ܽݔ
௡
௝ୀଵ
∑
ܽ
௝

,
∑
ܽ
௝
ݔ
௝
൑ܾ,
௡
௝ୀଵ
0൑ݔ
௝
൑1, ݆ൌ1,…,݊
ൟ
(7)
Mệnh đề 2. Giả sử
௖
భ
௔
భ
൒
௖
మ
௔
మ
൒⋯൒
௖
೙
௔
೙
.

ଵ
+⋯+ܽ
௥
+ܽ
௥ାଵ
൐ܾ

0൑
௕ିሺ௔
భ
ା⋯ା௔
ೝ
ሻ
௔
ೝశభ
൏1.
Giá trị tối ưu là
݂
̅
ൌܿ
ଵ
+⋯+ܿ
௥
+
ܿ
௥ାଵ

ܽ
௥ାଵ
ܾ

ܾ
௞
ൌܾ−ሺܽ
ଵ
ݑ
ଵ
+⋯+ܽ
௞
ݑ
௞
ሻ.
Ta có
݉ܽݔ
൛
݂
ሺ
ݔ
ሻ
:ݔ∈ܦ,ݔ
௝
ൌݑ
௝
,݆ൌ1,…,݇
ൟ

ൌ݉ܽݔ
ቐ
ߪ
௞
+

൛
∑
ܿ
௝
ݔ
௝
:
௡
௝ୀ௞ାଵ

∑
ܽ
௝
ݔ
௝
൑ܾ
௞
;0൑ݔ
௝
൑1, ݆ൌ݇+1,…,݊
௡
௝ୀ௞ାଵ
ൟ

ൌߪ
௞
+ܿ
௞ାଵ
+⋯+ܿ
௥

௥
ሻ
Do đó có thể tính cận trên cho phương án bộ phận
ሺ
ݑ
ଵ
,…,ݑ
௞
ሻ
như sau:
݃
ሺ
ݑ
ଵ
,…,ݑ
௞
ሻ
ൌߪ
௞
+ܿ
௞ାଵ
+⋯+ܿ
௥
+
௖
ೝశభ
௕
ೝ
௔
ೝశభ