ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
LÊ THANH BÌNH
PHƯƠNG PHÁP LAI MẠNG NƠ RON
GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN NP-C
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH
THÁI NGUYÊN 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
LÊ THANH BÌNH
PHƯƠNG PHÁP LAI MẠNG NƠ RON
GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN NP-C
VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS- TS. ĐẶNG QUANG Á
THÁI NGUYÊN 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-i-
MỤC LỤC
TRANG PHỤ BÌA
LỜI CAM ĐOAN
MỤC LỤC ............................................................................................................... i
DANH MỤC CÁC BẢNG…………………………………………….…...………iii
DANH MỤC CÁC HÌNH ...................................................................................... iv
LỜI NÓI ĐẦU………………………………………………………………………1
CHƢƠNG I: GIỚI THIỆU SƠ LƢỢC VỀ CÁC BÀI TOÁN NP-C......................... 3
1.1. Giới thiệu chung về bài toán NP-C ................................................................ 3
1.2. Cách tiếp cận giải bài toán NP-C ................................................................... 4
1.2.1. Một số khái niệm ................................................................................... 4
1.2.2. Giới thiệu một số thuật toán xấp xỉ giải bài toán NP-C .......................... 5
1.2.3. Các thuật toán gần đúng ........................................................................ 6
1.2.4. Tô mầu đồ thị với bài toán 4 mầu ........................................................ 13
1.2.5. Bài toán phẳng hóa đồ thị .................................................................... 15
1.3. Kết luận ......................................................................................................... 17
CHƢƠNG II : MẠNG NƠ RON VÀ THUẬT GIẢI DI TRUYỀN GIẢI BÀI TOÁN
TỐI ƢU ................................................................................................................. 18
2.1. Giới thiệu về mạng nơ-ron ........................................................................... 18
2.1.1. Lịch sử phát triển................................................................................. 18
2.1.2. Mô hình mạng nơ-ron nhân tạo............................................................ 19
2.2. Phạm vi ứng dụng của mạng nơ-ron ........................................................... 23
2.2.1. Những bài toán thích hợp .................................................................... 23
2.2.2. Các lĩnh vực ứng dụng mạng nơ-ron .................................................... 23
2.2.3. Ƣu và nhƣợc điểm của mạng nơ-ron .................................................... 24
2.3. Mạng Hopfield .............................................................................................. 24
2.3.1. Mạng Hopfield rời rạc ......................................................................... 26
2.3.2 Mạng Hopfield liên tục ......................................................................... 27
2.4. Giới thiệu thuật giải di truyền ...................................................................... 28
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- ii -
2.4.1. Các tính chất đặc thù của thuật giải di truyền ....................................... 29
2.4.2. Các bƣớc quan trọng trong việc áp dụng thuật giải di truyền ............... 29
2.4.3. Ví dụ minh họa .................................................................................... 31
2.4.4. Các phƣơng thức biến hóa của giải thuật di truyền .............................. 34
2.4.5. Các giải thuật di truyền lai ................................................................... 38
2.5. Giải thuật di truyền với bài toán tối ƣu ....................................................... 39
2.5.1. Ánh xạ hàm mục tiêu sang hàm phù hợp ............................................. 39
2.5.2. Tỷ lệ hoá giá trị phù hợp...................................................................... 40
2.5.3. Mã hoá tham biến nhờ véctơ nhị phân ................................................. 41
2.5.4. Bài toán tối ƣu ràng buộc..................................................................... 41
2.6. Mạng nơ ron Hopfield - giải thuật di truyền giải bài toán tối ƣu. .............. 42
2.7. Kết luận ......................................................................................................... 44
CHƢƠNG 3: ỨNG DỤNG THUẬT GIẢI DI TRUYỀN GIẢI BÀI TOÁN PHÂN
CÔNG NHIỆM VỤ ............................................................................................... 45
3.1. Giới thiệu ...................................................................................................... 45
3.2. Đị nh nghĩa bài toán ...................................................................................... 47
3.3. Ứng dụng Thuật giải di truyền vào bài toán ............................................... 48
3.3.1. Mã hóa: ............................................................................................... 49
3.3.2. Toán tử chọn cá thể ............................................................................. 50
3.3.3. Toán tử lai ghép và toán tử đột biến..................................................... 51
3.3.4. Sƣ̉a chƣ̃a giải pháp .............................................................................. 52
3.3.5. Tìm kiếm cục bộ .................................................................................. 54
3.4. Thí nghiệm và nhận xét ................................................................................ 55
3.4.1. Thí nghiệm .......................................................................................... 55
3.4.2. Nhận xét .............................................................................................. 56
3.5. Kết luận ......................................................................................................... 57
KẾT LUẬN……………………..………………………………………………….58
TÀI LIỆU THAM KHẢO………….….…………………………………………...59
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- iii -
DANH MỤC BẢNG
Bảng 3.1: Các ứng dụng toán tử lai ghép thực hiện trong GGA.
52
Bảng 3.2: Các ứng dụng toán tử đột biến thực hiện trong GGA.
52
Bảng 3.3: Ví dụ về các sở thích của sinh viên
53
Bảng 3.4: Ví dụ về các sở thích của sinh viên
54
Bảng 3.5: Số sinh viên trong nhóm thứ i trong những giải pháp đƣợc
tìm thấy bởi GGA.
Bảng 3.6: So sánh các kết quả thu đƣợc bằng GGA và thuật toán
tham lam GRAH.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
56
57
http://www.lrc-tnu.edu.vn
- iv -
DANH MỤC CÁC HÌNH
Hình 1.1: Bản dồ 9 nƣớc chƣa tô màu.
14
Hình 1.2: Bản dồ 9 nƣớc tô bởi 4 mầu.
14
Hình 1.3: Đồ thị 6 cạnh.
16
Hình 1.4: Hình (a) và (b) là đồ thị phẳng.
16
Hình 1.5: Đồ thị trên một hàng đơn.
17
Hình 2.1: Mô hình nơ ron sinh học.
19
Hình 2.2 : Mô hình một Nơ-ron .
21
Hình 2.3: Mô hình mạng Hopfield.
25
Hình 2.4: Lƣu đồ mô tả cấu trúc của giải thuật di truyền.
31
Hình 2.5: Lƣu đồ thuật toán của quá trình chọn lọc.
35
Hình 2.6: Lƣu đồ thuật toán quá trình lai ghép.
36
Hình 2.7: Lƣu đồ thuật toán của quá trình đột biến .
37
Hình 2.8: Lƣu đồ thuật toán của giải thuật lai.
42
Hình 2.9: Ví dụ về biểu diễn nơ ron của bài toán với N = 4.
44
Hình 3.1: Ví dụ về sở thích của các sinh viên trong 5 nhóm.
55
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-0-
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-1-
LỜI NÓI ĐẦU
Trong thực tế có rất nhiều bài toán phức tạp thuộc lớp bài toán NP- C
và bài toán tối ƣu có ràng buộc, cũng có nhiều công trình nghiên cứu để giải
quyết các bài toán đó. Ví dụ nhƣ: Bài toán tìm đƣờng đi ngắn nhất, bài toán
tô màu bản đồ, bài toán vận tải... Xong các giải thuật đƣa ra thƣờng phức
tạp mà chƣa có thuật toán đơn giản và hợp lý. Những năm gần đây trên thế
giới đã đƣa ra phƣơng pháp lại mạng Nơ ron Hopfield và thuật giải di truyển
nhằm giải quyết các bài toán tối ƣu thuộc lớp NP-C và đƣợc áp dụng rộng
rãi trong lĩnh vực Công nghệ thông tin. Việc nghiên cứu và áp dụng những
thành tựu mới vào việc phân tích, thiết kế, phân công nhiệm vụ là một trong
những vấn đề nóng đang rất đƣợc quan tâm.
Nhận thức đƣợc vấn đề đó và có sự gợi ý, định hƣớng của PGS .TS
Đặng Quang Á em đã mạnh dạn nghiên cứu đề tài " Phương pháp lai
mạng nơ ron - giải thuật di truyền giải bài toán NP-C và ứng dụng". Nội
dung cơ bản của luận văn gồm có ba chƣơng:
Chƣơng một giới thiệu sơ lƣợc về một số bài toán NP-C, cách tiếp cận
giải các bài toán NP-C nhƣ: bài toán tô mầu đồ thị, bài toán phẳng hóa đồ
thị, bài toán chọn đồng tiền…, trình bầy các cách tiếp cận tới việc giải quyết
các bài toán nêu trên.
Chƣơng hai giới thiệu sơ lƣợc về mạng nơ ron, mạng nơ ron Hopfield,
giải thuật di truyền. Đặc biệt trình bầy phƣơng pháp lai mạng Hopfield và
giải thuật di truyền giải bài toán tối ƣu.
Chƣơng ba ứng dụng giải thuật di truyền giải bài toán phân lịch thực
hành tại các trƣờng Đại học. Đây là bài toán có tính ứng dụng thực tế cao
trong nhiều lĩnh vực nhƣ phân công nhiệm vụ trong các đơn vị, xắp sếp lịch
biểu... Bài toán thuộc lớp NP-C. Vì vậy, ứng dụng giải thuật di truyền trong
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-2-
bài toán phân công nhiệm vụ trong hệ thống tính toán hỗn tạp sẽ hứa hẹn là
một gải pháp khả thi góp phần nâng cao hiệu quả trong công việc phân công,
điều hành của con ngƣời.
Qua luận văn này em xin chân thành cảm ơn: PGS .TS Đặng Quang Á Viện Công nghệ thông tin đã tận tình giúp đỡ, động viên, định hƣớng, hƣớng
dẫn em nghiên cứu và hoàn thành luận văn. Em xin cảm ơn các thầy cô giáo
trong viện Công nghệ thông tin, các thầy cô giáo khoa Công nghệ thông tin
ĐH Thái nguyên, đã giảng dạy và giúp đỡ em trong hai năm học vừa qua,
cảm ơn sự giúp đỡ nhiệt tình của các bạn đồng nghiệp.
Xin chân thành cảm ơn!
Thái Nguyên, tháng 11 năm 2010
Ngƣời viết luận văn
Lê Thanh Bình
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-3-
CHƢƠNG I
GIỚI THIỆU SƠ LƢỢC VỀ CÁC BÀI TOÁN NP-C
1.1. Giới thiệu chung về bài toán NP-C
Quá trình khám phá các bài toán thuộc loại NP-C cho ta biết rằng có rất
ít cơ hội phát triển đƣợc một thuật toán hiệu quả để giải nó. Điều đó khuyến
khích ta tìm kiếm các heuristic, các lời giải từng phần, các xấp xỉ và những
cách khác nhằm tránh giải trực diện bài toán.
Mỗi lần đƣa thêm một bài toán vào danh sách các bài toán NP-C chúng
ta lại củng cố thêm ý tƣởng rằng tất cả mọi bài toán NP-C đều đòi hỏi thời
gian mũ.
Định nghĩa 1.1: Ta nói L là bài toán thuộc loại NP-complete nếu các
khẳng định sau đều đúng:
1) L thuộc NP.
2) Với mọi ngôn ngữ L' ∈ NP có một phép thu thời gian đa thức L' về L.
Bài toán NP-complete đầu tiên chúng ta sẽ xét là bài toán thỏa SAT
(Boolean satisfiability). Chúng ta sẽ chứng tỏ rằng ngôn ngữ của mọi máy
Turing không đơn định (NTM) thời gian đa thức đều có một phép thu thời
gian đa thức về SAT. Khi đã có đƣợc một số bài toán thuộc NP-complete
(NP-C) chúng ta có thể chứng minh một bài toán mới thuộc NP-C bằng cách
thu một bài toán đã biết là NP-C về bài toán đó nhờ một phép thu thời gian đa
thức [ 1].
Định lý dƣới đây cho biết vì sao một phép thu nhƣ thế chứng minh đƣợc
bài toán đích là NP-C.
Định lý 1.1: Nếu bài toán P1 là NP-C, P2 là NP và có một phép thu
thời gian đa thức từ P1 về P2 thì P2 cũng là NP-C.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-4-
Chứng minh: Ta cần chứng tỏ rằng mỗi ngôn ngữ L thuộc NP đều thu
đƣợc P2 trong thời gian đa thức. Khi đó theo định nghĩa P2 sẽ thuộc NP-C.
Thật vậy vì P1 là NP-C nên có một phép thu đa thức L về P1. Giả sử thời
gian của phép thu này là P(n). Vì thế một chuỗi W ∈ L cã chiÒu dµi n ®-îc
biÕn ®æi thµnh mét chuçi x ∈ P1 có chiều dài tối đa là P(n). Ta cũng biết rằng
có một phép thu đa thức từ P1 về P2. Giả sử thời gian của phép thu này là
q(m). Thế thì phép thu này biến đổi chuỗi x ∈ P1 về một chuỗi y nào đó thuộc
P2 với thời gian tối đa là q(p(n)). Vì thế phép biến đổi W ∈ L về y ∈ P2 mất
thời gian tối đa là p(n) + q(p(n)). đây cũng là một đa thức. Nhƣ vậy, ta kết
luận rằng L có thể thu về P2 trong thời gian đa thức.
Định lý 1.2. Nếu có một bài toán nào đó là NP-C mà lại thuộc lớp P thì
ta có P = NP.
Chứng minh: Giả sử có bài toán Q ∈ NP-C và Q ∈ P. Thế thì mọi ngôn
ngữ L
trong NP đều thu đƣợc về Q trong thời gian đa thức. Nếu Q ∈ P thì L ∈
P. Nhƣ vậy NP ∈ P. Kết hợp với điều hiển nhiên là P ∈ NP ta đƣợc P = NP.
Nhận xét: Chúng ta vẫn tin tƣởng rằng nhiều bài toán thuộc NP nhƣng không
thuộc P nên chúng ta sẽ xem việc chứng minh một bài toán là NP-C có giá trị
ngang với việc chứng minh rằng nó không thể giải đƣợc trong thời gian đa
thức, và vì thế không có lời giải đúng nào bằng máy tính (và ta sẽ chỉ đi tìm
lời giải gần đúng).
1.2. Cách tiếp cận giải bài toán NP-C
1.2.1. Một số khái niệm
Nhƣ đã trình bầy ở phần trên việc tìm nghiệm của các bài toán NP-C với
kích cỡ đầu vào n tƣơng đối lớn là rất khó khăn, thƣờng là không khả thi vì độ
phức tạp có thể nói là hàm mũ. Đây là những bài toán nan giải hay còn gọi là
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-5-
bất trị. Vì thế thay cho việc tìm lời giải đúng (lời giải tối ƣu) ngƣời ta phải tìm
nghiệm gần đúng (lời giải gần tối ƣu) mà có thể chấp nhận đƣợc.
- Giải thuật xấp xỉ: Xét trƣờng hợp dữ kiện I của bài toán tối ƣu P. Gọi
F*(I) là giá trị của lời giải tối ƣu đối với I. Giải thuật G đƣợc gọi là giải thuật
xấp xỉ cho bài toán P nếu nó luôn tạo ra một lời giải khả thi (feasible solution)
mà giá trị 𝐹 (I) của lời giải này gần với F*(I) đối với mọi dữ liệu I của bài toán
P.
- Giải thuật xấp xỉ tuyệt đối: Giải thuật G đƣợc gọi là giải thuật xấp xỉ
tuyệt đối cho bài toán P ↔ với mọi trƣờng hợp I của P tồn tại hằng số K
|F*(I) - 𝐹 (I)| ≤ K
ở đây 𝐹 (I) là giá trị của lời giải do G tạo ra đối với dữ kiện I.
- Giải thuật f(n)-xấp xỉ: Giải thuật G đƣợc gọi là giải thuật f(n)-xấp xỉ
cho bài toán P ↔ với mọi dữ kiện I của bài toán P thì
|F ∗ I − 𝐹 (I)|
𝐹 (I)
≤𝑓 𝑛 ,
với n là kích thƣớc của I.
- Giải thuật 𝜀 - xấp xỉ là giải thuật f(n)-xấp xỉ nếu f(n) ≤ 𝜀.
1.2.2. Giới thiệu một số thuật toán xấp xỉ giải bài toán NP-C
a. Bài toán phủ đỉnh bé nhất (thuộc NP-C)
Input: Đồ thị vô hƣớng G = (V,E).
Output: Phủ đỉnh bé nhất.
Thuật toán gần tối ƣu: Procedure ApproxVertexCover
C := Ø {C là tập phủ đỉnh gần tối ƣu}
E := Tập các cạnh của G
While E ≠ Ø do
Chọn (u, v) là một cạnh bất kỳ
C := C U {u, v} {kết nạp 2 đỉnh u, v vào phủ đỉnh C}
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-6-
Loại bỏ khỏi E cạnh uv và mọi cạnh liên thuộc với u hoặc v
End do
Return(C)
b. Giải thuật tham lam giải các bài toán tối ưu hóa thuộc loại NP-C
Giải thuật tham lam là một heuristic. GrA (Greedy Algorithm) không
phải luôn luôn cho lời giải tối ƣu. Thƣờng nó chỉ cho lời giải gần tối ƣu. Khi
nó cho lời giải tối ƣu thì việc chứng minh tính đúng đắn của thuật toán cũng
không đơn giản.
Để mô tả chính xác GrA cần mô tả chính xác môi trƣờng trong đó các
bài toán tối ƣu đặt ra. Trong các bài toán tối ƣu trong ngữ cảnh GrA ngƣời ta
có:
- Tập (danh sách) các ứng viên, thí dụ, các nút, các cạnh trong đồ thị.
- Tập các ứng viên đã sử dụng.
- Một cách để kiểm tra liệu một tập các ứng viên đã cho có lời giải
(không nhất thiết là tối ƣu) hay không?
- Một hàm lựa chọn (selection function) để chọn các ứng viên chƣa đƣợc
sử dụng.
- Hàm mục tiêu gán giá trị cho các lời giải.
1.2.3. Các thuật toán gần đúng
a. Heuristic đối với bài toán phủ đỉnh
Bài toán: Cho đồ thị G = (V,E). Tìm tập đỉnh C nhỏ nhất phủ G theo
nghĩa nếu cạnh uv ∈ E ⇒ u ∈ C hoặc v ∈ C.
Thuật toán tham lam:
Input: Đồ thị G = (V,E).
Output: Phủ C của G gần với phủ nhỏ nhất.
begin
C := Ø;
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-7-
while E ≠ Ø do
Chọn trong V đỉnh có bậc cao nhất, loại nó ra khỏi G và bổ sung vào C.
end;
Vì mục đích của ta là phủ tất cả các cạnh của G bởi số ít đỉnh nhất nên
chiến lƣợc chọn trên mỗi bƣớc một đỉnh phủ đƣợc nhiều cạnh nhất là hoàn
toàn chấp nhận đƣợc. Tất nhiên vì bài toán là NP-C nên không hy vọng là
thuật giải này hiệu quả để đạt đƣợc tập phủ đỉnh bé nhất. Câu hỏi là tập đỉnh
tìm đƣợc gần với tập đỉnh tối ƣu đến mức nào? áp dụng giải thuật trên cho đồ
thị sau:
Đầu tiên chon một trong các đỉnh a1, a2 hoặc a3 có bậc bằng 5. Giả sử ta
chọn a1, a2 rồi a3. Cuối cùng là c1, c2, c3, c4 và c5. Nhƣ vậy phủ đỉnh gồm 8
đỉnh. Nhƣng phủ đỉnh tối ƣu chỉ gồm 5 đỉnh là {b1, b2, b3, b4, b5} nếu mở rộng
thí dụ này và xét đồ thị với n đỉnh loại a, n +2 đỉnh loại b và n +2 đỉnh loại c.
Theo giải thuật 1 ta tìm đƣợc phủ gồm 2n + 2 đỉnh, nhƣng phủ tối ƣu chỉ gồm
n + 2 đỉnh. Vì n không giới nội nên sai số có thể đạt gần tới 100%.
Phải chăng đây là phƣơng pháp xấu nhất của giải thuật tham, hay có thể
có sai số lớn hơn?
Xét đồ thị: Đầu tiên chọn a7 với deg(a7) = 5 lớn nhất. Sau khi loại a7 thì
a6 có bậc lớn nhất (bậc 4) rồi a5 (bậc 3),.. Trên mỗi bƣớc trong số các đỉnh có
bậc lớn nhất có một đỉnh loại a, sau đó đƣợc loại bỏ. Cuối cùng phủ đỉnh
đƣợc bổ sung các đỉnh loại c. Kết quả là ta đƣợc phủ đỉnh của G gồm 13 đỉnh,
trong khi phủ tối ƣu chỉ gồm 6 đỉnh {b1, b2, b3, b4, b5, b6}. Nhƣ vậy sai số
vƣợt quá 100%.
Để tổng quát hóa phản ví dụ trên đầu tiên ta cần hiểu cấu trúc của nó. Có
thể xem nó nhƣ 6 cạnh cibi (i = 1, 6), đƣợc bổ sung thêm các đỉnh loại a một
cách thích hợp.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-8-
Đầu tiên 6 cạnh loại b đƣợc phân thành 3 cặp và các đỉnh của mỗi cặp
đƣợc nối với một đỉnh loại a. Sau đó các đỉnh loại b đƣợc chia thành hai bộ ba
và tất cả các đỉnh của mỗi bộ ba nối với một đỉnh a mới. Cũng làm nhƣ vậy
với mỗi bộ bốn, bộ năm..
* Thuật toán
input và output nhƣ thuật toán 1.
begin
c:=Ø ;
while E ≠ Ø do
Chọn trong E cạnh bất kỳ (u, v), rồi loại bỏ các đỉnh u, v từ G và bổ sung
nó vào C
end;
Định nghĩa 1.2. Giả sử A là bài toán tối ƣu với hàm giá trị c là nguyên
dƣơng, A là thuật toán cho giá trị fA(I) đối với dữ kiện I, lời giải tối ƣu là 𝐹 (I).
Khi đó thuật toán A đƣợc gọi là thuật toán 𝜖-xấp xỉ đối với bài toán A nếu
∃ 𝜖 ≥ 0 sao cho
𝑐 𝑓𝐴 𝐼
− 𝑐(𝐹 I )
≤𝜖
𝑐𝐹 (I)
∀𝐼
Thí dụ: Thuật toán 2 là thuật toán 1-xấp xỉ, thuật toán 1 không phải là 𝜖 xấp xỉ ∀𝜖 > 0, vì sai số tƣơng đối của nó đối với các bài toán riêng biệt có thể
lớn hơn hằng số bất kỳ. Để mô tả trƣờng hợp xấu nhất của thuật toán đôi khi
ngƣời ta lấy 𝜖 = 𝜖(n). Thí dụ nếu n là số đỉnh trong bài toán phủ đỉnh ngƣời ta
chỉ ra rằng thuật toán 1 là lnn-xấp xỉ. Có nghĩa là với mọi đồ thị G với n đỉnh
thuật toán cho tập phủ C thỏa mãn
𝐶 − |𝐶 |
|𝐶 |
≤ ln 𝑛,
trong đó 𝐶 là phủ tối ƣu.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-9-
b. Bài toán TSP
Sử dụng các ý tƣởng của mục trƣớc vào bài toán này. Mục đích: xây
dựng thuật toán hiệu quả cho kết quả gần đúng.
Xét ma trận cỡ n x n các khoảng cách [dij ], dij > 0. Nhƣ thƣờng lệ ta giả
thiết dij = dji và dii = 0. Ta nói ma trận (dij) thỏa mãn bất đẳng thức tam giác
nếu
dij + djk ≥ dik
∀1≤i, j, k ≤ n.
Bất đẳng thức này thỏa mãn nếu dij là khoảng cách thông thƣờng giữa 2
điểm (xi, yi) và (xj , yj):
dij =
𝑥𝑖 − 𝑥𝑗
2
+ 𝑑𝑖 − 𝑑𝑗
2
Có thể có các ma trận (dij) khác thỏa mãn bất đằng thức tam giác.
Bài toán: Hãy tìm cách nhận số tiền S đã cho dùng ít tờ tiền nhất với
mệnh giá khác nhau.
c. Thuật toán tham giải bài toán chọn đồng tiền
input: Tổng số tiền S, tập các mệnh giá M = {m1,m2, ...,mn}.
+ Sắp xếp các mệnh giá theo thứ tự giảm dần. Giả sử đó là m1 > m2 > ...
> mn.
+ Nếu mệnh giá bé nhất mn > S thì bài toán không có lời giải. Thuật toán
kết thúc.
Nếu khác (tức là mn ≤ S) thì chọn các đồng tiền theo thứ tự mệnh giá
giảm cho đến khi đủ S hoặc không thể chọn thêm.
begin
k1 = [S/m1] (số đồng tiền mệnh giá m1).
b=0
for i = 2 to n
b = b + ki-1mi-1
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- 10 -
Si = S - b (số tiền còn lại sau khi đã chọn các đồng tiền mệnh giá
m1, ...,mi-1)
ki = [Si]/mi ( số đồng tiền mệnh giá mi)
end;
Thí dụ 1.1. S = 298, M = {50, 20, 10, 5, 2, 1}
Bƣớc Mệnh giá mi Số đồng tiền
1
2
3
4
5
6
50
20
10
5
2
1
Tổng giá trị đã có
Giá trị còn lại
250
290
290
295
297
298
48
8
8
3
1
0
Tổng giá trị đã có
30
30
40
Giá trị còn lại
10
10
0
5
2
0
1
1
1
Thuật toán cho lời giải tối ƣu
Thí dụ 1.2. S = 40, M = {30, 20, 5, 2}
Bƣớc
mi
1
30
2
20
3
5
Tổng cộng: 3 tờ tiền
Ki
1
0
2
Phƣơng án tối ƣu hơn: 2 tờ, mỗi tờ mệnh giá 20.
Kết luận: Nhƣ vậy thuật toán tham không phải khi nào cũng cho lời giải
tối ƣu.
Nhƣng khi tập dữ liệu lớn thì thuật toán nhanh chóng cho lời giải tối ƣu
hoặc gần tối ƣu.
d. Bài toán ba lô nguyên (0-1)
Giả sử ba lô có dung lƣợng là W. Có các vật b 1, ..., bn với dung lƣợng wi
và giá trị pi (profit). Xếp các vật vào ba lô sao cho đạt tổng giá trị lớn nhất
(giả thiết là các vật không thể chia nhỏ).
Ký hiệu xi là biến quyết định (loại 0-1):
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- 11 -
xi =
1𝑛ế
𝑢 𝑐ọ
𝑛 𝑣ậ
𝑡 𝑏𝑖
0 𝑛ế
𝑢 𝑘á𝑐
Khi đó bài toán đƣợc phát biểu nhƣ sau:
Tìm vector x = (x1, x2, ..., xn), xi 𝜖 {0, 1} sao cho
ràng buộc
𝑛
𝑖=1 𝑝𝑖 𝑥𝑖
𝑛
𝑖=1 𝑝𝑖 𝑥𝑖
→ 𝑚𝑎𝑥 với
≤ 𝑊.
e. Các phương pháp tham (GrM) đối với bài toán ba lô 0-1
GrM dựa trên việc đặt các vật vào ba lô từng cái một.
Các chiến lƣợc chọn vật đặt vào ba lô:
* Greedy-by-profit: Tại mỗi bƣớc chọn trong các vật còn lại vật có giá trị
lớn nhất (với điều kiện dung lƣợng của ba lô cho phép).
* Greedy-by-weight: Tại mỗi bƣớc chọn vật có trọng lƣợng bé nhất trong
các vật còn lại. Đặt càng nhiều vật vào ba lô càng tốt.
* Greedy-by-profit-density: Tại mỗi bƣớc chọn trong số các vật còn lại
vật có mật độ giá trị di = pi/wi lớn nhất.
Thí dụ 1.3. Cho các vật trong bảng và W = 100.
i
wi
pi
1
100
40
2
50
35
3
45
18
4
20
4
5
10
10
6
5
2
* Greedy-by-profit-density
di = pi/wi
0.4
0.7
0.4
0.2
1.0
0.4
Step 0: x1 = x2 = ... = x + 6 = 0
Bƣớc
Biến
1
2
3
4
x5 = 1
x2 = 1
x6 = 1
x4 = 1
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
𝒘𝒊 𝒙𝒊
10
60
65
85
𝒑𝒊 𝒙𝒊
10
45
47
51
http://www.lrc-tnu.edu.vn
- 12 -
* Greedy-by-profit
Start: x1 = x2 = ... = x + 6 = 0
𝒘𝒊 𝒙𝒊
Bƣớc
Biến
1
x1 = 1
𝒑𝒊 𝒙𝒊
100
40
* Greedy-by-weight
𝒘𝒊 𝒙𝒊
Bƣớc
Biến
1
2
3
4
x6 = 1
x5 = 1
x4 = 1
x3 = 1
𝒑𝒊 𝒙𝒊
5
15
35
80
2
12
16
34
Nhận xét 1. Greedy-by-profit-density tốt hơn theo profit hoặc theo
weight nhƣng còn xa mới tới giá trị tối ƣu khi W = 100 và profit = 55.
Bảng dƣới đây trình bày 4 lời giải:
i
wi
pi
di
G-profit
G-weight
G-density
Optimal
solution
1
2
3
4
5
6
100
50
45
20
10
5
40
35
18
4
10
2
0.4
0.7
0.4
0.2
1.0
0.4
1
0
0
0
0
0
100
40
0
0
1
1
1
1
80
34
0
1
0
1
1
1
85
51
0
1
1
0
0
1
100
55
Total weight
Total profit
Nhận xét 2. Bài toán ba lô 0-1 là bài toán NP-C, do đó có thể không có
lời giải tối ƣu.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- 13 -
1.2.4. Tô mầu đồ thị với bài toán 4 mầu
a. Giới thiệu
Lịch sử xuất hiện giả thuyết bốn màu còn nhiều điều chƣa rõ. Có ý kiến
cho rằng Mobious đã biết bài toán này từ năm 1852 khi Francis Guthrie, một
sinh viên trƣờng Tổng hợp London trình bày bài toán này cho Augustus De
Morgan, và ông này đã mô tả nó trong thƣ gửi cho Hamilton. (Lại có ý kiến
khác cho rằng bài toán này xuất hiện vào khoảng những năm 1850-1852 từ
một nhà buôn ngƣời Anh là Gazri khi tô bản đồ hành chính nƣớc Anh đã cố
gắng chứng minh rằng nó có thể tô bốn màu. Sau đó, năm 1952 ông ta đã viết
thƣ cho DeMorgan để thông báo về giả thuyết này). Năm 1878 Kelly, nhà
toán học nổi tiếng ngƣời Anh đã phát biểu trƣớc hội toán học London với
thông báo rằng ông đã suy nghĩ nhiều ngày về bài toán bốn màu nhƣng không
thể giải đƣợc.
Tính hấp dẫn của bài toán này nằm ở tính dễ hiểu trong cách phát biểu
bài toán : “Cần chứng minh rằng một đồ thị phẳng bất kỳ có thể tô bởi bốn
màu sao cho hai đỉnh kề nhau có hai màu khác nhau”. Để giả bài toán này, có
hai khuynh hƣớng :
1. Đối với một đồ thị phẳng bất kỳ, xây dựng thuật toán thực hiện việc tô
màu các đỉnh bởi bốn màu.
2. Chứng minh sự tồn tại của phép tô màu đó.
Tóm lại, bài toán bốn màu được phát biểu như sau:
Phát biểu bài toán bốn màu:
Cho một bản đồ trong đó có N nƣớc. Cần tô màu cho các nƣớc sao cho
hai nƣớc kề nhau (tức là có chung biên giới) đƣợc tô bởi hai màu khác nhau,
nhờ đó có thể phân biệt các vùng một cách dễ dàng.
Bài toán sẽ không còn tồn tại nếu nhƣ có số lƣợng màu lớn. Tuy nhiên,
sẽ thực sự khó khăn với ràng buộc rằng phải sử dụng số màu là nhỏ nhất.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -