Số hóa bởi Trung tâm Học liệu
ĐẠ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
MỤC LỤC
Trang
LỜI CẢM ƠN 4
LỜI CAM ĐOAN 5
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT 6
DANH MỤC BẢNG 7
DANH MỤC HÌNH 8
MỞ ĐẦU 9
Chƣơng 1. TỔNG QUAN 11
1.1. KIẾN THỨC CƠ SỞ VỀ LÝ THUYẾT BÀI TOÁN NP-HARD 11
1.1.1. Định nghĩa về lớp bài toán P và NP 11
1.1.2. Các ví dụ về bài toán NP 14
1.2. LÝ THUYẾT QUY HOẠCH TOÁN HỌC 15
1.2.1. Khái niệm chung 16
1.2.2. Quy hoạch tuyến tính 19
1.2.3. Quy hoạch rời rạc 22
1.3. TỔNG KẾT CHƢƠNG 25
Chƣơng 2. BÀI TOÁN PHỦ TẬP HỢP 26
2.1. GIỚI THIỆU BÀI TOÁN PHỦ TẬP HỢP 26
2.1.1. Một số ví dụ về bài toán phủ tập hợp 26
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 Số hóa bởi Trung tâm Học liệu
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
Thái Nguyên đã tận tình giúp đỡ, tạo mọi điều kiện thuận lợi cho em trong quá
trình học tập, nghiên cứu và thực hiện luận văn.
Đặc biệt, em xin gửi lời tri ân sâu sắc đến GS. TS Đặng Quang Á – người đã
dành nhiều thời gian, công sức và tận tình hướng dẫn khoa học cho em trong suốt
quá trình hình thành và hoàn chỉnh luận văn.
Xin chân thành cảm ơn Quý Thầy, Cô đã giảng dạy, truyền đạt cho em
những tri thức quý báu, thiết thực trong suốt khóa học.
Cuối cùng xin bày tỏ lòng biết ơn đối với gia đình, người thân, bạn bè, đồng
nghiệp đã giúp đỡ, động viên, đóng góp ý kiến quý báu cho em trong việc hoàn
thành luận văn này.
Thái Nguyên, ngày tháng năm 2014
Tác giả Hoàng Xuân Thái
5 Số hóa bởi Trung tâm Học liệu
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi dưới sự hướng
dẫn trực tiếp của GS.TS. Đặng Quang Á.
Mọi trích dẫn sử dụng trong báo cáo này đều được ghi rõ nguồn tài liệu
tham khảo theo đúng qui định.
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.
Giải thuật luyện thép
SCP
Set Covering Problem
Bài toán phủ tập hợp
Tiếng Việt
BTQHTT
Bài toán quy hoạch tuyến tính
BTQHPT
Bài toán quy hoạch phi tuyến
BTQHL
Bài toán quy hoạch lồi
BTQHTP
Bài toán quy hoạch toàn phƣơng
7 Số hóa bởi Trung tâm Học liệu 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 Số hóa bởi Trung tâm Học liệu
Bài toán tối ƣu tổ hợp là dạng bài toán có độ phức tạp tính toán cao thuộc lớp
NP khó. Đã có nhiều giải thuật đƣợc đƣa ra để giải quyết bài toán trên nhƣ họ giải
thuật kiến (Ant Algorithm), giải thuật luyện thép SA (Simulated Annealing), giải
thuật di truyền GA (Genetic Algorithm) và giải thuật Meta-Heuristic. Những giải
thuật này đã giải quyết các bài toán với hiệu quả cao và cho kết quả lời giải gần tối
ƣu.
Với độ phức tạp tính toán cao của các bài toán tối ƣu tổ hợp cũng nhƣ đòi hỏi
về mặt thời gian, việc giải các bài toán này với tính chất tuần tự của các giải thuật sẽ
gặp phải những vấn đề về thời gian thực hiện chƣơng trình, tốc độ xử lý, khả năng
lƣu trữ của bộ nhớ, xử lý dữ liệu với quy mô lớn, … Kích thƣớc bài toán tăng lên và
không gian tìm kiếm càng lớn yêu cầu cần phải có các giải thuật để tăng tốc độ và
hiệu quả của giải thuật.
Bài toán phủ tập hợp (set covering problem) là một bài toán tối ƣu tổ hợp cơ
bản. Dạng bài toán này có rất nhiều trong thực tế nhƣ: lập lịch biểu, lập kế hoạch
sản xuất, định tuyến, phân bổ đầu tƣ, …Đã có nhiều nghiên cứu về phƣơng pháp
hiệu quả để giải quyết bài toán này bao gồm các giải thuật heuristic, thuật toán sử
dụng ý tƣởng tham lam (Greedy Method) và các thuật toán sử dụng các phƣơng
pháp của quy hoạch nguyên.
Vì vậy, việc tìm hiểu bài toán dạng phủ tập hợp, các thuật toán giải quyết bài
toán để từ đó ứng dụng vào trong thực tế là một việc làm có ý nghĩa khoa học và
thực tiễn. Đây chính là mục đích của luận văn này.
2. Đối tƣợng nghiên cứu
Đối tƣợng nghiên cứu của luận văn này là bài toán phủ tập hợp và các vấn đề
liên quan, các thuật toán để giải quyết pài toán phủ tập hợp. 10 Số hóa bởi Trung tâm Học liệu
Số hóa bởi Trung tâm Học liệu
Chƣơng 1. TỔNG QUAN
1.1. 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<b<n) của n.
Để kiểm tra xem b có phải là ƣớc số của n chúng ta có thể thực hiện phép chi
xác định câu trả lời „no‟. Đối với mỗi bài toán, việc đƣa ra bằng chứng ngắn gọn dễ
kiểm tra để xác nhận câu trả lời „no‟ là dễ dàng hơn so với việc đƣa ra bằng chứng
ngắn gọn xác định câu trả lời là „yes‟.
1.1.1.3. Khái niệm quy dẫn
Định nghĩa 1.2 [1]. Giả sử chúng ta có hai bài toán quyết định A và B. Chúng
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 Số hóa bởi Trung tâm Học liệu
“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(n
2
) 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
1.1.2. Các ví dụ về bài toán NP
Bài toán bè cực đại (MaxClique): Cho đồ thị vô hƣớng G=(V, E). V là tập các
đỉnh, E là tập các cạnh tƣơng ứng các đỉnh trong V. Cần tìm bè lớn nhất của G. Bè
là tập các đỉnh trong đồ thị mà đôi một có cạnh nối với nhau (là một đồ thị con đầy
đủ 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à NP-
khó. 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 Số hóa bởi Trung tâm Học liệu
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à NP-
đế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
1
2.2,1.8x D R
sao cho
3
( ) 3x 1 axf x x M
Bài toán tối ƣu trên có dạng cực đại hóa đƣợc giải nhƣ sau: Cho
2
'( ) 3x 3 0fx
, 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
17 Số hóa bởi Trung tâm Học liệu Hình 1.2. Đồ thị hàm f(x)
Cho hàm số
:
n
f D R R
. Bài toán tối ƣu tổng quát có dạng: Max (Min) f(x),
* * * *
12
( , , , )
n
n
x x x x R
đƣợc gọi là điểm tối ƣu (hay phƣơng án tối ƣu) toàn cục nếu
*
xD
và
*
( ) ( ),f x f x x D
. Điểm
n
xR
đƣợc gọi là điểm tối ƣu (hay phƣơng án tối ƣu)
18 Số hóa bởi Trung tâm Học liệu
địa phƣơng nếu
xD
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
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)=
12
86xx
với điều kiện ràng buộc
2
1 2 1 2 1 2 1 2
, :4 2 60;2 4 48, 0, 0x D x x R x x x x x x
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
đã chứng minh đƣợc rằng mọi phƣơng án tối ƣu địa phƣơng của bài toán quy hoạch
tuyến tính cũng đồng thời là phƣơng án tối ƣu toàn cục.
1.2.1.2. Phân loại các bài toán tối ưu
Các bài toán tối ƣu, cũng đƣợc gọi là các bài toán quy hoạch toán học, đƣợc chia
thành các lớp sau [2]:
- Bài toán quy hoạch tuyến tính (BTQHTT)
- Bài toán tối ƣu phi tuyến hay còn gọi là bài toán quy hoạch phi tuyến
(BTQHPT), bao gồm cả bài toán quy hoạch lồi (BTQHL) và bài toán quy
hoạch toàn phƣơng (BTQHTP).
- Bài toán tối ƣu rời rạc, bài toán tối ƣu nguyên và hỗn hợp nguyên.
- Bài toán quy hoạch động.
19 Số hóa bởi Trung tâm Học liệu
- Bài toán quy hoạch đa mục tiêu.
- 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
a x b i l m
(3)
0, 1, ,
j
x j n
(4)
Miền xác định: tập hợp các véc tơ x thỏa mãn (2) và (4)
Phƣơng án bài toán: véc tơ x thỏa mãn (2) và (4)
Nếu
1
( , , )
n
xx
là phƣơng án của bài toán,
0
1
n
jj
j
x c x
thì
01
( , , , )
n
X x x x
gọi là
phƣơng án mở rộng của bài toán (1) – (4).
Phƣơng án
0
1
ax
n
jj
j
x c x m
(5)
ij
1
, 1,2, ,
n
ji
j
a x b i m
(6)
0, 1, ,
j
x j n
(7)
Gọi
1
2
.
.
j
j
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
1
, ,
n
X x x
phƣơng án tựa của bài toán quy hoạch tuyến tính,
1
( , , )
j jk
AA
là cơ sở của phƣơng án tựa,
1
, , , 1, , \
k
B j j N n B
thì hàm mục
tiêu
01
, , ,
n
x x x
có thể biểu diễn qua các biến phi cơ sở:
0 ij
( ), 0,1, ,
i i j
jN
x x x x i n
là tối ƣu điều
kiện cần và đủ là tồn tại cơ sở B sao cho
'
ij
( ), 0,1, ,
i i j
jN
x x x x i n0
0,
j
x j N
22 Số hóa bởi Trung tâm Học liệu
Giả sử ràng buộc (6) của bài toán (5) – (7) viết ở dạng:
0 ij
( ), 0,1, ,
i i j
jN
x x x x i n
phƣơng án tựa của bài toán quy hoạch tuyến tính.
Nếu
0
0,
j
x j N
thì bảng đơn hình T là chuẩn (đối ngẫu chấp nhận đƣợc),
vectơ X gọi là giả phƣơng án,
X
gọi là giả phƣơng án mở rộng.
1.2.3. Quy hoạch rời rạc
1.2.3.1. Định nghĩa [2]
Trong các bài toán quy hoạch tuyến tính, các biến số có thể nhận những giá trị
thực không âm. Tuy nhiên, trong thực tiễn thƣờng gặp các bài toán mà các biến số
chỉ có thể nhận một số hữu hạn hay đếm đƣợc giá trị, thƣờng là các giá trị nguyên.
Chẳng hạn sẽ là vô nghĩa khi đƣa ra câu trả lời: cần sản xuất nửa cái bàn hay cần
thuê 2,7 cái ô tô để vận chuyển hàng hóa … Trong một số bài toán, chẳng hạn bài
toán vận tải với các lƣợng hàng cung và cầu là các số nguyên, song nhiều bài toán
khác thì không phải nhƣ vậy. vì thế trong chƣơng này sẽ đề cập đến nội dung và
phƣơng pháp giải các bài toán tối ƣu trên lƣới các điểm nguyên hay trên các tập rời
rạc, gọi tắt là bài toán quy hoạch rời rạc hay bài toán quy hoạch nguyên. Bài toán
quy hoạch rời rạc có dạng sau:
Tìm cực đại của hàm
( , )f x y
phụ thuộc hai nhóm biến x và y với các ràng buộc
có dạng:
23
a
và
n nơi tiêu thụ (điểm thu), nhu cầu ở nơi thu là
ij
,
j
bc
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 x
ij
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à:
ij ij
ij
mincx
(9)
ij
1
, 1,2, ,
n
i
j
x a i m
(10)
ij
á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, c
ij
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à:
ij ij
11
min
nn
ij
cxij
1
1, 1,2, ,
n
j
x i nij
1
1, 1,2, ,
m
i
a x b0,
jj
x x 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à s
j
, có trọng lƣợng là a
j
, thể tích b
j
và giá trị sử dụng là c
j
. Bài toán đặt ra
Copyright: Tài liệu đại học ©