TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN TP HỒ CHÍ MINH
KHOA KHOA HỌC MÁY TÍNH
 
BÁO CÁO ĐỀ TÀI MÔN TOÁN CHO MÁY TÍNH
Đề tài : PHÂN TÍCH VÀ THIẾT KẾ THUẬT GIẢI CHO BÀI
TOÁN “NGƯỜI DU LỊCH” GV: PGS. TS Nguyễn Phi Khứ
HV: Dương Thị Xuân Thoại
Mã số: CH1301061 TP Hồ Chí Minh, 2013
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN TP HỒ CHÍ MINH
KHOA KHOA HỌC MÁY TÍNH

 Với khoảng cách là metric 3
 Với khoảng cách không là metric 4
5. Các giải thuật giải bài toán TSP 4
 Các giải thuật để tìm lời giải chính xác 4
 Heuristic và các giải thuật xấp xỉ 5
6. Thuật giải Heuristic 7
7. Ứng dụng nguyên lý Greedy vào giải bài toán TSP 7
8. Đánh giá thuật giải Heuristic của thuật toán 9
9. Một số ví dụ minh hoạ 11 Mục lục hình
Hình 1 – Mô hình đồ thị của bài toán TSP 3
Hình 2 – Mô hình ban đầu 8
Hình 3 – Mô hình các bước chọn lựa đường đi 9
Hình 4 – Ví dụ 1 12
Hình 5 – Ví dụ 2 12
Hình 6 – Ví dụ 3 13
MSHV: CH1301061_Dương Thị Xuân Thoại

Trang 1

1. Giới thiệu bài toán
i du lch (Travelling Salesman problem (TSP)) là mt bài toán khá ni
ti vc t hc nghiên cu trong lý thuyt khoa hc máy tính. Ni
dung ca c phát bit danh sách các thành ph và
khong cách gia chúng , nhim v là phn nht có th mà ch i


Trang 2

xét gii thut brute-force và quan sát thy tính không ta heuristic da trên láng ging
gn nht.
Hassler Whitney  i hc Princeton University là ngu i du
lch cho bài toán .
Trong nh nên ngày càng ph bin trong khoa hc
 châu Âu và M. Nhc k  George Dantzig, Delbert
Ray Fulkerson và Selmer M. Johnson ti RAND Corporation  Santa Monica, nhi
 nguyên tuyn tính và phát tric ct cho li
gii ca nó. Vi nhc mi này h c mt thí d ca bài toán vi 49
thành ph  xây dng mt cách tng minh rn
a. Trong nhng thp k tic nghiên cu bi rt nhiu nhà nghiên
c t toán hc , khoa hc máy tính , hóa hc ,vt lý và nhng khoa hc khác.
Richard M. Karp  ch ra rng bài toán chu trình Hamiltonian thuc lp NP-
complete ra tính NP khó (NP-hardness ) cu này gii thích
mt cách khoa h phc tp tính toán ca vic tìm li gii t
Nhiu thành tc trong sut nhi thp k 1970 và 1980, khi
Grötschel, Padberg, Rinaldi và nhi khác c gng gii mt cách chính xác mt th
hin ca bài toán vi 2392 thành ph, s dc ct và branch-and-bound.
Trong nh Applegate, Bixby, Chvátal
trình Concorde c s dng nhiu trong vic gin nay .
 t tp các th hin ca
bài toán TSP vi nhi c s dng bi nhiu nhóm nghiên cu
 so sánh kt quc  dài ti
i th hin ca bài toán TSP lên ti 33,810 thành ph c ly ra t bài
toán xây dng layout cho microchip, cho ti nay vn là th hin ln nht trong các th hin 
TSPLIB .Nhiu th hin khác vi hàng triu thành ph , li gic có th chng minh
nm sai khác 1% so vi li gii t

MSHV: CH1301061_Dương Thị Xuân Thoại

Trang 4

Nhng chiu dài ct metric trong tnh . Khi các thành ph
m trên tm hình, nhiu hàm khong cách t nhiên là các metric ví
d 
 Trong bài toán Euclidian TSP khong cách gia 2 thành ph là khong cách Euclide
ging.
 Trong bài toán Rectilinear TSP khong cách gia 2 thành ph là tng hai t x và
y ca chúng. c gi là khong cách Manhattan hay city-block
metric.
 Trong maximum metric, khong cách gia 2 thành ph là max c chênh lêch ta
 x và y ca chúng.
Hai metric cui xut hin trong ving mp các h trong mch in.
ng tnh t th nht ri ti t kia, vì vy thi
gian di chuyn ti mm mi là tng c ng di chuyng
vi mày mà chnh c 2 t cùng 1 lúc vì vy th di chuyn ti mm mi
quynh bi di chuy
 Với khoảng cách không là metric
Khong cách không tha mãn bng thc tam giác phát sinh trong nhinh
tuyn. Ví d trong mt kiu vn tch bng máy bay có th c dù
khong cách di chuy
5. Các giải thuật giải bài toán TSP
 Các giải thuật để tìm lời giải chính xác
