dijkstra演算法，a*演算法和d*演算法
dijkstra演算法是典型最短路演算法，用於計算乙個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴充套件，直到擴充套件到終點為止。dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。
dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如資料結構，圖論，運籌學等等。
dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用open, close表方式，drew為了和下面要介紹的 a* 演算法和 d* 演算法表述一致，這裡均採用open,close表的方式。
大概過程：
建立兩個表，open, close。
open表儲存所有已生成而未考察的節點，closed表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入open組中等待檢查。
2． 從open表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到close表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到open表中。
4． 重複2，3，步。直到open表為空，或找到目標點。
提高dijkstra搜尋速度的方法很多，常用的有資料結構採用binary heap的方法，和用dijkstra從起始點和終點同時搜尋的方法。
a*（a-star)演算法是一種啟發式演算法，是靜態路網中求解最短路最有效的方法。
公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函式，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函式h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜尋的點數多，搜尋範圍大，效率低。但能得到最優解。
如果估價值》實際值, 搜尋的點數少，搜尋範圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函式取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函式f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜尋向終點的方向進行。明顯優於dijstra演算法的毫無無方向的向四周搜尋。
conditions of heuristic
optimistic (must be less than or equal to the real cost)
as close to the real cost as possible
主要搜尋過程：
建立兩個表，open表儲存所有已生成而未考察的節點，closed表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入close中，取n節點的子節點x,->算x的估價值->
while(open!=null)
將n節點插入close表中;
按照估價值將open表中的節點排序; //實際上是比較open表內節點f的大小，從最小路徑的節點向下進行。
}a*演算法和dijistra演算法的區別在於有無估價值，dijistra演算法相當於a*演算法中估價值為0的情況。
動態路網，最短路演算法 d*a* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。
d*是動態a*（d-star,dynamic a*） 卡內及梅隆機械人中心的stentz在1994和2023年兩篇文章提出，主要用於機械人探路。是火星探測器採用的尋路演算法。
主要方法：
1.先用dijstra演算法從目標節點g向起始節點搜尋。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。
每個節點包含上一節點到目標點的最短路資訊1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原open和close中節點資訊儲存。
2.機械人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步dijstra計算出的最短路資訊從出發點向後追述即可，當在y點探測到下一節點x狀態發生改變，如堵塞。機械人首先調整自己在當前位置y到目標點g的實際值h(y)，h(y)=x到y的新權值c(x,y)+x的原實際值h(x).
x為下一節點(到目標點方向y->x->g），y是當前點。k值取h值變化前後的最小。
3.用a*或其它演算法計算，這裡假設用a*演算法,遍歷y的子節點，點放入close,調整y的子節點a的h值，h(a)=h(y)+y到子節點a的權重c(y,a),比較a點是否存在於open和close中，方法如下：
while()
if(a in close) 比較兩個a的h值 //注意是同乙個節點的兩個不同路徑的估價值
if( a的h值小於close表的h值 )
if(a not in both)
將a插入open表中; //還沒有排序
}放y到close表；
open表比較k值大小進行排序；
}機械人利用第一步dijstra計算出的最短路資訊從a點到目標點的最短路經進行。
d*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機械人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。
Dijkstra最短路徑演算法實習報告
1.引言 交通誘導系統的乙個核心技術是最優路徑的選擇技術。根據交通網路模型中各頂點和頂點之間的長度 時間或費用等屬性權值，通過dijkstra最短路徑演算法，解決有向圖即交通網路模型中源點到其他頂點的最短路徑問題。2.建立交信道路網路模型 交信道路網是路徑誘導的基礎和物件，首先需要建立交信道路網路模...
最短路徑Dijkstra演算法實驗報告
class graph template void graph creat graph template void graph show shortestpath template void graph shortestpath dij d v0 0 final v0 true for i 1 i ...
1 1 3演算法的三種基本邏輯結構和框圖表示 練習題
1.1.3演算法的三種基本邏輯結構和框圖表示 一 選擇題 1 任何乙個演算法都離不開的基本結構為 a 邏輯結構 b 條件分支結構 c 迴圈結構 d 順序結構 解析 選d.任何乙個演算法都要由開始到結束，故應當都有順序結構 2.如圖的程式框圖表示的演算法的功能是 a 計算小於100的奇數的連乘積 b ...