旅游路线设计解题报告

1、旅游路线设计解题报告问题分析此题很明显是一个求哈密顿路的问题，但关键却在求任两景点的最短距离。如果平平常常的就用O(n2)的dijstra算法的话，超时几乎是必然的。只有降低求最短路算法的时间复杂度，才是解决问题的唯一途径。解题思路要将时间复杂度降至O(n)显然是不可能的，看来只有往O(nlogn)上考虑了。这时便会发现，这种时间复杂度的降低程度，竟与排序中的时间复杂度由O(n2)降为O(nlogn)极度相似。因而由此产生联想：是否可以用排序中类似的方法来降低本题的时间复杂度呢？排序中时间复杂度为O(nlogn)的方法较熟悉的共有三种：快速排序、堆排序、分治合并排序。通过分析这三种排序方法可以

2、发现，堆排序的方法在本题中是可以借鉴的。在O(n2)的算法中，共有两重循环，其中外循环是不可能减少的，而内循环中的选择最小值(从未确定到达时间的区域中选择目前到达时间最早的区域)的操作，是可以用堆来减少运算的。假设当前到各区域的时间已经建成一个堆，那么选择最短时间就与堆排序中每次选出最小数的过程完全相同，只需要logn的时间。然而，虽然选择所需时间降至了nlongn，但却增加了改变到达其它区域时间的麻烦。一是各区域在堆中的位置不确定，二是要改变堆中非树根结点的权值，会使堆不再成为堆。解决第一个问题十分容易，只要加一个数组进行标记。解决第二个问题看来稍有些麻烦，但只要按照类似进行堆化的方法，将进

3、行堆化中从上至下变为从下至上即可，每次将当前结点的权值与其父结点比较，若大则结束，若小则先进行互换，将该结点的位置移到其父结点的位置上，然后再继续该比较的过程。这样的比较结束后，整棵树仍会保持堆的性质。因为每次最多改变三个区域的费用，故该过程只需3nlongn的时间。这样，便将求最短路径的时间复杂度降为了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堆中结点类型，w为时间，x、y对应结点

4、表示区域的坐标 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;区域地图 reached:array1.10 of boolean;是否到达过的标记 c:array0.10 of point;记录景点位置 dist:array0.10,0.10 of longint;来往任两景点需要的时间 pos:array0.101,0.101 of word;每个区域对应结点在堆中的位置 h:arr;堆 n,m,p:byte

5、; t:word;当前堆中的结点个数 min:longint;最短时间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);交换结点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);由上至下进行堆化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);由下至上进行堆化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个景点到其它景点的时间var h1,h2,i,j,num:longint;num为已确定最短到达时间的区域个数begin h10001.w:=maxlongint; for i:=1 to n do for j:=1 to m do posi,j:=10001

8、; 设定到达时间为+的区域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; 设标志以避免移到地图外 h1.w:=0;h1.x:=cno.x;h1.y:=cno.y; poscno.x,cno.y:=1;t:=1;num:=0;设起点 repeat for i:=1 to p do if (ci.x=h1.x) and (ci.y=h1.y) then distno,i:=h1.w; 是否到达了某景点 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 判断堆中是否需要加入新结点 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个景点是否到达过 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;将起点也作为一个景点 fo