旅游路線設(shè)計(jì)解題報(bào)告

1、旅游路線設(shè)計(jì)解題報(bào)告問題分析此題很明顯是一個(gè)求哈密頓路的問題，但關(guān)鍵卻在求任兩景點(diǎn)的最短距離。如果平平常常的就用O(n2)的dijstra算法的話，超時(shí)幾乎是必然的。只有降低求最短路算法的時(shí)間復(fù)雜度，才是解決問題的唯一途徑。解題思路要將時(shí)間復(fù)雜度降至O(n)顯然是不可能的，看來只有往O(nlogn)上考慮了。這時(shí)便會(huì)發(fā)現(xiàn)，這種時(shí)間復(fù)雜度的降低程度，竟與排序中的時(shí)間復(fù)雜度由O(n2)降為O(nlogn)極度相似。因而由此產(chǎn)生聯(lián)想：是否可以用排序中類似的方法來降低本題的時(shí)間復(fù)雜度呢？排序中時(shí)間復(fù)雜度為O(nlogn)的方法較熟悉的共有三種：快速排序、堆排序、分治合并排序。通過分析這三種排序方法可以

2、發(fā)現(xiàn)，堆排序的方法在本題中是可以借鑒的。在O(n2)的算法中，共有兩重循環(huán)，其中外循環(huán)是不可能減少的，而內(nèi)循環(huán)中的選擇最小值(從未確定到達(dá)時(shí)間的區(qū)域中選擇目前到達(dá)時(shí)間最早的區(qū)域)的操作，是可以用堆來減少運(yùn)算的。假設(shè)當(dāng)前到各區(qū)域的時(shí)間已經(jīng)建成一個(gè)堆，那么選擇最短時(shí)間就與堆排序中每次選出最小數(shù)的過程完全相同，只需要logn的時(shí)間。然而，雖然選擇所需時(shí)間降至了nlongn，但卻增加了改變到達(dá)其它區(qū)域時(shí)間的麻煩。一是各區(qū)域在堆中的位置不確定，二是要改變堆中非樹根結(jié)點(diǎn)的權(quán)值，會(huì)使堆不再成為堆。解決第一個(gè)問題十分容易，只要加一個(gè)數(shù)組進(jìn)行標(biāo)記。解決第二個(gè)問題看來稍有些麻煩，但只要按照類似進(jìn)行堆化的方法，將進(jìn)

3、行堆化中從上至下變?yōu)閺南轮辽霞纯桑看螌?dāng)前結(jié)點(diǎn)的權(quán)值與其父結(jié)點(diǎn)比較，若大則結(jié)束，若小則先進(jìn)行互換，將該結(jié)點(diǎn)的位置移到其父結(jié)點(diǎn)的位置上，然后再繼續(xù)該比較的過程。這樣的比較結(jié)束后，整棵樹仍會(huì)保持堆的性質(zhì)。因?yàn)槊看巫疃喔淖內(nèi)齻€(gè)區(qū)域的費(fèi)用，故該過程只需3nlongn的時(shí)間。這樣，便將求最短路徑的時(shí)間復(fù)雜度降為了O(nlongn)。程序const st1=input.txt;輸入文件名 st2=output.txt;輸出文件名 b:array1.4,1.2 of shortint=(1,0),(0,1),(-1,0),(0,-1);type node=record堆中結(jié)點(diǎn)類型，w為時(shí)間，x、y對應(yīng)結(jié)點(diǎn)

4、表示區(qū)域的坐標(biāo) w:longint; x,y:byte; end; arr=array0.10001 of node; point=record x,y:integer; end;var a:array0.101,0.101 of integer;區(qū)域地圖 reached:array1.10 of boolean;是否到達(dá)過的標(biāo)記 c:array0.10 of point;記錄景點(diǎn)位置 dist:array0.10,0.10 of longint;來往任兩景點(diǎn)需要的時(shí)間 pos:array0.101,0.101 of word;每個(gè)區(qū)域?qū)?yīng)結(jié)點(diǎn)在堆中的位置 h:arr;堆 n,m,p:byte

5、; t:word;當(dāng)前堆中的結(jié)點(diǎn)個(gè)數(shù) min:longint;最短時(shí)間procedure readp;讀入過程var f:text; i,j:byte;begin assign(f,st1);reset(f); readln(f,n,m); for i:=1 to n do for j:=1 to m do read(f,ai,j); readln(f,p); for i:=1 to p do readln(f,ci.x,ci.y); close(f);end;procedure swap(i,j:word);交換結(jié)點(diǎn)var k:node;begin k:=hi;hi:=hj;hj:=k; p

6、oshi.x,hi.y:=i; poshj.x,hj.y:=j;end;procedure heap1(i:word);由上至下進(jìn)行堆化begin if (i*2=t) and (hi*2.whi.w) then begin swap(i,i*2); heap1(i*2); end else if i*2+1=t then if hi*2.whi*2+1.w then begin if hi*2.whi.w then begin swap(i,i*2); heap1(i*2); end end else if hi*2+1.whi.w then begin swap(i,i*2+1); hea

7、p1(i*2+1); end;end;procedure heap2(i:word);由下至上進(jìn)行堆化begin if (i1) and (hi div 2.whi.w) then begin swap(i div 2,i); heap2(i div 2); end;end;procedure find(no:integer);尋找第no個(gè)景點(diǎn)到其它景點(diǎn)的時(shí)間var h1,h2,i,j,num:longint;num為已確定最短到達(dá)時(shí)間的區(qū)域個(gè)數(shù)begin h10001.w:=maxlongint; for i:=1 to n do for j:=1 to m do posi,j:=10001

8、; 設(shè)定到達(dá)時(shí)間為+的區(qū)域h0.w:=0; for i:=1 to n do begin posi,0:=0;posi,m+1:=0; end; for i:=1 to m do begin pos0,i:=0;posn+1,i:=0; end; 設(shè)標(biāo)志以避免移到地圖外 h1.w:=0;h1.x:=cno.x;h1.y:=cno.y; poscno.x,cno.y:=1;t:=1;num:=0;設(shè)起點(diǎn) repeat for i:=1 to p do if (ci.x=h1.x) and (ci.y=h1.y) then distno,i:=h1.w; 是否到達(dá)了某景點(diǎn) inc(num); fo

9、r i:=1 to 4 do begin h1:=h1.x+bi,1;h2:=h1.y+bi,2; if hposh1,h2.w=maxlongint then begin 判斷堆中是否需要加入新結(jié)點(diǎn) inc(t); with ht do begin w:=h1.w+sqr(ah1.x,h1.y-ah1,h2)+1; x:=h1;y:=h2; posx,y:=t; end; heap2(t); end elseif h1.w+sqr(ah1.x,h1.y-ah1,h2)+1 =min then exit; if i=p+1 then begin min:=t;exit; end; for j:=1 to p do if not reachedj then begin判斷第j個(gè)景點(diǎn)是否到達(dá)過 reachedj:=true; try(i+1,j,t+distlast,j); reachedj:=false; end;end;procedure main;求最佳路線var i:integer; f:text;begin new(h); c0.x:=1;c0.y:=1;將起點(diǎn)也作為一個(gè)景點(diǎn) fo