ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
ĐỀ TÀI
PHƯƠNG PHÁP HUERISTIC VÀ BÀI
TOÁN NGƯỜI ĐƯA THƯ
GVHD: PGS.TS. Đỗ Văn Nhơn
SVTH: Nguyễn Hải Yến
MSSV: CH1301074
TP. Hồ Chí Minh, ngày 19 tháng 01 năm 2014
t
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
LỜI NÓI ĐẦU
Bài toán tìm kiếm được xem là bài toán được nhiều người quan tâm, đặc
biệt là tìm kiếm tối ưu toàn cục. Có nhiều phương pháp để giải các bài toán tìm
kiếm tối ưu toàn cục như : phương pháp trực tiếp (áp dụng các công thức, định lý,
thuật giải đã có sẵn ), các phương pháp gián tiếp hoặc tìm kiếm lời giải thông dụng
(phương pháp thử sai, phương pháp vét cạn, phương pháp quay lui). Ngoài các
phương pháp nêu trên thì trong học phần “ Thuật toán và phương pháp giải quyết
vấn đề em còn được tiếp cận với các phương pháp hueristic và meta hueristic.
Và sau đây là bài thu hoạch của em : “Tìm hiểu về hueristic -
metahueristic - Giải pháp hueristic theo nguyên lý tham lam giải bài toán người
đưa thư ”.
Em xin gửi lời cảm ơn chân thành đến trường Đại học Công Nghệ Thông
Tin TP.HCM đã tạo điều kiện cho em được tiếp cận với môn học “Thuật toán và
phương pháp giải quyết vấn đề ”
Em xin cảm ơn Thầy PGS.TS. Đỗ Văn Nhơn đã tận tình truyền đạt kiến
thức và có những định hướng giúp em hoàn thành bài thu hoạch.
Mặc dù đã rất cố gắng nhưng bài thu hoạch của em khó tránh khỏi thiếu
sót em mong Thầy góp ý nhận xét để bài thu hoạch hoàn thiện hơn.

1.1. Khái niệm về lớp bài toán P và NP
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: 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.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 ‘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
SVTH : CH1301074 – Nguyễn Hải Yến 4
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
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 rất
nhiều, sau đây là một số ví dụ:
• 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 chia n cho b sau thời gian đa thức. Trong ví dụ này , b là bằng chứng
ngắn gọn (vì b<n) và dễ kiểm tra (có thuật toán đa thức để kiểm tra b đúng

Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
1.1.4. Lớp bài toán P
Định nghĩa. 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.
Ví dụ: Bài toán cây khung nhỏ nhất giải được nhờ thuật toán Prim với thời gian
0(n
2
) thuộc lớp bài toán P.
1.1.5. Lớp bài toán NP
Định nghĩa. 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ụ: 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< b < n) của n. Để
kiểm tra xem b có phải là ước số của n hay không ta có thể thực hiện phép chia n
cho b sau thời gian đa thức. Trong ví dụ này dễ thấy b là bằng chứng ngắn gọn
(b<n) và dễ kiểm tra (có thuật toán thời gian tính đa thức để kiểm tra xem b có là
ước số của n).
1.1.6. Lớp bài toán Co- NP
Định nghĩa. Ta gọi Co-NP là lớp các bài toán quyết định mà để xác nhận câu trả
lời ‘no’ của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ: Bài toán kiểm tra tính nguyên tố: “Có phải n là số nguyên tố không?”, để
đưa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời ‘no’ cho đầu vào n ta
có thể đưa ra một ước số b của n.
1.1.7. Lớp bài toán NP- đầy đủ (NP- complete)
Định nghĩa. Một bài toán quyết định A được gọi là NP-đầy đủ (NP-Complete)
nếu như:
• A là một bài toán trong NP.
• Mọi bài toán trong NP đều có thể quy dẫn về A.
Bổ đề. Giả sử bài toán A là NP-đầy đủ, bài toán B thuộc NP, và bài toán A qui dẫn
được về bài toán B. Khi đó bài toán B cũng là NP-đầy đủ

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ó.
Sau đây là mô hình phân lớp các bài toán đã nêu trê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. 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.
1.2. Mở rộng khái niệm thuật giải
Trong quá trình nghiên cứu giải quyết các vấn đề - bài toán, người ta đã đưa
ra những nhận xét như sau :
• Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu
thuật toán và cũng không biết là có tồn tại thuật toán hay không.
SVTH : CH1301074 – Nguyễn Hải Yến 8
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
• Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì
thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán
khó đáp ứng.
• Có những bài toán được giải theo những cách giải vi phạm thuật toán
nhưng vẫn chấp nhận được.
Từ những nhận định trên, người ta thấy rằng cần phải có những đổi mới cho
khái niệm thuật toán. Người ta đã mở rộng hai tiêu chuẩn của thuật toán : tính xác
định và tính đúng đắn. Việc mở rộng tính xác định đối với thuật toán đã được thể
hiện qua các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán bây giờ
không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần
đúng. Trong thực tiễn, có nhiều trường hợp người ta chấp nhận các cách giải
thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức tạp và

