..

ĐẠI HỌC THÁI NGUN

THƠNG

PHÙNG DƢƠNG HỒNG

MỘT SỐ THUẬT TỐN GIẢI BÀI TỐN PHỦ
ĐỈNH

L

Thái Ngun - 20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

i

LỜI CAM ĐOAN
Tôi xin cam đoan rằng, đây là công trình nghiên cứu của tơi trong đó có
sự giúp đỡ tận tình của thầy giáo hướng dẫn và các thầy cô tại Viện CNTT,
các thầy, cô giáo Trường Đại học Công nghệ Thông tin và Truyền thông, sự
hỗ trợ của các đồng nghi

. Các nội dung nghiên cứu và kết quả trong

đề tài này là hoàn toàn trung thực.
Trong luận văn, tơi có tham khảo đến một số tài liệu của một số tác giả
đã được liệt kê tại phần Tài liệu tham khảo ở cuối luận văn.

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

Phùng Dƣơng Hồng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

ii

LỜI CẢM ƠN
Để hồn thành chương trình cao học và viết luận văn này, tôi đã nhận
được sự hướng dẫn, giúp đỡ và góp ý nhiệt tình của q thầy cô trường Đại
học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên.
Trước hết, tôi xin chân thành cảm ơn đến quý thầy cô trường Đại học
Công nghệ thông tin và truyền thông - Đại học Thái Nguyên, các thầy cô
Viện CNTT, đặc biệt là những thầy cô đã tận tình dạy bảo cho tơi trong suốt
thời gian học tập tại trường.
Tôi xin gửi lời biết ơn sâu sắc đến GS.TS Đặng Quang Á đã dành rất
nhiều thời gian và tâm huyết hướng dẫn nghiên cứu và giúp tơi hồn thành
luận văn tốt nghiệp.
Nhân đây, tơi xin chân thành cảm ơn Ban giám hiệu trường Đại học
Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên đã tạo rất nhiều
điều kiện để tôi học tập và hồ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 q báu của q 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 hồ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 Hồng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

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
1.1.3. Lớp bài toán NP-đầy đủ (NP-Complete) .......................................... 4
1.2. Một số bài toán NP-C trong lý thuyết đồ thị, trong quy hoạch nguyên.. 5
1.3. Khái niệm chung về các phương pháp Heuristic .................................... 8
1.4. Một số phương pháp Heuristic giải các bài toán NP-C .......................... 9
1.4.1. Thuật toán tham lam ......................................................................... 9

1.4.1.1. Giới thiệu chung ............................................................................ 9
1.4.1.2. Thuật toán cho phương pháp tham lam .................................... 10
1.4.1.3. Ví dụ áp dụng ............................................................................... 11
1.4.1.4. Đánh giá ..................................................................................... 14
1.4.2. Giới thiệu về mạng nơ-ron .............................................................. 14
1.4.2.1. Lịch sử phát triển ......................................................................... 14
1.4.2.2. Mơ hình mạng nơ-ron nhân tạo ................................................... 15
1.4.2.3. Phạm vi ứng dụng của mạng nơ-ron ........................................... 17
1.4.2.4. Mạng nơ-ron Hopfield ................................................................. 18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

iv

Chƣơng 2: BÀI TOÁN PHỦ ĐỈNH VÀ MỘT SỐ THUẬT TOÁN GIẢI
BÀI TOÁN PHỦ ĐỈNH ................................................................................ 26
2.1. Giới thiệu bài toán phủ đỉnh ................................................................. 26
2.2. Một số thuật toán giải bài toán phủ đỉnh .............................................. 27
2.2.1. Thuật toán tham .............................................................................. 27
2.2.2. Thuật tốn mới của Dharwadker .................................................... 32
Chƣơng 3: MƠ PHỎNG SỐ......................................................................... 39
3.1. Lựa chọn phương pháp sử dụng............................................................ 39
3.2. Xây dựng chương trình ......................................................................... 39
3.3. Phân tích và đánh giá kết quả ............................................................... 46
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


/>

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 tố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 tố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 tốn phủ đỉnh theo phương pháp tham (n=7) ........... 28
Hình 2.3: Thí dụ về bài tốn phủ đỉnh theo phương pháp tham (n=13) ......... 30
Hình 2.4: Thí dụ về bài tố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

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

1


