ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG

HOÀNG XUÂN THÁI

MỘT SỐ THUẬT TOÁN GIẢI BÀI TOÁN
PHỦ TẬP HỢP VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - Năm 2014


1

ĐẠI HOẠC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG

HOÀNG XUÂN THÁI

MỘT SỐ THUẬT TOÁN GIẢI BÀI TOÁN
PHỦ TẬP HỢP VÀ ỨNG DỤNG
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số

:

60.48.01


2.1.2. Bài toán phủ tập hợp........................................................................... 28
2.2. MỘT SỐ KẾT QUẢ LÝ THUYẾT VỀ BÀI TOÁN PHỦ TẬP HỢP ......... 29
2.2.1. Hướng tiếp cận giải bài toán SCP ......................................................... 29


3

2.2.2. Một số phương pháp tìm giải pháp gần tối ưu cho bài toán SCP........... 31
2.3. THUẬT TOÁN HEURISTIC GIẢI BÀI TOÁN PHỦ TẬP HỢP ............... 35
2.3.1. Thuật toán Heuristic ........................................................................... 35
2.3.2. Ứng dụng thuật toán Heuristics giải bài toán SCP .............................. 36
2.3.3. Tính hiệu quả của thuật toán Heuristic................................................ 45
2.4. THUẬT TOÁN CHÍNH XÁC .................................................................... 50
2.4.1. Ví dụ về thuật toán nhánh cận .................................................................. 50
2.4.2. Thuật toán chính xác giải bài toán SCP .................................................... 54
2.5. TỔNG KẾT CHƯƠNG .............................................................................. 57
Chương 3. CÀI ĐẶT CHƯƠNG TRÌNH VÀ ỨNG DỤNG ................................ 58
3.1. BÀI TOÁN PHÂN LỊCH TRỰC BÁC SĨ ................................................... 58
3.1.1. Phát biểu bài toán..................................................................................... 58
3.1.2. Cài đặt thuật toán tham lam...................................................................... 59
3.1.3. Cài đặt thuật toán Nhánh cận ................................................................... 60
3.2. XÂY DỰNG CHƯƠNG TRÌNH PHÂN LỊCH TRỰC BÁC SĨ .................. 64
3.2.1. Công cụ lựa chọn................................................................................ 64
3.2.2. Modul chương trình ............................................................................ 64
3.2.3. Giao diện chương trình ....................................................................... 66
3.3. THỬ NGHIỆM VÀ ĐÁNH GIÁ ................................................................ 70
3.4. TỔNG KẾT CHƯƠNG .............................................................................. 70
KẾT LUẬN VÀ KIẾN NGHỊ .............................................................................. 72
DANH MỤC TÀI LIỆU THAM KHẢO .............................................................. 74


Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin
chịu hoàn toàn trách nhiệm.

Thái Nguyên, ngày tháng năm 2014
Tác giả

Hoàng Xuân Thái


6

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
Tiếng Anh
Từ viết tắt

Tên đầy đủ

Diễn giải

GA

Genetic Algorithm

Giải thuật di truyền

LP

Linear Programming

Quy hoạch tuyến tính

BTQHL

Bài toán quy hoạch lồi

BTQHTP

Bài toán quy hoạch toàn phương


7

DANH MỤC BẢNG
Trang
Bảng 3.1. Danh sách các bác sĩ và các dịch vụ mà bác sĩ đó có thể thực hiện trong
trường hợp tổng quát ............................................................................................. 58
Bảng 3.2. Thời gian trung bình (miligiây).............................................................. 70


8

DANH MỤC HÌNH
Trang
Hình 1.1 Mô hình phân lớp các bài toán P, NP, CO-NP, NP-Complete, NP-hard 15
Hình 1.2. Đồ thị hàm f(x)

17

Hình 2.1. Thuật toán Meta-RaPS tìm giải pháp cơ sở

38


54