Thuật giải 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ường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất).
− Giải bài toán theo thuật giải Heuristic 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.
− Thuật giải Heuristic 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ơ sở 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):
SVTH : CH1301074 – Nguyễn Hải Yến 10
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
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.
− 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.5. Thuật giải di truyền (GA)
1.5.1. Giới thiệu

Một NST được tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác
nhau để quy định một tính trạng nào đó. Trong GA, một gen được coi như một
phần tử trong chuỗi NST.
1.5.2.2. Quần thể
Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đấy. Trong
giải thuật di truyền ta quan niệm quần thể là một tập các lời giải của một bài
toán.
1.5.2.3. Các toán tử di truyền
• Chọn lựa
Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay
đổi các cá thể trong quần thể. Những cá thể tốt, thích nghi được với điều
kiện sống thì có khả năng đấu tranh lớn hơn, do đó có thể tồn tại và sinh
sản. Các cá thể không thích nghi được với điều kiện sống thì dần mất đi.
Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn trong tự
SVTH : CH1301074 – Nguyễn Hải Yến 12
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
nhiên, chọn lựa các cá thể trong GA chính là cách chọn các cá thể có độ
thích nghi tốt để đưa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục
đích là sinh ra các cá thể mới tốt hơn. Có nhiều cách để lựa chọn nhưng
cuối cùng đều nhằm đáp ứng mục tiêu là các cá thể tốt sẽ có khả năng được
chọn cao hơn.
• Lai ghép
Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để
sinh ra thế hệ con. Trong giải thuật di truyền, lai ghép được coi là một sự tổ
hợp lại các tính chất (thành phần) trong hai lời giải cha mẹ nào đó để sinh
ra một lời giải mới mà có đặc tính mong muốn là tốt hơn thế hệ cha mẹ.
Đây là một quá trình xảy ra chủ yếu trong giải thuật di truyền.
• Đột biến
Đột biến là một sự biến đổi tại một ( hay một số ) gen của nhiễm sắc
thể ban đầu để tạo ra một nhiễm sắc thể mới. Đột biến có xác suất xảy ra