LỜI NĨI ĐẦU
Trong thực tế có rất nhiều bài tố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 tốn đó, trong đó có nhiều bài tốn của lý thuyết đồ thị như: bài
toán phủ đỉnh, bài toán tập độc lập, bài toán tơ mầu đồ thị, bài tốn người bán
hàng rong, bài tốn phẳng hóa đồ thị,... nhiều bài tốn quy hoạch ngun như:
bài tốn ba lơ, bài tốn đóng thùng,.. Vì các bài tốn loại NP-C có độ phức tạp
hàm mũ nên khi dữ liệu đầu vào lớn nên nói chung người ta không thể thu
được lời giải đúng của bài tốn và buộc phải tìm lời giải gần đúng. Có nhiều
thuật tốn heuristic với thời gian đa thức để tìm nghiệm xấp xỉ của các bài
toán NP-C. Những năm gần đây trên thế giới đã đưa ra một số phương pháp
và thuật giải 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ế, giải quyết một số bài
toán 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 GS.TS Đặng
Quang Á em đã mạnh dạn nghiên cứu đề tài: "Một số thuật toán giải bài
toán phủ đỉnh". 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 chung về bài toán NP-C; một số bài toán NP-C
trong lý thuyết đồ thị, trong quy hoạch nguyên; giới thiệu một số phương
pháp Heuristic giải các bài toán NP-C.
Chương hai giới thiệu bài toán phủ đỉnh và một số phương pháp giải
bài toán phủ đỉnh.
Chương ba ứng dụng.
Qua luận văn này em xin chân thành cảm ơn: GS.TS Đặng Quang Á Viện Công nghệ Thông tin đã tận tình giúp đỡ, động viên, định hướng,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

2


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!

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

3

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 tố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 tố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 tố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 ngun liệu có độ dài n

thì nó sẽ kiểm nhận sau khơng q 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 tố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,

nhưng hầu hết các nhà nghiên cứu đều tin rằng P

NP. Từ đó ta có mơ hình

mơ phỏng sau:
NP
P

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

4

Hình 1.1. Mối quan hệ giữa lớp P và NP
1.1.3. Lớp bài tốn NP-đầy đủ (NP-Complete)
Định nghĩa 1.2: 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 tố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 tốn đã biết là NP-C về bài tố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 tốn đích là NP-C.
Định lý 1.1: Nếu bài tố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.
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

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

P2


5

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 tố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 tố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. Như vậy NP

P. Kết hợp với điều hiển nhiên là P

P thì L

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 tố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 tố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 tốn balơ, các
bài tốn tổ hợp, phân tích ra thừa số… đều là các bài tốn khó. Sau đây là
một số bài tốn khó thuộc lớp NP-Complete trong lý thuyết đồ thị, trong quy
hoạch nguyên.
1.2.1. Bài toán về tập độc lập (Independent set)
Cho G là một đồ thị vơ hướng. Ta nói tập con I của các đỉnh thuộc G là
một tập độc lập nếu khơng có hai đỉnh nào của I được nối bởi một cạnh của G
(tức là I là tập các đỉnh mà không có 2 đỉnh nào liền kề nhau). Một tập độc
lập là cực đại nếu nó có nhiều nút nhất trong số các tập độc lập.
Thí dụ: Đồ thị trong hình 1.2 sau có tập độc lập gồm các đỉnh {1, 4}.
Đó cũng là tập độc lập cực đại.

1

3 Nguyên
Số hóa bởi Trung tâm Học liệu – Đại học Thái

2

4
/>

6

Hình 1.2. Hình bài tốn về tập độc lập
1.2.2. Bài toán phủ đỉnh (Vertex-Cover)
Bài toán được phát biểu như sau:
N* sao cho k ≤ |V|


- Cho đồ thị G = (V, E) và số k

- Hỏi tồn tại hay không một tập con V’ của V sao cho |V’| < k và mỗi
cạnh {u, e}

E thì một trong 2 đỉnh u hoặc e (hoặc cả đỉnh u và e ) phải

thuộc V’.
1.2.3. Bài toán đồ thị con đủ (Clique Problem)
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ị: G1 = (V1, E1) và G2 = (V2, E2).
- Hỏi G1 có chứa đồ thị con G’ = (V’, E’) đẳng cấu với đồ thị G2, tức
tồn tại tập con V’
V2 → V’ sao cho

V, E’
(u, v)

E thỏa |V’| = |V2|, |E’| = |E2| và một song ánh f :

E2 khi và chỉ khi {f(u), f(v)} E’.