Hình 2.9. Cây phân nhánh giải bài toán người du lịch

54

Hình 3.1. Giao diện chính của chương trình

67

Hình 3.2. Giao diện nạp dữ liệu

68

Hình 3.3. Giao diện phân lịch bằng thuật toán tham lam

68

Hình 3.4. Giao diện phân lịch bằng thuật toán tham lam

69

Hình 3.5. Giao diện lưu kết quả phân lịch

69

Hình 3.6. Đồ thị biểu diễn thời gian thực hiện trung bình

70



10

3. Phạm vi nghiên cứu
Luận văn tập trung nghiên cứu các kiến thức có liên quan, các cơ sở lý thuyết
như: Lý thuyết các bài toán NP-hard, quy hoạch tuyến tính, quy hoạch nguyên, các
phương pháp giải chúng và áp dụng vào bài toán phủ tập hợp.
4. Nhiệm vụ nghiên cứu
-

Tìm hiểu và hệ thống các kiến thức cơ sở về lý thuyết các bài toán NP-hard

-

Tìm hiểu về quy hoạch toán học, bài toán phủ tập hợp và ứng dụng.

-

Tìm hiểu một vài thuật toán chính xác giải bài toán phủ tập hợp.

-

Cài đặt và thử nghiệm một vài thuật toán.

5. Những nội dung nghiên cứu chính
Bố cục của luận văn gồm phần mở đầu trình bày lý do chọn đề tài, đối tượng và
nhiệm vụ nghiên cứu của đề tài. Chương một, tập trung trình bày những kiến thức
tổng quan về lý thuyết NP-hard và quy hoạch toán học. Chương hai, giới thiệu bài
toán phủ tập hợp, một số kết quả lý thuyết về bài toán phủ tập hợp, trình bày thuật

KIẾN THỨC CƠ SỞ VỀ LÝ THUYẾT BÀI TOÁN NP-HARD

1.1.1. Định nghĩa về lớp bài toán P và NP
1.1.1.1. Khái niệm các loại thời gian tính
Thời gian tính tốt nhất: là thời gian tính tối thiểu cần thiết để thực hiện thuật
toán với mọi bộ dữ liệu đầu vào kích thước n.
Thời gian tính tồi nhất: là thời gian tính tối đa cần thiết để thực hiện thuật toán
với mọi bộ dữ liệu đầu vào có kích thước n.
Thời gian tính trung bình: là thời gian tính cần thiết để thực hiện thuật toán trên
một tập hữu hạn các bộ dữ liệu đầu vào có kích thước n. Thời gian tính trung bình
được tính theo công thức sau:
Thời gian tính trung bình=(Tổng thời gian tính tất cả các bộ dữ liệu có thể)/ Số
bộ dữ liệu.
Định nghĩa 1.1 [1]. Bài toán quyết định là bài toán mà đầu ra chỉ có thể là ‘yes’
hoặc ‘no’ (đúng/sai, 0/1).
Đối với một bài toán quyết định, có những bộ dữ liệu vào cho ra câu trả lời (đầu
ra) là ‘yes’, chúng ta gọi đây là bộ dữ liệu ‘yes’, nhưng cũng có những bộ dữ liệu
vào cho ra câu trả lời là ‘no’, chúng ta gọi những bộ dữ liệu này là bộ dữ liệu ‘no’.
1.1.1.2. Bằng chứng ngắn gọn dễ kiểm tra
Rất nhiều các bài toán quyết định có một đặc điểm chung, đó là để xác nhận câu
trả lời ặc điểm chung, đó là để xác nhận câu trả lời ‘yes’ đối với bộ dữ liệu vào
‘yes’ của chúng, chúng ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận
câu trả lời ‘yes’ cho bộ dữ liệu vào ‘yes’ đó. Tính ngắn gọn dễ kiểm tra ám chỉ việc
thời gian kiểm tra để đưa ra kết quả chỉ mất thời gian đa thức. Ví dụ về những bài
toán quyết định kiểu này:
-