Li gii trc tip nht có th là th tt c các hoán v và xem hoán v nào là tt nht ( dùng
brute-force) . Thi gian chy cho cách tip cn này là O(n!), vì vy cách tip cn này thm
chí không th thc hin vi ch 20 thành ph .Mt trong s nhng ng dng mt
ca quy hong là gii thu phc tp O(n
2

Vào tháng 3- 2005, i du lch vi 33,810 m trong 1 mc gii
quyt s dung công c Concorde TSP Solver: ng t 
c tìm thc chng khi lng tính
toán mt khong 15.7  CPU (Cook et al. 2006). 2006 mt bài toán vi
85,900 c gii quyt bi Concorde TSP Solver, và mt khong 136 
CPU .
 Heuristic và các giải thuật xấp xỉ
Rt nhiu heuristics và gii thut xp x, có th i gii t
xut. c hii có th tìm li gii cho bài toán cc ln (hàng triu thành
ph) trong khong thi gian chp nhc vi li gii xp x ch khác 2-3% so vi li gii
t
Mt vài kic tìm ra.
 Heuristics xây dựng
Gii thut láng ging gn nht nearest neighbour (NN) (hay còn gi là gii thut tham lam
greedy algorithm)  i du lch chn thành ph gn nhn di
chuyn tip theo. Gii thun và hiu qu . Cho
khong N thành ph phân b ngu nhiêu trên mt phng trung bình gii thui
gii có chiu dài xp x 1.25 * ln chiu dài c
Tuy nhiên, có nhiu cách sp xc bit các thành ph làm cho gii thu
i t nht (Gutin, Yeo, and Zverovich, 2002).  bài toán TSP
i xng và bi xng (Gutin and Yeo, 2007).
MSHV: CH1301061_Dương Thị Xuân Thoại

Trang 6

Gt heuristic mMatch Twice and Stitch (MTS) (Kahng, Reda 2004.
MTS y tính hiu qu n so vi nhng heuristic xây dng hin ti . MTS
thc hin hai ln khp tun t , mà ln khp th c thc hin sau khi xóa tt c các cnh
ca ln khp th nh a ra tp tt c 
i cùng

MSHV: CH1301061_Dương Thị Xuân Thoại

Trang 7

search và evolutionary computing. K thu Lin-Kernighan technique mang li kt qu
m bo ít nht là bn so vi 3-opt. c Lin-Kernighan-Johnson tính mt
Lin-Kernighan , t bin (xóa ít nht 4 cnh
và ni lc v-opt i ). t
bi  di chuyi cc b  local minimum ). K
thut V-t trong s nhng heuristic mnh cho bài toán và có th gii
quyng hc bing bài toán TSP
không phi metric mà nhng heuristic khác không gii quyc.
6. Thuật giải Heuristic


















b. u mong mun, khi  trên ng ngn nht thì cui cùng ta s có mt hành
trình ngn nht. u này không phi lúc nào cng úng. Vi u kin trong hình thì thut
gii cho ta mt hành trình có chiu dài là 14 trong khi hành trình ti u là 13. Kt qu ca
thut gii ng hp này ch lch  v so vi kt qu ti u. Trong khi
ó,  phc tp ca thut gii Heuristic này ch là O(n
2
).

Hình 2 – Mô hình ban đầu
MSHV: CH1301061_Dương Thị Xuân Thoại

Trang 9
Hình 3 – Mô hình các bước chọn lựa đường đi
Các c ca thut toán:
c 1: Chn mt nh bt u V.
c 2: T nh hin hành chn cnh ni có chiu dài nh nht n các nh ch
ving th.  du ã ving th nh va chn.
c 3: Nu còn nh ch ving th thì quay li c 2.
c 4: Quay li nh V.
8. Đánh giá thuật giải Heuristic của thuật toán
Input: Ma trn nxn (n là s m (thành ph) cn  qua)
Output: Chu trình ng  ngn nht qua tt c các m (thành ph))
Basic operation:
-Duyt nh.
-So sánh tìm min các cnh ni nh hin ti và các nh ch  qua.
Thut toán:
MSHV: CH1301061_Dương Thị Xuân Thoại

MSHV: CH1301061_Dương Thị Xuân Thoại

Trang 11

v[0]=x;
for(int i=1;i<n;i++)
{
nh có khong cách nh nht t nh k tip
v[i]=next
e=next
}
v[n]=x;
Ta có chu trình t t c nh c th và tr v x.
 m: Thut toán Heuristic cho bài toán i du lch có  phc tp O(n
2
) tt
h rt nhiu so vi thut toán ti  (có  phc tp O(n!)).
c m: thut gii có nhng hn ch, ch cho ra li gii chính xác.
Kt lun: Thut gii Heuristic cho bài toán i du lch tuy ch  ra c li
gii chính xác cho bài toán, nh nó cho ra mt li gii có th chp nhn c vi  phc
tp thp h nhiu so vi thut toán ti u.
9. Một số ví dụ minh hoạ
Ch trình vit bng ngôn ng C# 2005. Ch trình s c  th (ma trn) t file
Graph.txt và xut ra kt qu.  th nhp vào phi là  th y  nu không phi thì không
xut ra chu trình Hamilton. Ngc li, thì xut ra chu trình Hamilton.
MSHV: CH1301061_Dương Thị Xuân Thoại

Trang 12