西安電子科技大學(xué)算法上機(jī)報告

1、爰氯西安電子科技大學(xué)（2018年度）算法分析實(shí)驗報告實(shí)驗名稱：滲透實(shí)驗班級：1603012姓名：朱斌學(xué)號：16030120032實(shí)驗一：滲透問題（Percolation ）一、實(shí)驗題目使用合并-查找（union-find ）數(shù)據(jù)結(jié)構(gòu)，編寫程序通過蒙特卡羅模擬（ Monte Carlo simulation）來估計滲透閾值的值。給定由隨機(jī)分布的絕緣材料和金屬材料構(gòu)成的組合系統(tǒng)：金屬材料占多大比例才能使組合系統(tǒng)成為電導(dǎo)體？給定一個表面有水的多孔滲水地形（或下面有油），水將在什么條件下能夠通過底部排出（或油滲透到表面）？科學(xué)家們已經(jīng)定義了一個稱為滲透（percolation的抽象過程來模擬這種情況。

2、模型：我們使用N x N網(wǎng)格點(diǎn)來模型一個滲透系統(tǒng)。每個格點(diǎn)或是openly點(diǎn)或是blocked格點(diǎn)。 一個full site是一個opern點(diǎn)，它可以通過一連串的鄰近（左，右，上，下）oper點(diǎn)連通到頂行的一個 opern點(diǎn)。如果在底行中有一個 full site格點(diǎn)，則稱系統(tǒng)是滲透的。（對 于絕緣/金屬材料白例子，oper點(diǎn)對應(yīng)于金屬材料，滲透系統(tǒng)有一條從頂行到底行的金屬 路徑，且full sites格點(diǎn)導(dǎo)電。對于多孔物質(zhì)示例，opern點(diǎn)對應(yīng)于空格，水可能流過，從而滲透系統(tǒng)使水充滿 opern點(diǎn)，自頂向下流動。）BEdo畫 nci percolateopen s加 connected to

3、 topno open H能 conneaed to mp問題： 在一個著名的科學(xué)問題中，研究人員對以下問題感興趣：如果將格點(diǎn)以空置概率p獨(dú)立地設(shè)置為opern點(diǎn)（因此以概率 1-p被設(shè)置為blocke略點(diǎn)），系統(tǒng)滲透的概率是多少?當(dāng)p= 0時，系統(tǒng)不會滲出；當(dāng)p=1時，系統(tǒng)滲透。 下圖顯示了 20X20隨機(jī)網(wǎng)格和100X100隨機(jī)網(wǎng)格的格點(diǎn)空置概率 p與滲濾概率。percohuionprobabilitysite vacancy probability psite vacancy probability p當(dāng)N足夠大時，存在閾值 p*,使得當(dāng)p 爐，隨機(jī)N x N網(wǎng)格幾乎不會滲透，并且當(dāng) p

4、p*時，隨機(jī)NMN網(wǎng)格幾乎總是滲透。尚未得出用于確定滲濾閾值p*的數(shù)學(xué)解。你的任務(wù)是編寫一個計算機(jī)程序來估計p*opublic Percolation(int N)public void open(int i, int j)public boolean isOpen(int i, int j)public boolean isFull(int i, int j)public boolean percolates()public static void main(String口 args)Percolation數(shù)據(jù)類型：模型化一個Percolation系統(tǒng)，創(chuàng)建含有以下 API的數(shù)據(jù)類型Perc

5、olation。 public class Percolation / create N-by-N grid, with all sites blocked/ open site (row i, column j) if it is not already/ is site (row i, column j) open?/ is site (row i, column j) full?/ does the system percolate?/ test client, optional 約定行i列j下標(biāo)在1和N之間,其中(1, 1)為左上格點(diǎn)位置：如果open(), isOpen(), or

