Bài toán người du lịch và các thuật giải

Tr
ng i hc Khoa hc T nhiên TP.HCM Khoa CNTT L
p CNTN2008 H tên sinh viên: Trn Vinh Kính MSSV: 0812252
 ÁN CUI K LÝ THUYT
 TH  tài: Bài toán ng
i du lch và các thu t gi i Giáo viên lý thuyt: Dng Anh c Giáo viên h
ng d n th c hành: ng Nguyn c Tin, Nguyn Huy Khánh 2 N
i dung  án 1/Gi
i thi u v lch s ca bài toán ngi du lch ................................................................... 2 2/Mô t chi tit bài toán............................................................................................................ 3 3/Thut gii chính xác .............................................................................................................. 4 4/Các thut gii gn úng (Heuristic) ...................................................................................... 6 4.1/Thut gii tham lam (thut gii láng ging gn nht) .................................................. 6 4.2/Thut toán nhánh cn ................................................................................................... 7 1/Gi
i thiu v lch s ca bài toán ngi du lch Bài toán ngi du lch là mt vn  kt ni ti u trong nghiên cu khoa hc máy tính. Cho mt danh sách các thành ph và các cp khong cách gia 2 thành ph trong ó, nhi m v là phi tìm mt chu trình ngn nht  thm mi thành ph mt ln duy nht. Hình minh ho cho bài toán ngi du lch Trong hình trên, tour  ngi du lch có th thm ht tt c các thành ph v
i chi phí ngn nht  c th hi n b!ng các cnh màu ". Vn  này  c nêu ra ln u tiên nh là mt vn  toán hc vào nm 1930 và là vn   c tp trung nghiên cu nhiu nht trong l#nh v c ti uu. Nó  c s dng th nghi m, ánh giá các thut toán ti u. Tuy vn  có tính phc tp cao, nhng có rt nhiu phng pháp chính xác và gn úng ã  c bit n, do ó có th gii  c vài trng h p có n 10 ngàn thành ph. Trong nhng nm 1950 và 1960, bài toán tr$ nên ph% bin trong gi
i khoa hc châu Âu và $ M&. Các công trình áng k u tiên  c th c hi n b$i George Dantzig, Delbert Ray Fulkerson và Selmer M. Johnson ngi ã  xut bài toán nh mt chng trình tuyn tính và phát trin phng pháp nhánh cn cho bài toán. V
i các phng pháp m
i h ã gii mt trng h p v
i 49 thành ph mt cách ti u b!ng cách xây d ng mt chu trình và 3 chng minh r!ng không có chu trình nào ngn hn. Trong nhiu thp k' sau ó, bài toán  c nghiên cu trong rt nhiu ngành nh toán hc, khoa hc máy tính, hoá hc, và vt lý. 2/Mô t chi ti t bài toán Bài toán ngi du lch có th biu din thành mt ( th, trong ó các thành ph là các 'nh, các con ng i li gia các thành ph là các cnh, (ng thi khong cách gia các thành ph là trng s tng ng ca cnh ni chúng. Tt nhiên, ( th sau khi xây d ng xong là ( th , gia hai thành ph không có ng i tr c tip mà phi thông qua mt thành ph khác thì ta gán trng s ca cnh ó s l
n nht có th. Khi ó, bài toán ngi du lch tr$ thành bài tìm mt chu trình Hamilton ngn nht, và l trình ca ngi du lch chính là chu trình Hamilton ngn nht. Bn Thành Nhà hát TP Sân bay TSN m Sen H KHTN Bn Thành 0 1 6 7 3 Nhà hát TP 1 0 6 8 4 Sân bay TSN 6 6 0 5 7 m Sen 7 8 5 0 6 H KHTN 3 4 7 6 0 Nu nh khoàng cách gia hai thành ph bt k) là nh nhau cho c hai h
ng thì dùng ( th vô h
ng, ng c li ta s dng ( th có h
ng. Trong ví d trên, ta gi nh ng i t* 2 h
ng là nh nhau. Trng h p khong cách gia các thành ph trong ( th là khong cách metric (tc là tho bt +ng thc tam giác Cij , Cik + Ckj), thì khong cách tr c tip t* thành ph A n thành ph B là khong cách ngn nht và không bao gi l
n hn khong cách mà có thông S KHTN BT NH TSN 5 6 6 7 8 7 6 3 1 4 4 qua thành ph C. Th c t, khi các thành ph  c biu din b$i các im trên mt ph+ng, rt nhiu các khong cách gn nh là khong cách metric. Trong nhiu trng h p, các khong cách không tho bt +ng thc tam giác hoc do tiêu chí ánh giá khong cách không thuc không gian metric ch+ng hn nh khong cách theo tiêu chí thi gian di chuyn, rõ ràng máy bay di chuyn nhanh hn nhiu so v
i ôtô mc dù khong cách di chuyn có th l
n hn. 3/Thut gi i chính xác Trong các thut gii chính xác cho bài toán ngi du lch, u tiên phi k n thut toán vét cn. Thut toán này tìm tt c các chu trình Hamilton trong ( th, sau ó chn mt chu trình nh" nht làm áp án. Vi c tìm chu trình Hamilton  c th c hi n theo phng pháp duy t chiu sâu và kt h p quay lui. Do quá trình duy t có th rt sâu nên ta không s dng  quy mà dùng stack  kh  quy. S dng mt bin min  lu li t%ng trng s ca chu trình Hamilton nh" nht. Ban u min=+- hoc min = m* trng s ca cnh l
n nht. Chu trình Hamilton là chu trình i qua ht tt c các 'nh và sao ó quay v 'nh xut phát, do ó, ta dùng mt danh sách ChuaXet[]  lu li các 'nh cha xét, mt bin Sum  lu li trng s ca chu trình hi n thi, do chu trình Hamilton không quan trng 'nh xut phát, ta chn 'nh xut phát là 'nh có ch' s nh" nht là 1. Quá trình duy t nh sau: -Ban u a 'nh 1 và 0 vào stack, Sum = 0. -Lp li quá trình sau: Ly (Top) 'nh t* stack ra là 'nh i và trng s ts, gán ChuaDuyet[i] là false và Sum+=ts, np 0 0 vào stack sau ó np các 'nh k j và trng s tng ng v
i 'nh ang xét mà ChuaDuyet[j]=true, nu i không có 'nh k tho yêu cu, tc là ã duy t ht tt c các 'nh (do ( th ang xét là ( th ). Ta cng trng s ca cnh i
1 vào Sum và gán min b!ng Min(Sum, min). Sum – = cnh i
1. Lp li quá trình sau: Ly 'nh t* stack ra, nu 'nh này không còn 'nh k tho yêu cu thì Pop 'nh và trng s này ra, nu có 'nh tho thì thoát vòng lp và duy t tip t* 'nh này, trng h p ly 'nh t* stack ra là 0 thì Pop 2 ln  ly 2 'nh liên tc trong stack ra sau ó tip tc vòng lp. 5 Stack 'nh Stack trng s 'nh ang xét Sum Min 1 0 0 +- 1,0,4,3,2 0,0,1,6,3 1 0 .. 1,0,4,3,2,0,4,3 0,0,1,6,3,0,7,5 2 3 .. 1,0,4,3,2,0,4,3,0,4 0,0,1,6,3,0,7,5,0,2 3 8 .. 1,0,4,3,2,0,4,3,0,4,0 0,0,1,6,3,0,7,5,0,2,0 4 8+2+1=11 11 1,0,4,3,2,0,4 0,0,1,6,3,0,7 4 11-1-2-5=3 .. 1,0,4,3,2,0,4,0,3 0,0,1,6,3,0,7,0,2 4 10 .. 1,0,4,3,2,0,4,0,3,0 0,0,1,6,3,0,7,0,2,0 3 10+2+6=18 11 1,0,4,3 0,0,1,6 3 18-6-2-7-3=0 .. 1,0,4,3,0,4,2 0,0,1,6,0,2,5 3 6 .. 1,0,4,3,0,4,2,0,4 0,0,1,6,0,2,5,0,7 2 11 .. 1,0,4,3,0,4,2,0,4,0 0,0,1,6,0,2,5,0,7,0 4 11+7+1=19 11 1,0,4,3,0,4 0,0,1,6,0,2 4 19-1-7-5=6 .. 1,0,4,3,0,4,0,2 0,0,1,6,0,2,0,7 4 8 .. 1,0,4,3,0,4,0,2,0 0,0,1,6,0,2,0,7,0 2 8+7+3=18 11 1,0,4 0,0,1 4 18-3-7-2-6=0 .. 1,0,4,0,3,2 0,0,1,0,2,7 4 1 .. 1,0,4,0,3,2,0,3 0,0,1,0,2,7,0,5 2 8 .. 1,0,4,0,3,2,0,3,0 0,0,1,0,2,7,0,5,0 3 8+5+6=19 11 1,0,4,0,3 0,0,1,0,2 3 19-6-5-7=1 .. 1,0,4,0,3,0,2 0,0,1,0,2,5 3 3 .. 1,0,4,0,3,0,2,0 0,0,1,0,2,5,0 2 3+5+3=11 11 Kt thúc thut toán, ta tìm  c chu trình Hamilton là 1
2
3
4
1 v
i  dài là 11. 1 4 2 3 3 7 5 6 1 2 1 4 2 3 3 7 5 6 1 2 6 4/Các thut gi i gn úng (Heuristic) 4.1/Thut gii tham lam (thut gii láng gi ng g n nht) Thut gii vét cn $ trên cho ta mt áp án ti u, tuy nhiên  phc tp ca nó là quá cao (n-1)! thuc nhóm O(n!). Do ó, trong th c tin ngi ta chp nhn các thut gii cho kt qu tt (nhng không phi lúc nào c.ng tt) b$i s n gin, nhanh chóng và cài t d dàng. Mt trong các thut gii ó là thut gii tham lam hay còn gi là thut toán láng ging gn nht. Trong thut toán này, ti mi b
c, ta chn con ng (cnh) ni v
i thành ph ('nh) gn nht v
i hy vng r!ng n con ng ngn nht s/ cho ra ng i ngn nht. Ví d sau ây minh ho cho thut gii tham lam v
i n=5 áp án ca thut toán tham lam thng là tt (tuy không phi ti u) vì áp án ti u là 1
3
4
5
2
1 v
i chi phí là 10 so v
i kt qu ca thut toán tham lam là 14. Hàm minh ho cho thut toán tham lam: int run(int n,int id) { int min; int b[100]; //L
u li 
ng i int count = 0; //S nh ã thm int temp; //Ch s ca nh g n nh t int s=0; b[0] = k; while(count < n) { min=10000; //L
u li trng s ca cnh nh nh t for(int i = 0;i < n; i++) //chn ra cnh ni v i nh g n nh t 1 4 2 3 3 7 4 3 1 2 5 4 2 1 3 1 4 2 3 3 7 4 3 1 2 5 4 2 1 3 1 4 2 3 3 7 4 3 1 2 5 4 2 1 3 1 4 2 3 3 7 4 3 1 2 5 4 2 1 3 1 4 2 3 3 7 4 3 1 2 5 4 2 1 3 1 4 2 3 3 7 4 3 1 2 5 4 2 1 3 7 if(a[id][i] 0 && check (i,b,n) == 1) //check: kim tra ã thm nh i ch
a // là 1 nu ch
a thm, 0 nu thm ri { min = a[id][i];//Cp nht li trng s nh nh t temp = i; //Cp nht li ch s } if(count<n-1) s=s+min; b[count + 1] = temp; id = temp; count ++; } s=s+a[id][k]; //Cng v i trng s ca cnh t nh cui n nh xu t phát b[n] = k; cout << "Duong di ngan nhat: "; for(int i = 0; i < n; i++) cout "; cout<<b[n]; cout<<"\n\n"; cout<<"Quang duong ngan nhat nguoi du lich nen di la: "<<s; cout<<"\n\n"; return 0; } Thut gii tham lam có  phc tp nh" hn nhiu so v
i gii thut vét cn, chi phí cho gii thut này là n(n-1)/2 thuc nhóm O(n2). Tuy nhiên, nh ã nói $ trên, gii thut này không phi luôn luôn úng, trong mt s trng h p, li gii ca thut gii tham lam rt t nh trong ví d sau: 4.2/Thut toán nhánh cn Thut toán nhánh cn là phng pháp ch yu  gii các bài toán ti u t% h p. T t$ng c bn ca thut toán là trong quá trình tìm kim li gii, ta s/ phân hoch tp các phng án thành hai hay nhiu nhánh con nh cây tìm kim, sau ó ánh giá t*ng nhánh  1 4 2 3 100 7 5 7 5 7 5 7 7 5 5 1 4 2 3 100 7 5 7 5 7 5 7 7 5 5 8 quyt nh xem nên tip tc $ nhánh nào và loi b" nhánh mà các phng án con ca nó không th là phng án ti u. Trong thut gii trình bày d
i ây, chúng ta s/ tìm li gii d a trên ma trn trng s C[ ][ ]. i v
i bài toán ngi du lch, khi tin hành tìm kim li gii, chúng ta s/ phân tp các hành trình thành 2 tp con: Tp g(m nhng hành trình có cha cnh (i,j) và tp còn li g(m nhng hành trình không cha cnh (i,j). Tr
c tiên,  cho vi c phân nhánh  c d dàng, ta cn phi rút gn ma trn trng s, do t%ng chi phí ca hành trình s/ cha úng mt phn t ca mi dòng và mi ct nên khi cng hay tr* c dòng hay ct cho mt s
thì t%ng trng s c tt c các hành trình s/ gim i
. Do ó, ta có th rút gn ma trn trng s sao cho trên mi dòng và ct u có ít nht mt s 0, (ng thi, t%ng ca các s
s/ là cn d
i ca tt c các hành trình. i v
i tp phân hoch cha cnh i,j. Do i,j thuc hành trình này nên ta phi xoá dòng i ct j do không th có cnh khác t* i i ra và t* i vào j ngoài cnh i,j, ngoài ra c.ng t C[j][i] b!ng - do ã chn cnh C[i][j]. i v
i tp phân hoch không cha cnh i,j ta ch' vi c t C[i][j]= - Ta ln l t tìm cn d
i ca 2 ma trn này, sao ó chn phân hoch tip trên ma trn có cn d
i nh" hn. Do ó, khi chn cnh  phân nhánh ta phi chn làm sao  cn d
i ca nhánh không cha i,j là lón nht,  tìm cnh ó ta chn s 0 trong ma trn  khi thay nó b!ng - s/ cho ta t%ng h!ng s rút gn theo cnh và dòng l
n nht. Mt lu ý na là khi ã chn cnh i,j và j,k thì ta phi ngn chn không cho qua cnh k,i  không hình thành các chu trình con. Ví d: gii bài toán ngi du lch v
i ma trn chi phí nh sau Tp tt c các hành trình Hành trình cha i,j Hành trình không cha i,j 9 1 2 3 4 5 1 - 8 5 22 11 2 4 - 9 17 27 3 15 7 - 12 35 4 5 27 17 - 29 5 23 21 19 7 - u tiên s/ th c hi n vi c rút gn ma trn b!ng cách tr* ln l t mi dòng v
i s nh" nht trên dòng ó hoc tr* mi ct v
i s nh" nht trên ct ó sao cho trên mi dòng hoc mi ct u có ít nht mt s 0. 1 2 3 4 5 1 - 3 0 17 6 2 0 - 5 13 23 3 8 0 - 5 28 4 0 22 12 - 24 5 16 14 12 0 - Ta có cn d
i ca ma trn này là 5+4+7+5+7=28. Ta chn cnh  phân nhánh là cnh (5,4), khi ó, ma trn ca tp phân hoch cha cnh (5,4) và tp phân hoch không cha cnh (5,4) ln l t là: 1 2 3 5 1 - 3 0 6 2 0 - 5 23 3 8 0 - 28 4 0 22 12 - Cn d
i là 28+6=34 Cn d
i là 23+28=51 Ta tip tc rút gn và phân nhánh tp phân hoch cha cnh (5,4) 1 2 3 5 1 - 3 0 0 2 0 - 5 17 3 8 0 - 22 4 0 22 12 - 5 4 7 5 7 1 2 3 4 5 1 - 3 0 17 6 2 0 - 5 13 23 3 8 0 - 5 28 4 0 22 12 - 24 5 16 14 12 - - 1 2 3 5 1 - 3 0 0 2 0 - 5 17 3 8 0 - 22 4 0 22 12 - 10 Cn d
i ca tp phân hoch không cha (1,5) là 17+34=51 Chn cnh (1,5) thì cn d
i ca tp phân hoch cha (5,4) và cha (1,5) là 34. (ng thi phi ngn vi c hình thành chu trình con b!ng cách cho C[4][1]= -. Tip tc rút gn, ta li  c ma trn sau có cn d
i là 12+34=46 Phân nhánh cnh (3,2) ta  c ma trn 2x2 ca tp phân hoch cha cnh (5,4), (1,5), (3,2) có cn d
i là 46 Cui cùng ta thêm vào hành trình 2 cnh cui là (2,1) và (4,3). Nh vy, các cnh ca hành trình tìm  c là (5,4), (1,5), (3,2), (2,1), (4,3) và chu trình cn tìm là 1
5
4
3
2
1 v
i chi phí là 7+11+7+4+17=46. 1 2 3 2 0 - 5 3 8 0 - 4 - 22 12 1 2 3 2 0 - 0 3 8 0 - 4 - 15 0 1 2 3 2 0 - 0 3 8 0 - 4 - 15 0 1 3 2 0 - 4 - 0