Trường Đại học Công Nghệ Thông Tin – ĐHQG TPHCM
ĐẠI HỌC QUỐC GIA TPHCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KHOA HỌC MÁY TÍNH

BÀI THU HOẠCH MÔN THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT
VẤN ĐỀ
Đề tài: BÀI TOÁN NGƯỜI DU LỊCH
GVHD: Đỗ Văn Nhơn
Học viên thực hiện:
Lê Chí Cảnh – CH1301081TP. H Chí Minh, tháng 10 năm 2014
Bài thu hoạch môn Thuật toán và các phương pháp giải quyết vấn đề
Trường Đại học Công Nghệ Thông Tin – ĐHQG TPHCM
Mục lục
Contents
Phần mở đầu
Lý do thực hiện và mục tiêu của đề tài
Trong cuộc sống của chúng ta việc tìm ra một hành trình di chuyển qua
các địa điểm ít ốn chi phí nhất là một bài toán kinh điển trong lĩnh vực khoa
học. Lời giải tìm có giá trị lớn trong hoạt động thực tiễn của con người, giúp
chúng ta di chuyển nhanh hơn, và tiết kiệm chi phí hơn. Tuy nhiên tính đến
thời điểm hiện tại thì vẫn chưa có giải thuật hiệu quả nào cho việc giải bài toán
này. Trong phạm vi bài thu hoạch này, em sẽ đưa ra một giải pháp để giải
Bài thu hoạch môn Thuật toán và các phương pháp giải quyết vấn đề
Trường Đại học Công Nghệ Thông Tin – ĐHQG TPHCM
quyết một bài toán tìm đường đi với chi phí ngắn nhất cho người du lịch (tiếng
Anh: travelling salesman problem – TSP ).
Bố cục bài thu hoạch

trước độ dài L, xác định xem có tn tại hay không một chu trình đi qua mỗi
đỉnh đúng một lần và có độ dài nhỏ hơn L) thuộc lớp NP-đầy đủ. Do đó, có
nhiều khả năng là thời gian xấu nhất của bất kì thuật toán nào cho TSP đều
tăng theo cấp số nhân với số thành phố.
TSP có một vài ứng dụng thậm chí trong dạng thức nguyên thuỷ của nó
như lập kế hoạch, logistic, và sản xuất các microchip. Thay đổi đi chút ít nó
xuất hiện như một bài toán con trong rất nhiều lĩnh vực như việc phân tích gen
trong sinh học. Trong những ứng dụng này, khái niệm thành phố có thể thay
đổi thành khách hàng, các điểm hàn trên bảng mạch, các mảnh DNA trong gen,
và khái niệm khoảng cách có thể biểu diễn bởi thời gian du lịch hay giá thành,
hay giống như sự so sánh giữa các mảnh DNA với nhau. Trong nhiều ứng
dụng, các hạn chế truyền thống như giới hạn tài nguyên hay giới hạn thời gian
thậm chí còn làm cho bài toán trở nên khó hơn.
Trong lý thuyết của độ phức tạp tính toán, phiên bản quyết định của bài
toán TSP thuộc lớp NP-đầy đủ. Vì vậy không có giải thuật hiệu quả nào cho
việc giải bài toán TSP. Hay nói cách khác, giống như thời gian chạy xấu nhất
cho bất ký giải thuật nào cho bài toán TSP tăng theo hàm mũ với số lượng
thành phố, vì vậy thậm chí nhiều trường hợp với vài trăm thành phố cũng đã
mất vài năm CPU để giải một cách chính xác.
Bài thu hoạch môn Thuật toán và các phương pháp giải quyết vấn đề
Trường Đại học Công Nghệ Thông Tin – ĐHQG TPHCM
CHƯƠNG 2: PHÁT BIỂU BÀI TOÁN NGƯỜI DU LỊCH
VÀ CÁC THUẬT GIẢI LIÊN QUAN
2.1. Phát biểu bài toán
Cho trước một tập của các thành phố và các chi phí đi lại giữa mỗi cặp
thành phố, bài toán người du lịch , hoặc viết tắt trong tiếng anh là
TSP, là để tìm ra chi phí thấp nhấp để đến thăm tất cả các
thành phố trong tập ban đầu và trở về điểm bắt đầu của
bạn. Trong điều kiện tiêu chuẩn, thì chúng ta quy
định chi phí đi lại là đối xứng theo nghĩa là đi du lịch