6、isFull() 不在這個規(guī)定的范圍，則拋出IndexOutOfBoundsException例外。如果N 0構(gòu)造函數(shù)應(yīng)該拋出川egalArgumentException例外。構(gòu)造函數(shù)應(yīng)該與N2成正比。所有方法應(yīng)該為常量時間加上常量次調(diào)用合并 -查找方法union(), find(), connected(), and count()。蒙特卡洛模擬(Monte Carlo simulation ).要估計滲透閾值，考慮以下計算實(shí)驗：初始化所有格點(diǎn)為 blocke d重復(fù)以下操作直到系統(tǒng)滲出：o 在所有blocked勺格點(diǎn)之間隨機(jī)均勻選擇一個格點(diǎn)(row i, column j)。o 設(shè)置這個格

7、點(diǎn)(row i, column j)為 oper點(diǎn)。 opern點(diǎn)的比例提供了系統(tǒng)滲透時滲透閾值的一個估計。例如，如果在20X20的網(wǎng)格中，根據(jù)以下快照的opern點(diǎn)數(shù)，那么對滲濾閾值的估計是204/400 = 0.51 ,因為當(dāng)?shù)?04個格點(diǎn)被ope的系統(tǒng)滲透。50 open sites100 open sites150 open sites204 open sites通過重復(fù)該計算實(shí)驗 T次并對結(jié)果求平均值，我們獲得了更準(zhǔn)確的滲濾閾值估計。令xt是第t次計算實(shí)驗中ope格點(diǎn)所占比例。樣本均值任提供滲濾閾值的一個估計值；樣本標(biāo)準(zhǔn)差;測量閾值的靈敏性。假設(shè)T足夠大(仞如至少 30),以下為滲濾

8、閾值提供 95%置信區(qū)間:N -PercolationStats 來執(zhí)行我們創(chuàng)建數(shù)據(jù)類型public class PercolationStats public PercolationStats(int N, int T) on an N-by-N gridpublic double mean()public double stddev()public double confidenceLo()public double confidenceHi()public static void main(String口 args)crcr-R系列計算實(shí)驗，包含以下 API。/ perform T in

9、dependent computational experiments/ sample mean of percolation threshold/ sample standard deviation of percolation threshold/ returns lower bound of the 95% confidence interval/ returns upper bound of the 95% confidence interval/ test client, described below在 NW 0或 T 0時，構(gòu)造函數(shù)應(yīng)該拋出java.lang.IllegalArg

10、umentException 例外。此外，還包括一個 main()方法，它取兩個命令行參數(shù) N和T,在N x N網(wǎng)格上進(jìn)行T次獨(dú) 立的計算實(shí)驗(上面討論)，并打印出均值 N、標(biāo)準(zhǔn)差仃和95%滲透閾值的置信區(qū)間。使用標(biāo)準(zhǔn)庫中的標(biāo)準(zhǔn)隨機(jī)數(shù)生成隨機(jī)數(shù)；使用標(biāo)準(zhǔn)統(tǒng)計庫來計算樣本均值和標(biāo)準(zhǔn)差。Example values after creating PercolationStats(200, 100)mean()stddev()confidenceLow() confidenceHigh()=0.5929934999999997=0.00876990421552567=0.59127459877375

11、67=0.5947124012262428Example values after creating PercolationStats(200, 100)mean() stddev() confidenceLow() confidenceHigh()=0.592877=0.009990523717073799=0.5909188573514536=0.5948351426485464Example values after creating PercolationStats(2, 100000)mean()=0.6669475stddev()=0.11775205263262094confid

12、enceLow()=0.666217665216461confidenceHigh()=0.6676773347835391運(yùn)行時間和內(nèi)存占用分析。使用 quick-fine法(QuickFindUF.java from algs4.jar)實(shí)現(xiàn) Percolation 數(shù)據(jù)類型。進(jìn)行實(shí) 驗表明當(dāng)N加倍時對運(yùn)行時間的影響；使用近似表示法，給出在計算機(jī)上的總時間，它是 輸入N和T的函數(shù)表達(dá)式。使用 weighted quick-un輯該(WeightedQuickUnionUF.java from algs4.jar)實(shí)現(xiàn) Percolation數(shù)據(jù)類型。進(jìn)行實(shí)驗表明當(dāng)N加倍時對運(yùn)行時間的影響；

