1
Nguy n Đc Nghĩaễ ứ
Ch ng 4 ươ
BÀI TOÁN TỐI ƯU TỔ HỢP
BÀI TOÁN TỐI ƯU TỔ HỢP
2
Nguy n Đc Nghĩaễ ứ
N i dungộ
1. Phát biểu bài toán
2. Duyệt toàn bộ
3. Thuật toán nhánh cận
3
Nguy n Đc Nghĩaễ ứ
1. Phát bi u bài toánể
1.1. Bài toán tổng quát
1.2. Bài toán người du lịch
1.3. Bài toán cái túi
1.4. Bài toán đóng thùng
4
Nguy n Đc Nghĩaễ ứ
Trong r t nhi u v n đ ng d ng th c t ấ ề ấ ề ứ ụ ự ế
c a t h p, các c u hình t h p đ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. ẽ ọ ố ư ổ ợ
5
Nguy n Đc Nghĩaễ ứ
Phát bi u bài toánể
Díi d¹ng tæng qu¸t bµi to¸n tèi u tæ hîp
cã thÓ ph¸t biÓu nh sau:
T×m cùc tiÓu (hay cùc ®¹i) cña phiÕm
hµm
f(x) min (max),
víi ®iÒu kiÖn
x D,
trong ®ã D lµ tËp h÷u h¹n phÇn tö.