Ta có thể vận dụng kĩ thuật tìm kiếm địa phương để giải bài toán tìm
đường đi ngắn nhất của người giao hàng (TSP).
• Xuất phát từ một chu trình nào đó.
• Bỏ đi hai cạnh có độ dài lớn nhất không kề nhau, nối các đỉnh lại với
nhau sao cho vẫn tạo ra một chu trình đủ.
Tiếp tục quá trình biến đổi trên cho đến khi nào không còn cải thiện
được phương án nữa và kết luận.
2.3. Phương pháp tham lam (Greedy, một thuật giải Heuristic)
Tìm nghiệm của bài toán tối ưu thường đòi hỏi chi phí lớn về thời gian
tính toán và không gian bộ nhớ (ví dụ như bài toán TSP). Tuy nhiên trong
nhiều trường hợp ta chỉ tìm được một nghiệm đủ tốt, khá gần với nghiệm tối ưu
là đạt yêu cầu, nhất là khi có hạn chế về mặt thời gian và bộ nhớ. Phương pháp
tham lam xây dựng các thuật toán giải các bài toán tối ưu dựa trên tư tưởng tối
ưu cục bộ theo một chiến lược tư duy kiểu con người, nhằm nhanh chóng đạt
đến một lời giải "tốt". Có một số thuật toán dựa trên tư tưởng của phương pháp
tham lam thực sự tìm được phương án tối ưu (chẳng hạn thuật toán Kruscal tìm
cây khung cực tiểu), còn lại đa số các thuật toán dựa trên phương pháp tham
lam thường là thuật toán gần đúng, chỉ cho một lời giải xấp xỉ lời giải tối ưu.
Bài thu hoạch môn Thuật toán và các phương pháp giải quyết vấn đề
Trường Đại học Công Nghệ Thông Tin – ĐHQG TPHCM
Một số chiến lược tham lam
Phương pháp tham lam tìm nghiệm tối ưu dựa trên các chiến lược tối ưu
cục bộ của con người. Trước khi trình bày những thuật giải tham lam cho
những bài toán cụ thể, chúng tôi đề cập đến hai chiến lược tối ưu cục bộ cơ
bản:
- Chọn cái tốt nhất trước (còn gọi là "chọn miếng ngon trước". Đây là lí
do vì sao phương pháp này được gọi là "tham lam" hay "tham ăn").
- Cải tiến cái đang có thành cái tốt hơn.
1. Chiến lược thứ nhất thường được áp dụng khi xây dựng dần từng thành
phần của nghiệm tối ưu. Thuật giải sẽ đánh giá các lựa chọn theo một tiêu

