NP - Complete
2013-11-25 2
Một số bài toán tối ưu rời rạc
Bài toán người du lịch:
Cho n điểm trên mặt phẳng (thành phố), giữa hai thành phố bất kỳ
được xác định một thông số là chi phí đi lại. Một hành trình là một
cách đi xuất phát từ một thành phố nào đó, qua n thành phố và quay
về nơi xuất phát.
OP (Optimization Problem): Tìm hành trình * có tổng chi phí bé nhất.
DP (Decision Problem): Có tồn tại một hành trình với chi phí D?
2013-11-25 3
Một số bài toán tối ưu rời rạc
Bài toán tô màu đồ thị:
Cho đồ thị G ={V,E}.
OP: Số màu ít nhất để tô đồ thị G?
DP: Cho số nguyên K. Có tồn tại hay không cách tô màu đồ thị
G với số màu không quá K?
Một cách tô màu đồ thị là một phương án gán cho mỗi đỉnh một màu, sao
cho hai đỉnh liền kề có hai màu khác nhau.
2013-11-25 4
Một số bài toán tối ưu rời rạc
Bài toán cái túi:
Cho n đồ vật với kích thước là các số nguyên s1, s2, ..., snvà các túi
với kích thức là số nguyên T.
OP: Tìm số túi ít nhất để xếp các đồ vật.
DP: Cho số nguyên K. Có tồn tại cách xếp các đồ vật vào không quá K
túi với sức chứa T?
2013-11-25 5
Một số bài toán tối ưu rời rạc
Bài toán tập con:
Cho số nguyên dương T và tập X gồm nsố nguyên dương a1, a2, ..., an.
OP: Xác định tập con của X sao cho tổng của chúng gần nhất và không
quá T.
DP: Có tồn tại tập con sao cho tổng kích thước đúng bằng T.