1.2.6. Bài tốn chu trình Hamilton (Hamilton Cycle)
Chu trình Hamilton là chu trình sơ cấp đi qua tất cả các đỉnh của đồ thị.
Bài toán được phát biểu như sau:
- Cho đồ thị G = (V, E) có chu trình Hamilton H.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

7

- Tìm trong đồ thị G một chu trình Hamilton đúng bằng chu trình H đã cho.
1.2.7. Bài tốn người bán hàng (Traveling Salesman)
Cho đồ thị G và một số k nguyên, mỗi cạnh e của G có một trọng số
nguyên C(e). Vấn đề đặt ra là có tồn tại một chu trình đi qua tất cả các đỉnh
của G (mỗi đỉnh đúng một lần) mà tổng trọng số các cạnh đã đi qua không
vượt quá k?
Ta phát biểu lại bài toán như sau:
- Cho tập n thành phố C = {C1, C2, …, Cn} với khoảng cách d(Ci, Cj)
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 tốn TSP
Mục đích: xây dựng thuật tố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 =

( xi

x j )2

(di

d j )2

Có thể có các ma trận (dij) khác thỏa mãn bất đằng thức tam giác.
1.2.9. Bài tốn ba lơ ngun (0-1)
Giả sử ba lơ có dung lượng là W. Có các vật b1, ..., 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ỏ).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

8

Ký hiệu xi là biến quyết định (loại 0-1):

xi =

1 nÕu chän vËt bi
0 nÕukh¸c

Khi đó bài tốn được phát biểu như sau:
Tìm vector x = (x1, x2, ..., xn), xi
ràng buộc

{0, 1} sao cho

n
i 1

pi xi

max với

n

wi xi

W

i 1

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 tốn. Nó thể hiện cách
giải bài tố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 tố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 tốn để
nhanh chóng tìm ra mục tiêu.
+ Ngun 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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

9

+ 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
Định nghĩa 1.3: Giải thuật tham lam là một thuật toán giải quyết một
bài tốn theo kiểu metaheuristic để tìm kiếm lựa chọn tối ưu ở mỗi bước đi
với hy vọng tìm được tối ưu tồn cục.
Giải thuật tham lam có 5 thành phần:
a) Một tập hợp các ứng viên để từ đó tạo ra lời giải;
b) Một hàm lựa chọn để lựa chọn ứng viên tốt nhất để bổ sung vào lời giải;
c) Một hàm khả thi dùng để quyết định một ứng viên có thể là một lời giải;
d) Một hàm mục tiêu để ấn định giá trị lời giải hoặc một lời giải chưa
hoàn chỉnh;
e) Một hàm đánh giá để chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh.
- Hai thành phần quyết định nhất tới quyết định tham lam:
+ Tính chất lựa chọn tham lam: Chúng ta có thể lựa chọn giải pháp nào
được cho là tốt nhất ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh
từ việc thực hiện lựa chọn vừa rồi. Lựa chọn của thuật toán tham lam có thể
phụ thuộc vào các lựa chọn trước đó.
Thuật tốn tiến triển theo kiểu thực hiện các chọn lựa theo một vịng
lặp, cùng lúc đó thu nhỏ bài tốn đã cho về một bài toán con nhỏ hơn. Giải
thuật tham lam lựa chọn sớm và thay đổi đường đi thuật tốn theo lựa chọn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

10

đó, và khơng bao giờ xét lại các lựa chọn cũ. Đối với một số bài tốn, đây có
thể là một thuật tốn khơng chính xác.
+ Cấu trúc con tối ưu: Một bài tốn được gọi là "có cấu trúc tối ưu",
nếu một lời giải tối ưu của bài toán con chứa lời giải tối ưu của bài toán

lớn hơn.
- Ý tưởng của phương pháp tham lam:
+ Phương pháp tham lam là kỹ thuật thiết kế thường được dùng để giải
các bài toán tối ưu. Phương pháp được tiến hành theo nhiều bước. Tại mỗi
bước, theo một lựa chọn nào đó (xác định bằng một hàm chọn), sẽ tìm một lời
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 lam
Chọ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);
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

11

- Cập nhật các đối tượng để chọn: A = A - { x };