. Nếu không thực hiện lai ghép, con sinh ra sẽ giống
hoàn toàn bố mẹ. Nếu được lai ghép, con sinh ra sẽ có một phần giống bố và một
phần giống mẹ.
• Xác suất đột biến
Xác suất đột biến cho biết tính thường xuyên của việc các gen của NST
thay đổi như thế nào. Nếu xác suất đột biến là pm, khi đó khả năng để mỗi gen
của một NST bất kỳ bị đột biến là p
m
. Tác dụng của toán tử đột biến là ngăn ngừa
giải thuật di truyền rơi vào tình trạng cực trị địa phương, tuy nhiên nếu thực hiện
đột biến với xác suất quá cao sẽ biến giải thuật di truyền thành giải thuật tìm kiếm
ngẫu nhiên.
• Kích thước quần thể
Kích thước quần thể cho biết có bao nhiêu cá thể trong một quần thể (trong
một thế hệ). Qua các nghiên cứu cũng như các thử nghiệm đã cho thấy kích thước
quần thể không nên quá bé cũng như không quá lớn. Nếu có quá ít cá thể thì ít có
khả năng thực hiện lai giống và chỉ một phần nhỏ không gian tìm kiếm được dùng.
Như vậy sẽ dễ xảy ra trường hợp bỏ qua các lời giải tốt. Nhưng quá nhiều cá thể
cũng không tốt vì GA sẽ chạy chậm đi, ảnh hưởng đến hiệu quả của giải thuật. Các
nghiên cứu cũng đã chỉ ra không có lợi khi tăng kích thước quần thể lên quá một
giới hạn cho phép.
1.5.5. Các cách mã hóa NST
• Mã hoá nhị phân
Mã hoá nhị phân là phương pháp mã hoá nhiễm sắc thể phổ biến nhất.
Trong mã hoá nhị phân, mỗi nhiễm sắc thể là một chuỗi nhị phân, mỗi bit trong nó
có thể biểu diễn một đặc tính của nghiệm.
Ví dụ: hai nhiễm sắc thể 1 và 2 có chiều dài là 16.
Nhiễm sắc thể 1: 1101100100110110
SVTH : CH1301074 – Nguyễn Hải Yến 15
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn

ta thường phải phát triển các toán tử đột biến và lai ghép cho phù hợp với từng bài
toán.
1.5.6. Khởi tạo quần thể
Khởi tạo quần thể ban đầu là ta tạo ra một cách ngẫu nhiên các lời giải có
thể (thường là các lời giải thỏa mãn ràng buộc của bài toán nhưng chưa biết là đại
lượng cần tối ưu đã là tối ưu hay chưa). Tuỳ vào từng bài toán cụ thể mà ta có các
phương pháp khởi tạo khác nhau.
Chất lượng của quần thể ban đầu càng cao thì lời giải mà giải thuật di
truyền đưa ra càng tốt. Trong nhiều giải thuật di truyền, thường sử dụng các giải
thuật đã có để giải bài toán mà cho kết quả khá tốt để khởi tạo quần thể ban đầu.
Xây dựng hàm thích nghi sao cho giá trị thích nghi phải phản ánh được giá
trị thực của NST trong việc đáp ứng yêu cầu của bài toán. Ví dụ như trong các bài
toán về cây khung nhỏ nhất thì hàm thích nghi sẽ là hàm tính tổng trọng số các
cạnh trên các cây khung.
Trong giải thuật di truyền thì hàm tính độ thích nghi là một trong hai yếu tố
quan trọng nhất quyết định sự thành công hay thất bại của GA.
Có nhiều cách để lựa chọn các cá thể từ quần thể: lựa chọn theo tỉ lệ, lựa
chọn theo xếp hạng, lựa chọn theo cơ chế lấy mẫu ngẫu nhiên, lựa chọn tranh đấu
1.5.7. Các toán tử di truyền
• Mã hoá nhị phân
1.5.7.1. Toán tử lai ghép
Lai ghép đơn điểm cắt :
− Một điểm cắt được chọn tại một vị trí thứ k trên NST.
− Từ đầu NST đến vị trí k, NST con sao chép từ cha, phần còn lại sao
chép từ mẹ.
SVTH : CH1301074 – Nguyễn Hải Yến 17
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Lai ghép hai điểm cắt :
− Hai điểm cắt được chọn .
− Từ đầu cho đến điểm cắt thứ nhất được sao chép từ cha, từ điểm cắt