13、使用近似表示法，給出在計算機(jī)上的總時間，它是輸入 N和T的函數(shù)表達(dá)式。二、算法設(shè)計程序要求實(shí)現(xiàn)對一個 NxN矩陣的連通性判斷問題，則可以使用quick-find算法和加權(quán) quick-union算法來實(shí)現(xiàn)，因為算法中的數(shù)組是一維的，所以首要解決的問題就是將NxN矩陣中的點(diǎn)經(jīng)過變換轉(zhuǎn)換到一維數(shù)組中對應(yīng)的位置來完成之后的算法求解。將它們在連通分量數(shù)組中的編號依次設(shè)置為0NxN-1。為了之后檢驗連通性的問題，有一個非常巧妙的方法。抽象出在矩陣的頂部有一個單獨(dú)的注水口，它和第一行的所有點(diǎn)都是連通的，在矩陣的底部有一個出水口，它和最后一行的所有點(diǎn)是連通的，并分別將注水口和出水口在連通分量數(shù)組中的編號設(shè)為

14、NxN和NxN+1。按照題目的要求每次隨機(jī)打開矩陣中的一個點(diǎn)，然后判斷與它鄰近的點(diǎn)(上下左右)是否已經(jīng)被打開，若已經(jīng)打開就將它們連 接起來。那么每次打開一個新的結(jié)點(diǎn)之后檢驗連通性只需要檢驗注水口和出水口是否連通即可。具體設(shè)計:Percolation設(shè)計Percolation類，分別使用 quick-find和weight quick-union算法進(jìn)行合并。類中設(shè)計open方法打開一個點(diǎn)，并將該點(diǎn)與其它相鄰的點(diǎn)合并。classprivate int matrixLength;/網(wǎng)格大小private boolean matrix;/記錄方格是否打開數(shù)組private QuickFindUF q

15、u; /合并查找類變量/ 或者：private WeightedQuickUnionUF wqu;private int virtualTop; /注水口private int virtualbottom; /出水口public Percolation(int N)if (N = 0) throw new IllegalArgumentException(length must be positive); )matrixLength = N;virtualTop = matrixLength * matrixLength;virtualbottom = matrixLength * matri

16、xLength + 1;matrix = new booleanN * N;qu = new QuickFindUF(N * N + 2);/檢查邊界private void checkValidIndex(int row,int col)if(row = 0 | row matrixLength)thrownew IndexOutOfBoundsException(row index out of bounds);if(col matrixLength)thrownew IndexOutOfBoundsException(col index out of bounds);)/計算點(diǎn)(row

17、i, col j)的一維坐標(biāo) private int rowCol to real(int row,int col)return (row - 1) * matrixLength + col - 1;)/打開一個點(diǎn)public void open(int row,int col)checkValidIndex(row, col);/檢查邊界int real = rowCol_to_real(row, col); /轉(zhuǎn)換成一維坐標(biāo)if (matrixreal) return;/如果已經(jīng)是打開的，就直接返回if (row = 1) /如果是第一行的情況，那么讓他連接top的虛擬點(diǎn)qu.union(

18、real, virtualTop);if (row = matrixLength) /如果是最后一行的情況，那么讓他連接bottom的虛擬點(diǎn)qu.union(real, virtualbottom);int neighbor; /記錄相鄰點(diǎn)的坐標(biāo)-6 -/判斷周圍的四個點(diǎn)是否是打開的，如果是的話就連接if (row 1) / upneighbor = rowCol to real(row - 1, col);if (matrixneighbor) qu.union(real, neighbor);if (row 1) / leftneighbor = rowCol to real(row, c

19、ol - 1);if (matrixneighbor) qu.union(real, neighbor);if (col matrixLength) / rightneighbor = rowCol to real(row, col + 1);if (matrixneighbor) qu.union(real, neighbor);public boolean isOpen(int row,int col) /判斷這個點(diǎn)是不是已打開的checkValidIndex(row, col);return matrixrowCol to real(row, col);public boolean is

