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
THÔNG
PHÙNG DƢƠNG HOÀNG MỘT SỐ THUẬT TOÁN GIẢI BÀI TOÁN PHỦ
ĐỈNH
L
Thái Nguyên - 20
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 LỜI CAM ĐOAN
điều kiện để tôi học tập và hoàn thành tốt khóa học.
Mặc dù tôi đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả sự nhiệt
tình và năng lực của mình, tuy nhiên không thể tránh khỏi những thiếu sót, tôi
rất mong nhận được những đóng góp quí báu của quý thầy cô và các bạn.
Lời cảm ơn sau cùng tôi xin dành cho gia đình và những người bạn đã
hết lòng quan tâm và tạo điều kiện tốt nhất để tôi hoàn thành luận văn tốt
nghiệp này!
Tôi xin chân thành cảm ơn!
Thái Nguyên, tháng 6 năm 2014
Học viên thực hiện Phùng Dƣơng Hoàng
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
MỤC LỤC
Trang
Trang bìa phụ
Lời cam đoan i
Lời cảm ơn ii
Mục lục iii
Danh mục các hình v
LỜI NÓI ĐẦU 1
Chƣơng 1: CÁC PHƢƠNG PHÁP HEURISTIC GIẢI 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.1.1. Lớp bài toán P 3
1.1.2. Lớp bài toán NP 3
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/
v
DANH MỤC CÁC HÌNH
Trang
Hình 1.1: Mối quan hệ giữa lớp P và NP 4
Hình 1.2. Hình bài toán về tập độc lập 6
Hình 1.3: Mô hình mạng Hopfield 19
Hình 1.4: Lời giải tốt và xấu của bài toán sánh cặp có trọng 24
Hình 2.1: Thí dụ về phủ đỉnh 26
Hình 2.2: Thí dụ về bài toán phủ đỉnh theo phương pháp tham (n=7) 28
Hình 2.3: Thí dụ về bài toán phủ đỉnh theo phương pháp tham (n=13) 30
Hình 2.4: Thí dụ về bài toán phủ đỉnh theo Dharwadker (n=12) 34
Hình 3.1: Chương trình tìm phủ đỉnh của một đồ thị n=12 45
Hình 3.2: Phủ đỉnh của đồ thị n=4 47
Hình 3.3: Phủ đỉnh của đồ thị n=6 49
Hình 3.4: Phủ đỉnh của đồ thị n=6 50
Hình 3.5: Phủ đỉnh của đồ thị n=7 51
Hình 3.6: Phủ đỉnh của đồ thị n=8 53
Hình 3.7: Phủ đỉnh của đồ thị n=8 54
Hình 3.8: Phủ đỉnh của đồ thị n=10 56
Hình 3.9: Phủ đỉnh của đồ thị n=11 57
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/
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 Trường Đại học
Công nghệ Thông tin và Truyền thông - Đại học 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!
3
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/
Chƣơng 1
CÁC PHƢƠNG PHÁP HEURISTIC GIẢI CÁC BÀI TOÁN NP-C
1.1. Giới thiệu chung về bài toán NP-C
1.1.1. Lớp bài toán P
Định nghĩa 1.1: Ta gọi lớp P là lớp những bài toán quyết định giải
được bằng máy tính Turing đơn định trong thời gian đa thức.
Một ngôn ngữ L thuộc lớp P nếu có một hàm đa thức T(n) sao cho
L=L(M) với một máy Turing đơn định nào đó có độ phức tạp thời gian T(n).
Như vậy, lớp P gần như tương ứng với lớp các bài toán quyết định giải
được trong thời gian đa thức, về mặt lý thuyết, có thể xem là lớp các bài toán dễ.
1.1.2. Lớp bài toán NP
Ta gọi lớp NP là lớp các bài toán quyết định có thể giải được bằng
máy tính Turing không đơn định trong khoảng thời gian đa thức.
Một cách không hình thức, chúng ta nói một ngôn ngữ L thuộc lớp NP
nếu tồn tại một máy tính Turing không đơn định M và một độ phức tạp thời
gian T(n) sao cho L = L(M) và khi M được cho một nguyên liệu có độ dài n
thì nó sẽ kiểm nhận sau không quá T(n) bước chuyển.
Để nói về mối quan hệ giữa lớp P và lớp NP ta thấy do máy tính Turing
đơn định là trường hợp đặc biệt của máy tính Turing không đơn định nên các
bài toán thuộc lớp P sẽ thuộc lớp NP.
Tuy P NP là rất hiển nhiên song ta vẫn chưa biết P = NP hay không,
thời gian đa thức từ P1 về P2 thì P2 cũng là NP-C.
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
5
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/
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. Một số bài toán NP-C trong lý thuyết đồ thị, trong quy hoạch nguyên
Các lớp bài toán NP-Complete là rất rộng. Hầu hết các bài toán nổi
tiếng mà
chúng ta đã biết như bài toán người bán hàng, bài toán balô, các
bài toán tổ hợp,
phân tích ra thừa số… đều là các bài toán khó. Sau đây là
Bài toán được phát biểu như sau:
- Cho đồ thị G = (V, E) và k N
*
thoả mãn k ≤ |V|
- Hỏi tồn tại hay không một tập con V’ của V sao cho |V'| k mà mọi
cặp
đỉnh trong V’ đều được nối bởi 1 cạnh trong E.
1.2.4. Bài toán về tô màu đồ thị
Phép tô màu đồ thị bằng gán màu cho các đỉnh sao cho hai đỉnh liền kề
được tô bởi hai màu khác nhau.
Sắc số của đồ thị: là số màu ít nhất cần dùng để tô màu đồ thị.
1.2.5. Bài toán đồ thị con đẳng cấu (Subgraph Isomorphism)
- Cho hai đồ thị: G
1
= (V
1
, E
1
) và G
2
= (V
2
, E
2
).
- Hỏi G
1
có chứa đồ thị con G’ = (V’, E’) đẳng cấu với đồ thị G
2
, tức
n
} với khoảng cách d(C
i
, C
j
)
Z
+
và một số nguyên dương k
- Hỏi có tồn tại một hoán vị π trên {1, 2, …, n} sao cho:
n
−1
∑
d(C
π(i)
, C
π(i+1)
) + d(C
π(m)
, C
π(1)
) ≤ k hay không?
i
=1
1.2.8. Bài toán TSP
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 [d
ij
], d
ij
ij
=
22
( ) ( )
i j i j
x x d d
Có thể có các ma trận (d
ij
) khác thỏa mãn bất đằng thức tam giác.
1.2.9. 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
, , b
n
với dung lượng
w
i
và giá trị p
i
(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ỏ).
8
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/
Ký hiệu x
i
là biến quyết định (loại 0-1):
x
i
1.3. Khái niệm chung về các phƣơng pháp Heuristic
- Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách
giải bài toán với các đặc tính sau:
+ Thườ ợc lời giải tốt (nhưng không chắc là lời giải tốt nhất).
+ Thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật
tối ưu, vì vậy chi phí thấp hơn.
+ Thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành
động của con người.
- Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó
người ta thường dựa vào một số nguyên lý cơ bản như sau:
+ Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó,
khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm
kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để
nhanh chóng tìm ra mục tiêu.
+ Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi
toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục
bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.
+ Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự
hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt.
9
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/
+ Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người
ta thường dùng các hàm Heuristic. Đó là các hàm đánh giá thô, giá trị của
hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá
trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước
của thuật giải.
1.4. Một số phƣơng pháp Heuristic giải các bài toán NP-C
1.4.1. Thuật toán tham lam
1.4.1.1. Giới thiệu chung
giải tối ưu cho bài toán nhỏ tương ứng. Lời giải của bài toán được bổ sung
dần từng bước từ lời giải của các bài toán con. Các lời giải tìm được bằng
phương pháp tham lam thường chỉ là chấp nhận theo điều kiện nào đó, chưa
chắc là tối ưu.
+ Cho trước một tập A gồm n đối tượng, ta cần phải chọn một tập con
S của A.
Với một tập con S được chọn ra thoả mãn các yêu cầu của bài toán,
ta gọi là một nghiệm chấp nhận được. Một hàm mục tiêu gắn mỗi nghiệm
chấp nhận được với
một giá trị. Nghiệm tối ưu là nghiệm chấp nhận được mà
tại đó hàm mục tiêu đạt giá trị nhỏ nhất (lớn nhất).
+ Đặc trưng tham lam của phương pháp thể hiện bởi: trong mỗi bước
việc xử lý sẽ tuân theo một sự lựa chọn trước, không kể đến tình trạng không
tốt có thể xảy ra khi thực hiện lựa chọn lúc đầu.
1.4.1.2. Thuật toán cho phương pháp tham lamChọn S từ tập A.
Tính chất tham lam của thuật toán định hướng bởi hàm Chọn.
+ Khởi động S = Ø
+ Trong khi A ≠ Ø:
- Chọn phần tử tốt nhất của A gán vào x : x = Chọn (A);
11
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/
- Cập nhật các đối tượng để chọn: A = A - { x };
- Nếu S U { x } thoả mãn yêu cầu bài toán thì
Cập nhật lời giải: S = S U { x };
Thủ tục thuật toán tham lam có thể cài đặt như sau:
Input: A [ 1 n ]
thị có
hướng có trọng số.
Thuật toán tham lam cho bài toán là chọn thành phố có chi phí nhỏ nhất
12
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/
tính từ thành phố hiện thời đến các thành phố chưa qua.
- Thuật toán
Input: C = ( C
i j
)
Output: TOUR // Hành trình tối ưu,
COST; // Chi phí tương ứng
Mô tả:
TOUR := 0; COST := 0; v:= u; // Khởi tạo
mọi k := 1 → n : // Thăm tất cả các thành phố
// Chọn cạnh kế
+ Chọn < v, w > là đoạn nối 2 thành phố có chi phí nhỏ nhất tính từ
thành phố v đến các thành phố chưa qua.
+ TOUR := TOUR + < v, w >; // Cập nhật lời giải
+ COST := COST + C
v w
; // Cập nhật chi phí
// chuyến đi hoàn thành
TOUR := TOUR + < v, u >;
COST := COST + C
v u
;
- Độ phức tạp của thuật toán
Thao tác chọn đỉnh thích hợp trong n đỉnh được tổ chức bằng một vòng
{
mini = a [ v ] [ k ];
w = k;
}
v = w;
i + +;
TOUR [ i ] = v;
daxet [ v ] = 1;
COST + = mini;
}
COST + = a [ v ] [ Ddau ];
14
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/
return COST;
}
1.4.1.4. Đánh giá
Bài toán được giải quyết bằng thuật toán tham lam (thường là các bài
toán tối ưu) nếu như nó có hai đặc điểm sau:
- Tính lựa chọn tham lam (greedy choice property): Một nghiệm tối ưu
có thể nhận được bằng cách thực hiện các lựa chọn có vẻ như tốt nhất tại mỗi
thời điểm mà không cần quan tâm tới các gợi ý của nó đối với các nghiệm của
các bài toán con. Hay nói một cách khác là nghiệm tối ưu của bài toán có thể
nhận được bằng cách thực hiện các lựa chọn tối ưu cục bộ.
- Cấu trúc con tối ưu (optimal substructure): Một nghiệm tối ưu có thể
nhận được bằng cách gia tăng các nghiệm thành phần đã được xây
dựng
với một nghiệm tối ưu của bài toán con còn lại. Có nghĩa là một nghiệm tối
ưu sẽ chứa các nghiệm tối ưu đối với các bài toán con kích thước nhỏ hơn.
tế bào thần kinh được gọi là các
nơ-ron. Mỗi nơ-ron gồm có ba phần: Thân nơ-ron với nhân ở bên trong
(soma), một đầu thần kinh ra (axon) và một hệ thống hình cây thần kinh
(dendrite). Có nhiều loại nơ-ron khác nhau về kích thước và khả năng thu
phát tín hiệu. Tuy nhiên, chúng có cấu trúc và nguyên lý hoạt động chung.
Hoạt động của nơ-ron sinh học có thể mô tả tóm tắt như sau: Mỗi nơ-
ron nhận tín hiệu vào từ các tế bào thần kinh khác. Chúng tích hợp các tín
hiệu vào, khi tổng tín hiệu vượt quá một ngưỡng nào đó chúng tạo tín hiệu ra
và gửi tín hiệu này tới các nơ-ron khác thông qua dây thần kinh. Các nơ-ron
liên kết với nhau thành mạng. Mức độ bền vững của các liên kết này xác định
một hệ số gọi là trọng số liên kết.
b. Nơ-ron nhân tạo
+ Trọng số và tổng tín hiệu đầu vào:
16
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/
Mô phỏng nơ-ron sinh học, ta có nơ-ron nhân tạo. Mỗi nơ-ron có rất
nhiều dây thần kinh vào, nghĩa là mỗi nơ-ron có thể tiếp nhận đồng thời nhiều
tín hiệu.
+ Hàm kích hoạt:
Hàm biến đổi tín hiệu đầu vào net cho tín hiệu đầu ra out được gọi là hàm
kích hoạt. Hàm này có đặc điểm là không âm và bị chặn. Có nhiều dạng hàm
kích hoạt, người ta thường sử dụng một hàm kích hoạt chung cho toàn mạng.
Một số hàm kích hoạt thường được sử dụng:
(i) Hàm McCuloch-Pitts:
net
net
netfout
nÕu
nÕu
Xét một cách tổng quát, mạng nơ-ron là một cấu trúc xử lý song song
thông tin phân tán mang các đặc tính nổi bật sau:
- Là mô hình toán học dựa trên bản chất của nơ-ron.
- Bao gồm một số lượng rất lớn các nơ-ron liên kết với nhau.
- Mạng nơ-ron có khả năng học, khái quát hoá tập dữ liệu học thông
qua việc gán và hiệu chỉnh các trọng số liên kết.
- Tổ chức theo kiểu tập hợp mang lại cho mạng nơ-ron khả năng tính
toán rất lớn, trong đó không có nơ-ron nào mang thông tin riêng biệt [2].
1.4.2.3. Phạm vi ứng dụng của mạng nơ-ron
a. Những bài toán thích hợp
Mạng nơ-ron được coi như là hộp đen biến đổi véc-tơ đầu vào m biến
thành véc-tơ đầu ra n biến. Tín hiệu ra có thể là các tham số thực, (tốt nhất
nằm trong khoảng [0,1], hoặc [-1,1]), số nhị phân 0,1, hay số lưỡng cực -1;+1.
Số biến của véc-tơ vào ra không bị hạn chế xong sẽ ảnh hưởng tới thời gian
tính và tải nguyên liệu của máy tính. Nói chung, các lớp bài toán áp dụng cho
nơ-ron có thể được phân chia thành bốn loại:
- Phân lớp (classification).
- Mô hình hoá (modeling).
- Biến đổi, thực hiện ánh xạ từ một không gian đa biến vào không gian
đa biến khác tương ứng (transformation and mapping).
- Liên kết và kỹ thuật dịch chuyển cửa sổ (association and moving
window).
b. Các lĩnh vực ứng dụng mạng nơ-ron
Khó có thể thống kê đầy đủ các ứng dụng của mạng nơ-ron. Tuy nhiên,
có thể nêu một số ứng dụng như sau:
18
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/
- Xử lý ảnh.
- Nhận dạng mẫu.
Hopfield được tìm thấy rất nhiều ứng dụng, đặc biệt trong bộ nhớ liên kết và
trong các bài toán tối ưu.
Giả sử mạng được xây dựng dưới dạng mạng một lớp, mỗi nơ-ron được
truyền ngược lại làm tín hiệu vào cho các nơ-ron khác nhưng bản thân các nơ-
ron không tự liên kết với chính nó. Khi đó mô hình mạng Hopfield được biểu
diễn như hình 1.3.
Tín hiệu ra của nơ-ron thứ j nào đó được truyền ngược lại làm tín hiệu
vào cho các nơ-ron khác trong mạng một cách đầy đủ thông qua các trọng số
tương ứng. Hình 1.3. Mô hình mạng Hopfield
Ký hiệu W
ij
là liên kết giữa hai nơ ron i và j (
jiij
ww
), V
i
là đầu ra
của nơron i. Ta coi véc tơ (V
1
, V
2
, V
n
) là trạng thái của mạng. Tại mỗi thời
1
X
1
X
2
Y
1
Y
2
Y
M .
.
.
Đầu vào Đầu ra
Copyright: Tài liệu đại học ©