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

Nội dung 1/Giới thiệu lịch sử của bài toán người du lịch 2/Mô tả chi tiết bài toán 3/Thuật giải chính xác 4/Các thuật giải gần đúng (Heuristic) +Thuật giải tham lam +Thuật toán nhánh cận

pdf10 trang | Chia sẻ: lvcdongnoi | Ngày: 03/07/2013 | Lượt xem: 9927 | Lượt tải: 11download
Bạn đang xem nội dung tài liệu Bài toán người du lịch và các thuật giải, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Trng i hc Khoa hc T nhiên TP.HCM Khoa CNTT Lp 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 ngi du lch và các thu t gi i Giáo viên lý thuyt: Dng Anh c Giáo viên hng d n th c hành:  ng Nguy n c Tin, Nguy n Huy Khánh 2 Ni dung  án 1/Gii 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/Gii 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 c p 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 vi 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 gii 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. Vi các phng pháp mi h ã gii mt trng h p vi 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 ln 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 hng thì dùng ( th vô hng, ng c li ta s dng ( th có hng. Trong ví d trên, ta gi nh ng i t* 2 hng 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 ln 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 m t 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 ho c 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 vi ôtô m c dù khong cách di chuyn có th ln hn. 3/Thu t 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=+- ho c min = m* trng s ca cnh ln 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. -L p 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 vi '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 i1 vào Sum và gán min b!ng Min(Sum, min). Sum – = cnh i1. L p 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 l p 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 l p. 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à 12341 vi  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 thu t gi i g n úng (Heuristic) 4.1/Thut gii tham lam (thut gii láng gi ng g n nh t) 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 bc, ta chn con ng (cnh) ni vi thành ph ('nh) gn nht vi 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 vi 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à 134521 vi chi phí là 10 so vi 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]; //Lu 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; //Lu li tr ng s ca cnh nh nh t for(int i = 0;i < n; i++) //ch n 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 cha // là 1 nu cha thm, 0 nu thm ri { min = a[id][i];//Cp nht li tr ng 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 tr ng 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 vi 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 di ây, chúng ta s/ tìm li gii d a trên ma trn trng s C[ ][ ]. i vi 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). Trc 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 di ca tt c các hành trình. i vi 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 vi 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 di ca 2 ma trn này, sao ó chn phân hoch tip trên ma trn có cn di nh" hn. Do ó, khi chn cnh  phân nhánh ta phi chn làm sao  cn di 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 ln nht. Mt lu ý na là khi ã chn cnh i,j và j,k thì ta phi ngn ch n 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 vi 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 vi s nh" nht trên dòng ó ho c tr* mi ct vi s nh" nht trên ct ó sao cho trên mi dòng ho c 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 di 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 di là 28+6=34 Cn di 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 di ca tp phân hoch không cha (1,5) là 17+34=51 Chn cnh (1,5) thì cn di 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 di 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 di 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à 154321 vi 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

Các file đính kèm theo tài liệu này:

  • pdfBài toán người du lịch.pdf
Luận văn liên quan