khi đạt điều kiện dừng. Điều kiện dừng của thuật giải ILS có thể là số lần lặp
tối đa hoặc thời gian lặp tối đa cho phép. Các bước như sau:
- Bước 1: Perturbation (tạm dịch là bước nhiễu loạn): làm thay đổi lời
giải s* dựa trên thông tin history tạo ra lời giải mới s’.
- Bước 2: Local Search (bước tìm kiếm cục bộ): áp dụng thuật giải tìm
kiếm cục bộ cho lời giải đầu vào s’, tìm ra s*’ là lời giải tối ưu cục bộ tiếp theo.
- Bước 3: AcceptanceCriterion (bước chọn lời giải): nếu s*’ thoả tiêu
chuẩn chọn thì s*’ sẽ trở thành lời giải đầu vào cho vòng lặp tiếp theo, nếu
không lời giải đầu vào vẫn sẽ là s*. Có nhiều tiêu chí để chọn lời giải làm lời
giải đầu vào s*cho vòng lặp tiếp theo, cụ thể như sau:
+ Chỉ chuyển qua lời giải tối ưu nhất, nghĩa là nếu lời giải tối ưu cục bộ
s*’ ở bước 2 tốt hơn lời giải tối ưu cục bộ trước đó thì s*=s*’ ngược lại dùng
tiếp tục lời giải s* cũ. Đây là tiêu chí chọn có tính chuyên sâu cao, còn được
gọi là better acceptance criterion.
+ Luôn chuyển qua lời giải tối ưu vừa tìm được và không chú trọng đến
chất lượng lời giải, nghĩa là luôn luôn s*=s*’. Đây là tiêu chí chọn có tính đa
dạng hoá với tên gọi random walk acceptance criterion.
Bài thu hoạch môn Thuật toán và các phương pháp giải quyết vấn đề
Trường Đại học Công Nghệ Thông Tin – ĐHQG TPHCM
Cần lưu ý rằng trong khi Local Search tập trung tìm kiếm trong không
gian lời giải rộng lớn S, thì ILS chỉ cần tập trung tìm kiếm trong không gian
lời giải nhỏ hơn gm các lời giải tối ưu cục bộ. Hơn nữa, thuật giải ILS đơn
giản, dễ áp dụng và dễ thực hiện, có thể nói tính đơn giản là một ưu điểm lớn
của thuật giải này. ILS được đánh giá cao về hiệu quả trong việc tạo ra lời giải
gần với lời giải tối ưu. Thuật giải ILS vừa giữ được tính đơn giản của
Heuristic và vừa giữ được tính tổng quát chung của Metaheuristic. Ngoài ra,
thuật giải này rất linh động, cho phép người dùng chọn thuật giải Local Search
theo ý muốn. Gần đây, thuật giải này được sử dụng khá nhiều như các bài báo
của Ilina Stoilkovska, M. Stolevik và các cộng sự, F. Bellanti và các cộng sự,
E.K Burke và các cộng sự.

Từ một lời giải ban đầu ta sử dụng thuật giải tìm kiếm địa
phương local search để tìm ra một lời giải tốt hơn. Chi tiết là từ lời giải
ban đầu, ta sẽ bỏ đi hai đường có độ dài lớn nhất không kề nhau, sau
đó nối các địa điểm lại với nhau sao cho vẫn tạo ra một chu trình đủ.
Bài thu hoạch môn Thuật toán và các phương pháp giải quyết vấn đề
Iterated Local Search:
s
0
= initializeSolution();
s* = localSearch(s0);
while(termination condition met) {
s’ = perturba tion(s*, history);
s*’= localSearch(s’);
s* = acceptaceCriterion(s*,s*’, history)
}
Trường Đại học Công Nghệ Thông Tin – ĐHQG TPHCM
Tiếp tục quá trình biến đổi trên cho đến khi nào không còn giảm được
chi phí di chuyển cho lời giải đang xét thì dừng và lưu kết quả vào
biến s
*.
• Lưu ý là từ bước 3 đến bước 5 sẽ được thực thi trong vòng lặp
while, vòng lặp này bị dừng lại khi đạt đến thời gian lặp tối đa cho
phép.
3.3. Bước 3 - Làm nhiễu lời giải vừa tìm được
Từ một lời giải s
*
, ta tiến hành làm nhiểu để nhằm tìm ra một lời
giải mới khác với lời giải hiện tại. Để làm nhiểu chúng ta sẽ tiến hàn
bỏ đi bốn đường (thay gì bỏ đi 2 đường trong hàm tìm kiếm địa
phương ở bước 2) có chi phí lớn nhất không kề nhau, sau đó nối các

chỉ giữ lại một lời giải tối ưu nhất cho nên giải pháp ứng dụng Iterated
Local Search vào bài toán người du lịch sẽ tìm được một lời giải tối ưu
hơn lời giải của thuật giải tìm kiếm địa phương Local Search. Nhưng
có một điểm lưu ý là thời gian tìm kiếm lời giải của Iterated Local
Search sẽ lâu hơn Local Search do chúng ta thực hiện việc mở rộng
không gian tìm kiếm.
Tài liệu tham khảo
[1] . Wikipedia, Bài toán người bán hàng.
Bài thu hoạch môn Thuật toán và các phương pháp giải quyết vấn đề
Trường Đại học Công Nghệ Thông Tin – ĐHQG TPHCM
[2]. Thư viện học viện mở Việt Nam, Kỹ thuật tìm kiếm đia
phương.
[3]. Vũ Ngọc Sen, Nghiên cứu bài toán xếp lịch trực cho y tá.
Bài thu hoạch môn Thuật toán và các phương pháp giải quyết vấn đề