20、Percolated()/判斷網(wǎng)格是否滲透return qu.isConnect(virtualTop, virtualbottom);QuickFindUF算法核心：每個點(diǎn)所在連通分量記錄在以該點(diǎn)為下標(biāo)的數(shù)組中，And方法的復(fù)雜度低，但合并時要遍歷數(shù)組中的所有點(diǎn)，將其中一個連通分量中所有點(diǎn)的連通分量記由標(biāo)號找該點(diǎn)所在連通分量錄改為另一個連通分量，union方法的復(fù)雜度高。public int find(int p) /return idp;public void union(int p,int q) /合并兩個連通分量int pID=find(p);int qID=find(q);if(pI

21、D=qID)return;)for(int i=0;iid.length;i+) /遍歷所有點(diǎn)，將與p點(diǎn)在同一連通分量的點(diǎn)合并到q所在的連通分量if(idi=pID) idi=qID;count-;WeightedQuickUnionUF算法核心：以每個點(diǎn)為下標(biāo)的數(shù)組中記錄該點(diǎn)的父親節(jié)點(diǎn)，由父親節(jié)點(diǎn)找到根節(jié)點(diǎn)，根節(jié)點(diǎn)為該連通分量的標(biāo)記；增加size數(shù)組記錄每個連通分量的大小，在union時比較兩個連通分量的size的大小，將小連通分量連接到大連通分量上，以此來減小樹的高度減少查找根節(jié)點(diǎn)的時間。public int find(int p) /復(fù)雜度為兩倍的樹的高度h即2hwhile(p!=idp

22、)p=idp;)return p;public void union(int p,int q)/不計算find的情況下union的算法復(fù)雜度為1int i=find(p);int j=find(q);if(i=j)return;if(sziszj) idi=j;)三、實(shí)驗結(jié)果及分析QuickFindUF 合并查找:Pl噠dse ertr N nd T : 100 50The incon of percolationStats is 0,591978The stddev of percolationStats is 0.616905627650075382Th，匚口ndidgne interva

23、ls of p*rcolationSt is 0.5B726982A?201 0.596686175779896 Thg tiifiQ of the prog rami is IJWriis通過以上數(shù)據(jù)分析：N 一定時，運(yùn)行時間與T成正比；T 一定時，運(yùn)行時間與N”成正比；所以用quick-find 方法解決滲透問題的時間成長量級為：44 TWeightedQuickUnionUF 算法： wnter N jnd T :rh hi#an of p#rcolftliDnStatf it 白一%74砧時的密）0001The stddflv of percolsticnStflts 狂 O,6163

24、67267066475The ccndidcnca inUnvuli of parcel at icn Sti e. 5929156753399d5S , 3.60195632666&056JTFw time of tbv prugrjrr it iidni*PJ.wds例 vntiat1 N nd r :100 1 的The of percolatioHStots is57263 1*999999999The Etddeu of porcoLutionStJt 工5 e.ei617l6032350ei54Th curdidncff intrvdl V 哼F式4七1ksiit 我 5&融電35

25、657659397 , 0.595%則M2M箕心 Th* tim* nf th* prcgr*rn if J05hswnlr N dnd I : 2 翻Th* of p4rcaldtiuStdt ii &.S93103999599997TM 廿.曰1日211902358123335TM tondidentc intcrvdii. of pureLdion&htE i& 色 5州“8g754優(yōu)3期,6.593293922593669 The tig of th電 pgrjim is h/ismsN 一定時，運(yùn)行時間與T成正比；T 一定時，運(yùn)行時間與lgN2成正比；所以用quick-find 方法