Bài toán kiểm tra tính hợp số: “Có phải số n là hợp số?”, để xác nhận câu trả
lời ‘yes’ cho đầu vào n, chúng ta có thể đưa ra một ước số b (1
ta nói A có thể quy dẫn về B nếu như sau một thời gian tính đa thức nếu tồn tại một
thuật toán thời gian đa thức R cho phép biến đổi bộ dữ liệu x của A thành bộ dữ
liệu vào R(x) của B sao cho x là bộ dữ liệu yes của A khi và chỉ khi R(x) là dữ liệu
vào yes của B.
Nếu A quy dẫn về được B sau thời gian đa thức và B có thể giải được sau thời
gian đa thức thì A cũng có thể giải được sau thời gian đa thức.
1.1.1.4. Lớp bài toán P.
Định nghĩa 1.3 [1]. Chúng ta gọi P là lớp các bài toán có thể giải được trong
thời gian đa thức, NP là lớp các bài toán quyết định mà để xác định câu trả lời


13

“yes” của nó chúng ta có thể đưa ra các bằng chứng ngắn gọn dễ kiểm tra, co-NP
là lớp các bài toán quyết định mà để xác định câu trả lời “no” của nó chúng ta có
thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ 1.1. Bài toán cây khung nhỏ nhất giải được nhờ thuật toán Prim với thời
gian O(n2) thuộc lớp bài toán P.
1.1.1.5. Lớp bài toán NP
Định nghĩa 1.4 [1]. Ta gọi NP là lớp các bài toán quyết định mà để xác nhận
câu trả lời “yes” của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ 1.2. Bài toán kiểm tra tính hợp số: “Có phải n là hợp số không?”, để xác
nhận câu trả lời “yes” cho đầu vào n ta có thể đưa ra một ước số b (1
đủ trong đồ thị G).
Bài toán tập độc lập (Independsent 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.
Bài toán phủ đỉnh (Vertex cover ): Ta gọi một phủ 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?
Một cách không hình thức, có thể nói rằng nếu ta có thể giải được một cách hiệu quả
một bài toán NP-khó cụ thể, thì ta cũng có thể giải hiệu quả bất kỳ bài toán NP bằng cách
sử dụng thuật toán giải bài toán NP-khó như một chương trình con.
Từ định nghĩa bài toán NP-khó có thể suy ra rằng mỗi bài toán NP-đầy đủ đều là NPkhó. Tuy nhiên một bài toán NP-khó không nhất thiết phải là NP-đầy đủ.
Cũng từ bổ đề nêu trên, ta có thể suy ra rằng để chứng minh một bài toán A nào đó là
NP-khó, ta chỉ cần chỉ ra phép qui dẫn một bài toán đã biết là NP-khó về nó.
Từ phần trình bày trên, ta thấy có rất nhiều bài toán ứng dụng quan trọng thuộc vào
lớp NP-khó, và vì thế khó hy vọng xây dựng được thuật toán đúng hiệu quả để giải chúng.


15

Do đó, một trong những hướng phát triển thuật toán giải các bài toán như vậy là xây dựng
các thuật toán gần đúng.

Hình 1.1 Mô hình phân lớp các bài toán P, NP, CO-NP, NP-Complete và NPhard
1.2.

LÝ THUYẾT QUY HOẠCH TOÁN HỌC

Tối ưu hóa, được khởi nguồn như một ngành của Toán học, có rất nhiều ứng

-

Tính toán thử và điều chỉnh mô hình nếu cần.

-

Áp dụng giải các bài toán thực tế.

1.2.1. Khái niệm chung
1.2.1.1. Bài toán tối ưu tổng quát

Tối ưu hóa là một trong những lĩnh vực kinh điển của toán học có ảnh hưởng
đến hầu hết các lĩnh vực khoa học – công nghệ và kinh tế - xã hội. Trong thực tế,
việc tìm giải pháp tối ưu cho một vấn đề nào đó chiếm một vai trò hết sức quan
trọng. Phương pháp tối ưu là phương pháp hợp lý nhất, tốt nhất, tiết kiệm chi phí,
tài nguyên, nguồn lực mà lại cho hiệu quả cao.
Ví dụ 1.4. Tìm

x  D   2.2,1.8  R1

3
sao cho f ( x)  x  3x  1  Max

Bài toán tối ưu trên có dạng cực đại hóa được giải như sau: Cho
f '( x)  3x 2  3  0 , ta có các điểm tới hạn là x=-1 và x=+1. Xét giá trị hàm số f(x) tại

thời điểm tới hạn vừa tìm được và tại các giá trị x = -2.2 và x = 1.8 (các điểm đầu
mút của đoạn [-2.2, 1.8]), ta có f(-2.2) = -3.048, f(-1)=3, f(1.8)= 1.432. Vậy giá trị x
cần tìm là x= -1. Kết quả của bài toán được minh họa trên hình I.1


được gọi là điểm tối ưu (hay phương án tối ưu) toàn cục nếu x  D và

f ( x* )  f ( x ), x  D . Điểm x  R n được gọi là điểm tối ưu (hay phương án tối ưu)


18

địa phương nếu x  D và tồn tại một lân cận N đủ nhỏ của điểm x sao cho
f ( x)  f ( x), x  N  D .
n
*
n
Đối với bài toán cực tiểu hóa Min f(x), với x  D  R , điểm x  R được gọi là

*
*
điểm tối ưu (hay phương án tối ưu) toàn cục nếu x  D và f ( x )  f ( x ), x  D .

n
Điểm x  R được gọi là điểm tối ưu (hay phương án tối ưu) địa phương nếu x  D

và tồn tại một lân cận N đủ nhỏ của điểm x sao cho f ( x)  f ( x), x  N  D .
Dễ thấy, mọi phương án tối ưu toàn cục cũng là phương án tối ưu địa phương,
trong khi đó một phương án tối ưu địa phương không nhất thiết là phương án tối ưu
toàn cục. Trên hình …, điểm x=1 chỉ là phương án tối ưu địa phương khi xét bài
toán cực tiểu hóa.
Ví dụ 1.5. Xét bài toán tối ưu sau: Max f(x)= 8 x1  6 x2 với điều kiện ràng buộc
x  D   x1 , x2   R 2 : 4 x1  2 x2  60; 2 x1  4 x2  48, x1  0, x2  0

Bài toán tối ưu trên đây còn được gọi là bài toán quy hoạch tuyến tính. Người ta

-

Bài toán quy hoạch ngẫu nhiên/ mờ …

Các phương pháp toán học giải các lớp bài toán tối ưu tổng quát như nêu trên
đây được gọi là các phương pháp tối ưu toán học (hay các phương pháp quy hoạch
toán học).
1.2.2. Quy hoạch tuyến tính
1.2.2.1. Phát biểu bài toán
Bài toán quy hoạch tuyến tính trong [2] là bài toán có dạng
n

x0   c j x j  max

(1)

j 1

n

a x
ij

j

 bi , i  1, 2,..., l

(2)

j


20

 L – miền xác định của bài toán (1) – (4)
 (L, C) – kí hiệu bài toán qui hoạch tuyến tính (1) – (4)
 X(L, C) – phương án tối ưu của bài toán (1) – (4)


X (L, C) – phương án tối ưu mở rộng của bài toán (1) – (4)

 LC là tập hợp các phương án tối ưu của bài toán (L, C)
 Bài toán quy hoạch tuyến tính gọi là giải được nếu tồn tại phương án tối
ưu.
1.2.2.2. Dạng chính tắc của bài toán qui hoạch tuyến tính
n

x0   c j x j  max

(5)

j 1

n

a x
ij

j

 bi , i  1, 2,..., m



21

Cơ sở của phương án tựa X là tập hợp

A



x j  0 . Các thành phần của phương

j

án tựa ứng với các vectơ cơ sở gọi là các thành phần cơ sở (các biến tương ứng gọi
là biến cơ sở), các thành phần còn lại gọi là các thành phần phi cơ sở (các biến
tương ứng gọi là biến cơ sở).
Nếu X   x1 ,..., xn  phương án tựa của bài toán quy hoạch tuyến tính,
( Aj1 ,..., Ajk ) là cơ sở của phương án tựa, B   j1 ,..., jk  , N  1,.., n \ B thì hàm mục

tiêu

x0 , x1 ,..., xn

có

thể

biểu


Phương án tựa X của bài toán (5) – (7) là không suy biến nếu các thành phần cơ
sở của nó là dương. Cơ sở của phương án tựa không suy biến xác định duy nhất.
Ứng với phương án tựa suy biến có nhiều cơ sở.
Tiêu chuẩn tối ưu: để cho phương án mở rộng X '   x0' , x1' ,..., xn'  là tối ưu điều
kiện cần và đủ là tồn tại cơ sở B sao cho
xi  xi'   xij ( x j ), i  0,1,..., n
jN

x0 j  0, j  N


22

Giả sử ràng buộc (6) của bài toán (5) – (7) viết ở dạng:
xi  xi 0   xij ( x j ), i  0,1,..., n
jN

Bảng đơn hình tương ứng T  xij

iQ n , jN 0

,

X   x1 , x2 ,..., xn   ( x10 , x20 ,..., xn 0 ),
n

X   x1 , x2 ,..., xn   ( c j x j , x1 ,..., xn ).
j 1

Nếu xi 0  0 (i  1, 2,..., n) thì bảng đơn hình T gọi là chấp nhận được, vectơ X là

là bài toán quy hoạch nguyên hoàn toàn. Còn nếu q>0 thì bài toán được gọi là bài
toán nguyên bộ phận.
1.2.3.2. Các bài toán thực tế dẫn tới quy hoạch rời rạc
 Bài toán vận tải
Có m kho hàng (điểm phát) chứa một loại hàng hóa, lượng hàng ở kho i là ai và
n nơi tiêu thụ (điểm thu), nhu cầu ở nơi thu là b j , cij là chi phí vận chuyển một đơn
vị hàng từ điểm phát i đến điểm thu j. Xác định các lượng hàng vận chuyển xij từ
các điểm phát i tới các điểm thu j sao cho tổng chi phí là nhỏ nhất và nhu cầu các
điểm thu được thỏa mãn.
Dạng toán học của bài toán là:

c x

ij ij

 min

(9)

ij
n

x

ij

 ai , i  1, 2,..., m

(10)



Nếu các ai và bj là nguyên thì đa diện lồi xác định bởi các ràng buộc của bài
toán có mọi đỉnh đều là nguyên. Do đó ta có thể dùng phương pháp đơn hình để giải
bài toán quy hoạch tuyến tính này, lời giải cuối cùng nhận được sẽ là một phương


24

án nguyên.
 Bài toán phân việc
Có n đơn vị sản xuất cần sản xuất n loại sản phẩm, cij là chi phí cho đơn vị i sản
xuất sản phẩm j. Hãy phân công mỗi đơn vị sản xuất một sản phẩm để tổng chi phí
là nhỏ nhất.
Dạng toán học của bài toán là:
n

n

 c x

ij ij

 min

i 1 j 1

n

x


 max

j

b

j 1
n

a x
j

j 1

x j  0, x j  Z

 Bài toán xếp hàng lên tàu
Một tàu chở hàng có trọng tải T và thể tích K, tàu chở n loại hàng, hàng loại j có
số lượng là sj, có trọng lượng là aj, thể tích bj và giá trị sử dụng là cj. Bài toán đặt ra