Kiến là loại cá thể sống bầy đàn. Chúng giao tiếp với nhau thông qua mùi mà
chúng để lại trên hành trình mà chúng đi qua. Mỗi kiến khi đi qua một đoạn
đường sẽ để lại trên đoạn đó một chất mà chúng ta gọi là mùi. Số lượng mùi sẽ
tăng lên khi có nhiều kiến cùng đi qua. Các con kiến khác sẽ tìm đường dựa vào
mật độ mùi trên đường, mật độ mùi càng lớn thì chúng càng có xu hướng chọn.
Dựa vào hành vi tìm kiếm này mà đàn kíên tìm được đường đi ngắn nhất từ tổ đến
nguồn thức ăn và sau đó quay trở tổ của mình.
Sau đây là ví dụ về luồng đi của đàn kiến thực tế
SVTH : CH1301074 – Nguyễn Hải Yến 20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
a. Kiến đi theo đường thẳng giữa A và E
b. Khi có chướng ngại vật kiến sẽ chọn hướng đi, có hai hướng với khả năng
kiến sẽ chọn là như nhau.
c. Trên đường ngắn hơn thì nhiều mùi (pheromone) hơn
1.6.2. Mô hình giải thuật
Procedure ACO
Initial();
While (!ĐK dừng) do
ConstructSolutions();
LocalSearch(); /*Tuỳ ý, có thể có hoặc không
UpdateTrails();
End;
End;
trong đó:
ĐK dừng (tức là điều kiện dừng) là điều kiện đạt được khi thuật toán ở
trạng thái kết thúc. Với bài toán người đưa thư thì ĐK dừng là điều kiện đạt được
khi số vòng lặp của thuật toán = số vòng lặp lớn nhất do người dùng tự định nghĩa
hoặc là tất cả đàn kiến đều đi theo một đường (tức là đường đi ngắn nhất).
SVTH : CH1301074 – Nguyễn Hải Yến 21
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn

Với V = tập đỉnh = { V
1
, V
2
,…,V
n
} = tập các địa chỉ cần phát thư (mỗi
đỉnh của đồ thỉ là một số nguyên Đỉnh 1, Đỉnh 2,…, Đỉnh n )
E = tập cạnh = { e1,e2,…,en} ei > 0 ∀i∈[1, n]
Input : Đỉnh xuất phát x ∈ V
Output: Chu trình hamilton ngắn nhất xuất phát từ x

≡ Độ dài đường đi Sum = ?
Đường đi theo thứ tự các đỉnh như thế nào ? ( x, …., x)
SVTH : CH1301074 – Nguyễn Hải Yến 23
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
// Mảng các đỉnh đi qua
2.3. Cách giải quyết
Trong trường hợp ta sử dụng thuật toán tối ưu cho bài toán này, chẳng hạn
như thuật toán vét cạn : thực hiện lựa chọn một phương án trong tập hợp tất cả các
phương án của bài toán để tìm ra phương án tối ưu. Khi số lượng các điểm giao
thư khá lớn  không gian các phương án quá lớn. Do vậy, khi áp dụng thuật toán
vét cạn không đảm bảo về thời gian cũng như kĩ thuật (độ phức tạp thuật toán là
O(n!)  Không thể thực hiện thuật toán). Vấn đề đặt ra là phải cải tiến thuật toán
vét cạn như thế nào để giải quyết các yếu điểm đó. Trong phạm vi bài thu hoạch
này em xây dựng một giải pháp hueristic theo nguyên lý “tham lam”
2.4. Thiết kế thuật toán
2.4.1. Ý tưởng
• Trên thực tế theo kinh nghiệm thì khi ta chọn đi trên những đoạn đường ngắn
nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất

2.2. DS đỉnh đã đi qua  Next ;// V[i] = Next
2.3. Sum += G[v[ht]][v[i]];
2.4. Đỉnh ht = Next; // đỉnh hiện tại
}
2.5. Cài đặt thuật toán
- Một ma trận vuông cấp n thể hiện thông tin của đồ thị dưới dạng file
“graph.txt”
SVTH : CH1301074 – Nguyễn Hải Yến 25