26、解決滲透問題的時間成長量級為：lgN 2t兩種算法均得出滲透問題的閾值約為0.59。-10 -(二)幾種排序算法的實(shí)驗性能比較一、實(shí)驗題目實(shí)現(xiàn)插入排序(Insertion Sort, IS),自頂向下歸并排序 (Top-down Mergesort,TDM ), 自底向上歸并排序 (Bottom-up Mergesort, BUM),隨機(jī)快速排序 (Random Quicksort, RQ), Dijkstra 3-路劃分快速排序(Quicksort with Dijkstra 3-way Partition , QD3P )。在你的計算機(jī)上 針對不同輸入規(guī)模數(shù)據(jù)進(jìn)行實(shí)驗，對比上述排序算法的時

27、間及空間占用性能。要求對于每次輸入運(yùn)行10次，記錄每次時間，取平均值。二、算法設(shè)計.每種排序算法均實(shí)現(xiàn)下列模板中的各個方法:public class Example public static void sort(Comparable a) private static boolean less(Comparable v,Comparable w) return pareTo(w)0;private static void exch(Comparable口 a,int i,int j) Comparable t=ai;ai=aj;aj=t;private static void show(Co

28、mparable口 a) for(int i=0;ia.length;i+)System.out.println(ai+);System.out.println();public static boolean isSorted(Comparable口 a) for(int i=0;ia.length;i+)if(less(ai,ai-1) return false;return true;參與排序的數(shù)據(jù)均實(shí)現(xiàn)Comparable接口。.插入排序算法:static voidint N=a.length;for(int i=1;i0&exch (a,j,j-1);)從i=0開始依次取i,將ai插入

29、到已經(jīng)部分有序的a0ai-1的合適的位置。.自頂向下排序算法：private static void sort(Comparable口 a,int lo,int hi) if(hi=lo) return;int mid=lo+(hi-lo)/2;sort (a,lo,mid);sort (a,mid+1,hi);merge (a,lo,mid,hi);)在sort方法中遞歸地調(diào)用sort方法將大數(shù)組二分為兩個小數(shù)組直至兩個小數(shù)組大小為1 ,再在遞歸返回時調(diào)用merge方法將已經(jīng)有序的兩個小數(shù)組合并成一個較大的有序數(shù)組。public static void merge(Comparable口 a

30、,int lo,int mid,int hi) int i=lo,j=mid+1;for(int k=lo;k=hi;k+)aux k=ak;for(int k=lo;kmid)ak=aux j+;else if(jhi)ak=aux i+;else if( less (aux j, aux i) ak= aux j+;elseak=aux i+;merge方法不斷從兩個數(shù)組中取出數(shù)據(jù)進(jìn)行比較，較小的數(shù)據(jù)插入到輔助數(shù)組中并取該較小數(shù)據(jù)所在數(shù)組的下一個數(shù)據(jù)繼續(xù)比較，當(dāng)有某個數(shù)組中的數(shù)據(jù)取完時則將另一個數(shù)組中剩下的數(shù)據(jù)全部放到輔助數(shù)組中，完成兩個有序數(shù)組合為一個有序數(shù)組的排序。4.自底向上排序算法

31、:public static void sort(Comparable a) int N=a.length;aux =new ComparableN;for(int sz=1;szN;sz=sz*2)min (lo+sz*2-1, N-1);for(int lo=0;loN-sz;lo+=sz*2)merge (a,lo,lo+sz-1,Math.-12 -）從數(shù)組大小size為1開始將相鄰的大小為 size的兩個數(shù)組用 merge方法歸并排序， 直至輔助數(shù)組中的數(shù)排完，輔助數(shù)組成為每2*size 部分有序的數(shù)組；增大數(shù)組大小size為上一次歸并的兩個數(shù)組大小size的兩倍，繼續(xù)用merge方

32、法將相鄰的大小為 size的數(shù)組排序；增大size重復(fù)上一步直至將整個輔助數(shù)組排成有序的。merge方法同上。5,隨機(jī)快速排序算法：private static void sort(Comparable a,int lo,int hi) if(hi=j)break;exch (a,i,j);exch (a,lo,j);return j;Partition方法以傳入的數(shù)組的第一個數(shù)據(jù)為切分?jǐn)?shù)據(jù)，比切分?jǐn)?shù)據(jù)小的數(shù)據(jù)全部移動到切分?jǐn)?shù)據(jù)左邊，比切分?jǐn)?shù)據(jù)大的全部移動到切分?jǐn)?shù)據(jù)右邊，將切分?jǐn)?shù)據(jù)移動到正確的位置并返回1位置j。sort方法調(diào)用Partition方法得到切分?jǐn)?shù)據(jù)aj,再遞歸地對aj左右兩邊的數(shù)

