CÁC CHIẾN LƯỢC
THIẾT KẾ GIẢI THUẬT
1
CHƯƠNG 5
Nội dung

Qui hoạch động

Giải thuật tham lam

Giải thuật quay lui (backtracking)

Giải thuật nhánh và cận
2

Phương Pháp Nhánh và Cận
• Ý tưởng phương pháp
• Lược đồ giải thuật
• Các ví dụ
Ý Tưởng Phương Pháp (trang 77)
•
Về nguyên tắc, kỹ thuật quay lui cho phép tìm
được nghiệm đúng của bài toán, nhưng do
phải vét cạn, khi kích thước bài toán lớn sẽ
rất kém hiệu quả
•
Kỹ thuật nhánh cận khắc phục được hạn chế
này bằng cách, xác định nhánh cận với mục
tiêu tại mỗi bước tìm kiếm, vì vậy loại bỏ
được hầu hết các hướng tìm kiếm không cần
thiết

• Kỹ thuật nhánh cận có thể không cho nghiệm tối ưu
chính xác mà chỉ cho nghiệm gần đúng
•
Kỹ thuật nhánh cận thường được áp dụng để giải các
bài toán tối ưu được mô hình hóa bởi
Tìm min{f(x) | x D}∈
•
Tập D ={x=(x
1
, x
2
, …., x
n
) A∈
1
×A
2
×…×A
n
| x thỏa tính
chất P} là hữu hạn, f(x) gọi là hàm mục tiêu
•
Một nghiệm của bài toán là một bộ (x
1
, x
2
, …., x
n
) D ∈
sao cho f(x

k
) ≤min{f(x) | x D, x∈
i
=a
i
, i=1, 2,…, k},với
mọi (a
1
, a
2
, …., a
k
), k=1,2, …(1)
•
Rõ ràng g(a
1
, a
2
, …., a
k
) là cận dưới của giá trị hàm
mục tiêu trên tập D(a
1
, a
2
, …., a
k
)={((a
1
, a

Ta nói x* là phương án tốt nhất hiện có, còn f* là kỷ
lục
•
Nếu g(a
1
, a
2
, …., a
k
) >f* thì từ(1) ta có
•
f*< g(a
1
, a
2
, …., a
k
) ≤min{f(x) | x D, x∈
i
=a
i
, i=1, 2,…, k}
•
Suy ra tập con phương án D(a
1
, a
2
, …., a
k
) chắc chắn

Giải?
Các Ví dụ
Giải
• Cố định thành phố xuất phát T
1
, bài toán dẫn đến tìm cực
tiểu của hàm
f(x
2
, x
3
, …, x
n
)=c[1, x
2
]+c[x
2
, x
3
]+…+c[x
n
,1] với điều kiện (x
2
,
x
3
, …, x
n
) là một hoán vị của 2, 3, …, n
Các Ví dụ

,u
k
]
Các Ví dụ
Giải
• Hành trình đầy đủ của hành trình bộ phận còn phải đi
qua n-k thành phố còn lại rồi quay về T
1
bao gồm n-k+1
đoạn đường
• Do chi phí phải trả cho mỗi đoạn trong n-k+1 đoạn còn
lại không ít hơn c
min
nên cận dưới cho phương án bộ
phận có thể tính theo công thức
g(u
1
, u
2
,…u
k
) = σ+(n-k+1)c
min
Các Ví dụ
Các Ví dụ
Các Ví dụ
Kết thúc thuật toán, ta thu được phương án tối
ưu (1,2,3,5,4,1) tương ứng với hành trình
T
1