- Nếu S U { x } thoả mãn u cầu bài tốn thì
Cập nhật lời giải: S = S U { x };
Thủ tục thuật tốn tham lam có thể cài đặt như sau:
Input: A [ 1.. n ]
Output: S là lời giải;
Greedy ( A, n ) ≡
S = Ø;
While ( A ≠ Ø )
{ x = Chọn (A);
A=A-{x}
If ( S U { x } chấp nhận được )
S = S U { x };
}
return S;
1.4.1.3. Ví dụ áp dụng
- Bài tốn:
Một người du lịch muốn tham quan n thành phố T1, …, Tn. Xuất phát
từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn
lại, mỗi thành phố đi qua đúng một lần rồi quay trở lại thành phố đã xuất phát.
Gọi C ij là chi phí đi từ thành phố Ti đến Tj . Hãy tìm một hành trình
thoả u cầu bài tốn sao cho tổng chi phí là nhỏ nhất.
- Ý tưởng:
Đây là bài tốn tìm chu trình có trọng số nhỏ nhất trong một đơn đồ
thị có hướng có trọng số.
Thuật tốn tham lam cho bài tốn là chọn thành phố có chi phí nhỏ nhất
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

12


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 = ( Ci 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 + Cv 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 tốn
Thao tác chọn đỉnh thích hợp trong n đỉnh được tổ chức bằng một vòng
lặp để duyệt. Nên chi phí cho thuật tốn xác định bởi 2 vịng lặp lồng nhau,
nên T(n) = V(n2).
- Cài đặt:
Int GTS ( mat a, int n, int TOUR [ max ], int Ddau )
{
int

v,

// Dinh dang xet


k,

// Duyet qua n dinh de chon

w,

// Dinh duoc chon trong moi buoc

int

mini; // Chon min cac canh ( cung ) trong moi buoc

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

13

int COST;

// Trong so nho nhat cua chu trinh

int daxet [ max ]; // Danh dau cac dinh da duoc su dung
for ( k = 1; k < = n; k ++ )
daxet [ k ] = 0;

// Chua dinh nao duoc xet

COST = 0; // Luc dau, gia tri COST = = 0
int i; // Bien dem, dem tim du n dinh thi dung

v = Ddau;

// hon dinh xuat phat la 1

i=1
TOUR [ i ] = v;

// Dua v vao chu trinh

daxet [ v ] = 1;

// Dinh v da duoc xet

while ( i < n )
{
mini = VC;
for ( k = 1; k < = n; k ++ )
if (! daxet [ k ] )
if ( mini > a [ v ] [ k ] )
{
mini = a [ v ] [ k ];
w = k;
}
v = w;
i + +;
TOUR [ i ] = v;
daxet [ v ] = 1;
COST + = mini;
}
COST + = a [ v ] [ Ddau ];

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

14

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 tốn con. Hay nói một cách khác là nghiệm tối ưu của bài tố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 tố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 tốn con kích thước nhỏ hơn.
1.4.2. Giới thiệu về mạng nơ-ron
1.4.2.1. Lịch sử phát triển
Quá trình nghiên cứu và phát triển mạng nơ-ron nhân tạo có thể chia
thành bốn giai đoạn như sau:
+ Giai đoạn một: Có thể tính từ nghiên cứu của William (1890) về tâm
lý học với sự liên kết các nơ-ron thần kinh. Năm 1940, MeCulloch và Pitts đã
cho biết: nơ-ron có thể được mơ hình hố như thiết bị ngưỡng (giới hạn) để
thực hiện các phép tính logic và mơ hình mạng nơ-ron của Mc Culloch-Pitts
cùng với giải thuật huấn luyện mạng của Hebb ra đời năm 1943.
+ Giai đoạn hai: Vào khoảng gần những năm 1960, một số mơ hình nơron hồn thiện hơn đã được đưa ra như: mơ hình Perceptron của Rosenblatt

(1958), Adaline của Widrow (1962).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

15

+ Giai đoạn ba: Có thể tính vào khoảng đầu thập niên 80. Những đóng
góp lớn cho mạng nơ-ron trong giai đoạn này phải kể đến Grossberg,
Kohonen, Rumelhart và Hopfield. Trong đó đóng góp lớn của Hopfield gồm
hai mạng phản hồi: mạng rời rạc năm 1982 và mạng liên tục năm 1984. Đặc
biệt, ông đã dự kiến nhiều khả năng tính tốn lớn của mạng mà một nơ-ron
khơng có khả năng đó.
+ Giai đoạn bốn: Tính từ năm 1987 đến nay, rất nhiều cơng trình được
nghiên cứu để ứng dụng mạng nơ-ron vào các lĩnh vực, ví dụ như: kỹ thuật
tính, tối ưu, sinh học, y học, thống kê, giao thơng, hố học… Cho đến nay,
mạng nơ-ron đã tìm được và khẳng định được vị trí của mình trong rất nhiều
ứng dụng khác nhau.
1.4.2.2. Mơ hình mạng nơ-ron nhân tạo
a. Nơ-ron sinh học
Hệ thần kinh ở người có khoảng 1010 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:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

16

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 tồn mạng.
Một số hàm kích hoạt thường được sử dụng:
(i) Hàm McCuloch-Pitts:
out f net

1 nÕu net
0 nÕu net

(1.1)

ở đây là ngưỡng.
(ii) Hàm McCuloch-Pitts trễ:
out f net

1 nÕu net UTP

0 nÕu net LTP
f net nÕu kh¸c

(1.2)

ở đây UTP>LTP. Trong đó:
UTP là ngưỡng trên (Upper Trip Point).
LTP là ngưỡng dưới (Lower Trip Point).
c. Mạng nơ-ron
Mạng nơ-ron nhân tạo (Artificial Neural Network) là một cấu trúc
mạng được hình thành nên bởi một số lượng các nơ-ron nhân tạo liên kết với
nhau. Mỗi nơ-ron có các đặc tính đầu vào, đầu ra và thực hiện một chức năng
tính tốn cục bộ.
Với việc giả lập các hệ thống sinh học, các cấu trúc tính tốn, mạng nơron có thể giải quyết được các lớp bài tốn nhất định, như: Bài toán xếp loại,
bài toán lập lịch, bài tốn tìm kiếm, bài tốn nhận dạng mẫu... Các bài tốn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

17

phức tạp cao, không xác định. Tuy nhiên, sự liên kết giữa một bài toán bất kỳ
trong thực tế với một giải pháp mạng nơ-ron lại là một việc không dễ dàng.
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 tố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 qt hố 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

tố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 tố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 tố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 hố (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:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

18

- Xử lý ảnh.
- Nhận dạng mẫu.
- Y học.
- Các hệ thống quân sự.
- Vấn đề lập kế hoạch, điều khiển và tìm kiếm.
- Các hệ thống năng lượng.

- Dự đốn.
- Giải các bài tốn tối ưu: Vấn đề chính là tìm những thuật tốn huấn
luyện mạng để góp phần tìm nghiệm cho nhiều lớp bài tốn tối ưu tồn cục.
c. Ưu và nhược điểm của mạng nơ-ron
- Ưu điểm:
+ Xử lý song song.
+ Thiết kế hệ thống thích nghi.
+ Khơng địi hỏi các đặc trưng mở rộng của bài tốn (chủ yếu dựa trên
tập học).
- Nhược điểm:
+ Khơng có các quy tắc và các hướng dẫn thiết kế một cách rõ ràng đối
với một ứng dụng nhất định.
+ Không có cách tổng quát để đánh giá hoạt động bên trong mạng.
+ Việc học đối với mạng có thể khó (hoặc khơng thể) thực hiện.
+ Khó có thể dự đốn trước được hiệu quả của mạng trong tương lai
(khả năng tổng qt hố).
1.4.2.4. Mạng nơ-ron Hopfield
Trong mạng hồi quy tín hiệu ra của một nơ-ron có thể được truyền
ngược lại làm tín hiệu vào cho các nơ-ron ở các lớp trước, hoặc các nơ-ron
trong cùng một lớp. Phần này sẽ trình bày mơ hình mạng tiêu biểu thuộc lớp
mạng hồi quy, đó là mạng Hopfield.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>

19

Mạng Hopfield được bắt đầu nghiên cứu từ năm 1982. Đây là mạng
một lớp với thơng tin và q trình xử lý có nối ngược. Chính cơng trình của
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.
x1

X

Y1

x2

X

Y2

1

Đầu vào

.
.
.

2

Đầu ra


YM

Hình 1.3. Mơ hình mạng Hopfield
Ký hiệu Wij là liên kết giữa hai nơ ron i và j ( w ij

w ji ),

Vi là đầu ra

của nơron i. Ta coi véc tơ (V1, V2, ... Vn) là trạng thái của mạng. Tại mỗi thời
điểm t mỗi nơron i tổng hợp các tín hiệu Vj từ các nơron khác và tín hiệu từ
bên ngồi (bias) Ui

j

WiÞ Vj (t )

Ii .

Tuỳ theo hàm kích hoạt fi mà nơ ron i cho đầu ra là.
Vi(t+1) = fi(Vi(t)).
Mạng đạt trạng thái cân bằng nếu Vi(t+1) = Vi(t) ,

i

Ta định nghĩa hàm năng lượng của mạng là:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

/>