33、組調(diào)用sort方法直至傳入sort方法的數(shù)組大小為1 （大小為1的數(shù)組恒有序），整個數(shù)組排序完 成。-13 -1 91 b i nj avaw. exe (201 9 目三、實(shí)驗結(jié)果及分析 SortCorn pare -Java Application G :JAVAjre 1.S.0_1000工S已排序15執(zhí)行時間:13.053sTDM已排序TDM執(zhí)行時間:0.037sBUM已排序BUM執(zhí)行時間：0.062sRQ已排序RQ執(zhí)行日寸間士 0.042sQD3P已排序QD3P執(zhí)行時間：0.054s-termi n a ted &ortCompare Jsws Application G:JAVAj

34、 rel .8.0=191 binjavaw.eKe-120195600IS已排序工S執(zhí)行時fib 12.908sTDM已排序TDM執(zhí)行時間：0.0345BUM已排序BUM執(zhí)行時間:0.031sRQ已排序RQ執(zhí)行時間:0.046sQD3P已排序QD3P執(zhí)行時間：0.041s SortCompare Java Application G:JAVAjre1.8,0_1 9IXbiinSjavaw.exe (201 91000015已排序15執(zhí)行E寸間：13.313sTDM已排序TDM執(zhí)行時間：0.042sBUM已排序BUM執(zhí)行時間:0.04sRQ已排序RQ執(zhí)行時間：0.952sQD3P已排序3P執(zhí)

35、行時間;0.053s由以上實(shí)驗結(jié)果可以看出插入排序花的時間最多，其他四種排序算法時間開銷相差不大,比插入排序快很多，隨機(jī)快排排序最快。-14 -（三）地圖路由（Map Routing）一、實(shí)驗題目實(shí)現(xiàn)經(jīng)典的 Dijkstra最短路徑算法，并對其進(jìn)行優(yōu)化。這種算法廣泛應(yīng)用于地理信息系統(tǒng)（GIS）,包括MapQuest和基于GPS的汽車導(dǎo)航系統(tǒng)。地圖：本次實(shí)驗對象是圖 map或graphs其中頂點(diǎn)為平面上的點(diǎn)，這些點(diǎn)由權(quán)值為歐氏 距離的邊相連成圖?？蓪㈨旤c(diǎn)視為城市，將邊視為相連的道路。為了在文件中表示地圖，我們列出了頂點(diǎn)數(shù)和邊數(shù)，然后列出頂點(diǎn)（索引后跟其x和y坐標(biāo)），然后列出邊（頂點(diǎn)對）， 最后列

36、出源點(diǎn)和匯點(diǎn)。 例如，如下左圖信息表示右圖：6 9 ） 0 1000 Z4QQ TOC o 1-5 h z 2800 3QQ02400 250Q40000一4500 380D6000 1500II AXDijkstra算法：Dijkstra算法是最短路徑問題的經(jīng)典解決方案。它在教科書第21章中有描述?；舅悸凡浑y理解。對于圖中的每個頂點(diǎn)，我們維護(hù)從源點(diǎn)到該頂點(diǎn)的最短已知的路徑長度，并且將這些長度保持在優(yōu)先隊列（priority queu（PQ）中。 初始時，我們把所有的頂點(diǎn)放在這個隊列中，并設(shè)置高優(yōu)先級，然后將源點(diǎn)的優(yōu)先級設(shè)為0.0。算法通過從PQ中取出最低優(yōu)先級的頂點(diǎn)，然后檢查可從該頂點(diǎn)經(jīng)由

37、一條邊可達(dá)的所有頂點(diǎn)，以查看這條邊是否提供了從源點(diǎn)到那個頂點(diǎn)較之之前已知的最短路徑的更短路徑。如果是這樣，它會降低優(yōu)先級來反映這種新的信息。這里給出了 Dijkstra算法計算從0至U 5的最短路徑0-1-2-5的詳細(xì)過程。process 0 （0.0）lower 3 to 3841.9lower 1 to 1897.4process 1 （1897.4）lower 4 to 3776.2lower 2 to 2537.7process 2 （2537.7）lower 5 to 6274.0 process 4 (3776.2)process 3(3841.9)process 5 (6274.

38、0)-15 -該方法計算最短路徑的長度。為了記錄路徑，我們還保持每個頂點(diǎn)的源點(diǎn)到該頂點(diǎn)最短路徑上的前驅(qū)。文件 Euclidean Graph.java, Point.java, IndexPQ.java, Intlterator.java 和Dijkstra.java提供了針對 map的Dijkstra算法的基本框架實(shí)現(xiàn)，你應(yīng)該以此作為起點(diǎn)。客戶端程序ShortestPath.java求解一個單源點(diǎn)最短路徑問題，并使用圖形繪制了結(jié)果?？蛻舳顺绦騊aths.java求解了許多最短路徑問題，并將最短路徑打印到標(biāo)準(zhǔn)輸出?？蛻舳顺绦駾istances.java求解了許多最短路徑問題，僅將距離打印到標(biāo)準(zhǔn)

39、輸出。目標(biāo)：優(yōu)化Dijkstra算法，使其可以處理給定圖的數(shù)千條最短路徑查詢。一旦你讀取圖（并可選地預(yù)處理），你的程序應(yīng)該在亞線性時間內(nèi)解決最短路徑問題。一種方法是預(yù)先計算出所有頂點(diǎn)對的最短路徑；然而，你無法承受存儲所有這些信息所需的二次空間。你的目標(biāo)是減少每次最短路徑計算所涉及的工作量，而不會占用過多的空間。建議你選擇下面的一些潛在想法來實(shí)現(xiàn)，或者你可以開發(fā)和實(shí)現(xiàn)自己的想法。想法1: Dijkstra算法的樸素實(shí)現(xiàn)檢查圖中的所有V個頂點(diǎn)。減少檢查的頂點(diǎn)數(shù)量的一種策略是一旦發(fā)現(xiàn)目的地的最短路徑就停止搜索。通過這種方法，可以使每個最短路徑查詢的運(yùn)行時間與 E log V成比例，其中E和V是Dij

40、kstra算法檢查的邊和頂點(diǎn)數(shù)。然而，這需要一些小心，因為只是重新初始化所有距離為8就需要與V成正比的時間。由于你在不斷執(zhí)行查詢，因而只需重新初始化在先前查詢中改變的那些值來大大加速查詢。想法2：你可以利用問題的歐式幾何來進(jìn)一步減少搜索時間，這在算法書的第21.5節(jié)描述過。對于一般圖，Dijkstra通過將dw更新為dv +從v到w的距離來松弛邊 v-w。對于 地圖，則將dw更新為dv +從v到w的距離+從w到d的歐式距離 一從v到d的歐式 距離。 這種方法稱之為 A*算法。這種啟發(fā)式方法會有性能上的影響，但不會影響正確性。想法3:使用更快的優(yōu)先隊列。在提供的優(yōu)先隊列中有一些優(yōu)化空間。你也可以

41、考慮使用Sedgewick程序20.10中的多路堆。測試：美國大陸文件usa.txt包含87,575個交叉口和121,961條道路。圖形非常稀疏-平 均的度為2.8。你的主要目標(biāo)應(yīng)該是快速回答這個網(wǎng)絡(luò)上的頂點(diǎn)對的最短路徑查詢。你的算法可能會有不同執(zhí)行時間，這取決于兩個頂點(diǎn)是否在附近或相距較遠(yuǎn)。我們提供測試這兩種情況的輸入文件。你可以假設(shè)所有的 x和y坐標(biāo)都是0到10,000之間的整數(shù)。二、算法設(shè)計因為要實(shí)現(xiàn)地圖路由，地圖是一個加權(quán)無向圖，圖中所用的邊為加權(quán)無向邊，實(shí)現(xiàn)一個 加權(quán)無向圖的數(shù)據(jù)結(jié)構(gòu)，初始化地圖后，利用 Dijkstra算法來找出最短路徑。經(jīng)典的Dijkstra算法是初始化時就把所有

42、節(jié)點(diǎn)的最短路徑找出來了，程序優(yōu)化則可以重用代碼（想法 1）,多次查詢兩節(jié)點(diǎn)間最短路徑用同一對象，并且每次查詢當(dāng)找到目標(biāo)節(jié)點(diǎn) 后便停止，不再遍歷其他的節(jié)點(diǎn)。然后將上一次查詢改變的成員變量部分還原，以供下一次的查詢使用，這樣便大大的優(yōu)化了傳統(tǒng)的Dijkstra算法。優(yōu)化方法采用的想法 1減少檢查的頂點(diǎn)數(shù)量，一旦發(fā)現(xiàn)目的地的最短路徑就停止搜索。通過這種方法使每個最短路徑查詢的運(yùn)行時間與Hog V成比例，在不斷執(zhí)行查詢，每次重新初始化在先前查詢中改變的那些值來大大加速查詢。-16 -public class DijkstraUndirectedSP private double distTo;priv

43、ate Edge edgeTo;private IndexMinPQ pq;private EdgeWeightedGraph mGraph;private int from;public DijkstraUndirectedSP(EdgeWeightedGraph G) 設(shè)置算法的起點(diǎn)public void setFrom(int from) 更新到節(jié)點(diǎn)的最短路徑private void relax(Edge e, int v) 獲取到某一節(jié)點(diǎn)的最短距離public double distTo(intv) 在這里才執(zhí)行相關(guān)的路徑初始化public boolean hasPathTo(intv

44、) 還原上一次查詢被修改的部分public void itijkstra() 遍歷到一個節(jié)點(diǎn)所經(jīng)過的邊public Iterable pathTo(int v) 想法1實(shí)現(xiàn)：調(diào)用setFrom函數(shù)設(shè)置算法的起點(diǎn)，每次設(shè)置新的起點(diǎn)后，調(diào)用initDijkstra方法還原上次 查詢操作被修改的數(shù)據(jù)。/設(shè)置算法的起點(diǎn)public void setFrom(int from) / /開始新的-次查詢后把上一次修改過的部分還原初始化initDijkstra();=from;distTofrom = 0.0;pq. insert(from, distTofrom);-17 -/還原上一次查詢被修改的部分public void initDijkstra()for (int i = 0; i mGraph.v(); i+) if (pq. contains(i) pq.delete(i);if (edgeToil=nul1) edgeToi=null;if (!Double. isInfinite(distTo(i) distToi=Double. POSITIVE. INFINITY;當(dāng)執(zhí)行查詢源點(diǎn)到目的地的最短路徑時調(diào)用 hasPathTo方法來查詢，不斷的從優(yōu)先隊列