基於演算法電力路徑規劃

① djstl演算法

定義Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,
CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。
問題描述在無向圖
G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。（單源最短路徑）

編輯本段迪傑斯特拉演算法迪傑斯特拉(Dijkstra)演算法思想
按路徑長度遞增次序產生最短路徑演算法：

把V分成兩組：

（1）S：已求出最短路徑的頂點的集合

（2）V-S=T：尚未確定最短路徑的頂點集合

將T中頂點按最短路徑遞增的次序加入到S中，

保證：（1）從源點V0到S中各頂點的最短路徑長度都不大於

從V0到T中任何頂點的最短路徑長度

（2）每個頂點對應一個距離值

S中頂點：從V0到此頂點的最短路徑長度

T中頂點：從V0到此頂點的只包括S中頂點作中間

頂點的最短路徑長度

依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的

直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和

（反證法可證）

求最短路徑步驟
演算法步驟如下：

1. 初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值

若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值

若不存在<V0,Vi>，d(V0,Vi)為∝

2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S

3. 對S中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的

距離值縮短，則修改此距離值

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

編輯本段迪傑斯特拉演算法的原理首先，引進一個輔助向量D，它的每個分量D表示當前所找到的從始點v到每個終點vi的最短路徑的長度。如D[3]=2表示從始點v到終點3的路徑相對最小長度為2。這里強調相對就是說在演算法過程中D的值是在不斷逼近最終結果但在過程中不一定就等於最短路徑長度。它的初始狀態為：若從v到vi有弧，則D為弧上的權值；否則置D為∞。顯然，長度為
D[j]=Min{D | vi∈V} 的路徑就是從v出發的長度最短的一條最短路徑。此路徑為(v,vj)。
那麼，下一條長度次短的最短路徑是哪一條呢？假設該次短路徑的終點是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權值，或者是D[j]和從vj到vk的弧上的權值之和。
一般情況下，假設S為已求得最短路徑的終點的集合，則可證明：下一條最短路徑（設其終點為X）或者是弧(v,x)，或者是中間只經過S中的頂點而最後到達頂點X的路徑。因此，下一條長度次短的最短路徑的長度必是D[j]=Min{D
| vi∈V-S} 其中，D或者是弧(v,vi)上的權值，或者是D[k](vk∈S)和弧(vk,vi)上的權值之和。 迪傑斯特拉演算法描述如下：
1）arcs表示弧上的權值。若不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到從v出發的最短路徑的終點的集合，初始狀態為空集。那麼，從v出發到圖上其餘各頂點vi可能達到的最短路徑長度的初值為D=arcs[Locate
Vex(G,v),i] vi∈V 2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發到集合V-S上任一頂點vk可達的最短路徑長度。

編輯本段迪傑斯特拉演算法C#程序public class Edge

{

public string StartNodeID ;

public string EndNodeID ;

public double Weight ; //權值，代價

} 節點則抽象成Node類，一個節點上掛著以此節點作為起點的「出邊」表。

public class Node

{

private string iD ;

private ArrayList edgeList ;//Edge的集合－－出邊表

public Node(string id )

{

this.iD = id ;

this.edgeList = new ArrayList() ;

}

property#region property

public string ID

{

get

{

return this.iD ;

}

}

public ArrayList EdgeList

{

get

{

return this.edgeList ;

}

}

#endregion

}

在計算的過程中，我們需要記錄到達每一個節點權值最小的路徑，這個抽象可以用PassedPath類來表示：

/// <summary>

/// PassedPath 用於緩存計算過程中的到達某個節點的權值最小的路徑

/// </summary>

public class PassedPath

{

private string curNodeID ;

private bool beProcessed ; //是否已被處理

private double weight ; //累積的權值

private ArrayList passedIDList ; //路徑

public PassedPath(string ID)

{

this.curNodeID = ID ;

this.weight = double.MaxValue ;

this.passedIDList = new ArrayList() ;

this.beProcessed = false ;

}

#region property

public bool BeProcessed

{

get

{

return this.beProcessed ;

}

set

{

this.beProcessed = value ;

}

}

public string CurNodeID

{

get

{

return this.curNodeID ;

}

}

public double Weight

{

get

{

return this.weight ;

}

set

{

this.weight = value ;

}

}

public ArrayList PassedIDList

{

get

{

return this.passedIDList ;

}

}

#endregion

}

另外，還需要一個表PlanCourse來記錄規劃的中間結果，即它管理了每一個節點的PassedPath。

/// <summary>

/// PlanCourse 緩存從源節點到其它任一節點的最小權值路徑=》路徑表

/// </summary>

public class PlanCourse

{

private Hashtable htPassedPath ;

#region ctor

public PlanCourse(ArrayList nodeList ,string originID)

{

this.htPassedPath = new Hashtable() ;

Node originNode = null ;

foreach(Node node in nodeList)

{

if(node.ID == originID)

{

originNode = node ;

}

else

{

PassedPath pPath = new PassedPath(node.ID) ;

this.htPassedPath.Add(node.ID ,pPath) ;

}

}

if(originNode == null)

{

throw new Exception("The origin node is not exist !")
;

}

this.InitializeWeight(originNode) ;

}

private void InitializeWeight(Node originNode)

{

if((originNode.EdgeList == null)
||(originNode.EdgeList.Count == 0))

{

return ;

}

foreach(Edge edge in originNode.EdgeList)

{

PassedPath pPath = this[edge.EndNodeID] ;

if(pPath == null)

{

continue ;

}

pPath.PassedIDList.Add(originNode.ID) ;

pPath.Weight = edge.Weight ;

}

}

#endregion

public PassedPath this[string nodeID]

{

get

{

return (PassedPath)this.htPassedPath[nodeID] ;

}

}

}

在所有的基礎構建好後，路徑規劃演算法就很容易實施了，該演算法主要步驟如下：

(1)用一張表(PlanCourse)記錄源點到任何其它一節點的最小權值，初始化這張表時，如果源點能直通某節點，則權值設為對應的邊的權，否則設為double.MaxValue。

(2)選取沒有被處理並且當前累積權值最小的節點TargetNode，用其邊的可達性來更新到達其它節點的路徑和權值（如果其它節點
經此節點後權值變小則更新，否則不更新），然後標記TargetNode為已處理。

(3)重復(2)，直至所有的可達節點都被處理一遍。

(4)從PlanCourse表中獲取目的點的PassedPath，即為結果。

下面就來看上述步驟的實現，該實現被封裝在RoutePlanner類中：

/// <summary>

/// RoutePlanner 提供圖演算法中常用的路徑規劃功能。

/// 2005.09.06

/// </summary>

public class RoutePlanner

{

public RoutePlanner()

{

}

#region Paln

//獲取權值最小的路徑

public RoutePlanResult Paln(ArrayList nodeList ,string
originID ,string destID)

{

PlanCourse planCourse = new PlanCourse(nodeList
,originID) ;

Node curNode = this.GetMinWeightRudeNode(planCourse
,nodeList ,originID) ;

#region 計算過程

while(curNode != null)

{

PassedPath curPath = planCourse[curNode.ID] ;

foreach(Edge edge in curNode.EdgeList)

{

PassedPath targetPath = planCourse[edge.EndNodeID] ;

double tempWeight = curPath.Weight + edge.Weight ;

if(tempWeight < targetPath.Weight)

{

targetPath.Weight = tempWeight ;

targetPath.PassedIDList.Clear() ;

for(int i=0 ;i<curPath.PassedIDList.Count ;i++)

{

targetPath.PassedIDList.Add(curPath.PassedIDList.ToString())
;

}

targetPath.PassedIDList.Add(curNode.ID) ;

}

}

//標志為已處理

planCourse[curNode.ID].BeProcessed = true ;

//獲取下一個未處理節點

curNode = this.GetMinWeightRudeNode(planCourse
,nodeList ,originID) ;

}

#endregion

//表示規劃結束

return this.GetResult(planCourse ,destID) ;

}

#endregion

#region private method

#region GetResult

//從PlanCourse表中取出目標節點的PassedPath，這個PassedPath即是規劃結果

private RoutePlanResult GetResult(PlanCourse
planCourse ,string destID)

{

PassedPath pPath = planCourse[destID] ;

if(pPath.Weight == int.MaxValue)

{

RoutePlanResult result1 = new RoutePlanResult(null
,int.MaxValue) ;

return result1 ;

}

string[] passedNodeIDs = new
string[pPath.PassedIDList.Count] ;

for(int i=0 ;i<passedNodeIDs.Length ;i++)

{

passedNodeIDs = pPath.PassedIDList.ToString() ;

}

RoutePlanResult result = new
RoutePlanResult(passedNodeIDs ,pPath.Weight) ;

return result ;

}

#endregion

#region GetMinWeightRudeNode

//從PlanCourse取出一個當前累積權值最小，並且沒有被處理過的節點

private Node GetMinWeightRudeNode(PlanCourse
planCourse ,ArrayList nodeList ,string originID)

{

double weight = double.MaxValue ;

Node destNode = null ;

foreach(Node node in nodeList)

{

if(node.ID == originID)

{

continue ;

}

PassedPath pPath = planCourse[node.ID] ;

if(pPath.BeProcessed)

{

continue ;

}

if(pPath.Weight < weight)

{

weight = pPath.Weight ;

destNode = node ;

}

}

return destNode ;

}

#endregion

#endregion

}

編輯本段迪傑斯特拉演算法pascal程序type bool=array[1..10]of
boolean;

arr=array[0..10]of integer;

var a:array[1..10,1..10]of integer;
//存儲圖的鄰接數組，無邊為10000

c,d,e:arr; //c為最短路徑數值,d為各點前趨,

t:bool; //e：路徑，t為輔助數組

i,j,n,m:integer;

inf,outf:text;

////////////////////////////////////////////////////////////////////////////////

procere init; //不同題目鄰接數組建立方式不一樣

begin

assign(inf,'dijkstra.in');
assign(outf,'dijkstra.out');

reset(inf); rewrite(outf);

read(inf,n);

for i:=1 to n do

for j:=1 to n do

begin

read(inf,a[i,j]);

if a[i,j]=0 then a[i,j]:=10000;

end;

end;

////////////////////////////////////////////////////////////////////////////////

procere dijkstra(qi:integer; t:bool; var c{,d}:arr);
//qi起點，{}中為求路徑部

var i,j,k,min:integer; //分,不需求路徑時可以不要

begin //t數組一般在調用前初始

t[qi]:=true; //化成false,也可將部分點

{for i:=1 to n do d[i]:=qi; d[qi]:=0; }
//初始化成true以迴避這些點

for i:=1 to n do c[i]:=a[qi,i];

for i:=1 to n-1 do

begin

min:=10001;

for j:=1 to n do

if (c[j]<min)and(not(t[j])) then begin k:=j;
min:=c[j];end;

t[k]:=true;

for j:=1 to n do

if (c[k]+a[k,j]<c[j])and(not(t[j])) then

begin

c[j]:=c[k]+a[k,j]; {d[j]:=k;}

end;

end;

end;

////////////////////////////////////////////////////////////////////////////////

procere make(zh:integer; d:arr; var e:arr);
//生成路徑,e[0]保存路徑

var i,j,k:integer; //上的節點個數

begin

i:=0;

while d[zh]<>0 do

begin

inc(i);e[i]:=zh;zh:=d[zh];

end;

inc(i);e[i]:=qi; e[0]:=I;

end;

主程序調用：求最短路徑長度：初始化t，然後dijkstra(qi,t,c,d)

求路徑：make(m,d,e) ，m是終點

編輯本段Dijkstra演算法的堆優化(PASCAL實現)一、思考
我們可以發現，在實現步驟時，效率較低(需要O(n)，使總復雜度達到O(n^2)。對此可以考慮用堆這種數據結構進行優化，使此步驟復雜度降為O(log(n))(總復雜度降為O(n
log(n))。

二、實現
1. 將與源點相連的點加入堆，並調整堆。
2. 選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。
3. 處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點
1):若該點在堆里，更新距離，並調整該元素在堆中的位置。
2):若該點不在堆里，加入堆，更新堆。
4. 若取到的u為終點，結束演算法；否則重復步驟2、3。
三、代碼
procere Dijkstra;

var

u,v,e,i:longint;

begin

fillchar(dis,sizeof(dis),$7e); //距離

fillchar(Inh,sizeof(Inh),false); //是否在堆中

fillchar(visit,sizeof(visit),false); //是否訪問過

size:=0;

e:=last[s];

while e<>0 do //步驟1

begin

u:=other[e];

if not(Inh[u]) then //不在堆里

begin

inc(size);

heap[size]:=u;

dis[u]:=cost[e];

Loc[u]:=size; //Loc數組記錄元素在堆中的位置

Inh[u]:=true;

Shift_up(Loc[u]); //上浮

end

else

if cost[e]<dis[u] then //在堆里

begin

dis[u]:=cost[e];

Shift_up(Loc[u]);

Shift_down(Loc[u]);

end;

e:=pre[e];

end;

visit[s]:=true;

while true do

begin

u:=heap[1]; //步驟2

if u=t then break; //步驟4

visit[u]:=true;

heap[1]:=heap[size];

dec(size);

Shift_down(1);

e:=last[u];

while e<>0 do //步驟3

begin

v:=other[e];

if Not(visit[v]) and (dis[u]+cost[e]<dis[v]) then
//與u相鄰的，未被訪問過的，滿足三角不等式的頂點

if Inh[v] then //在堆中

begin

dis[v]:=dis[u]+cost[e];

Shift_up(Loc[v]);

Shift_Down(Loc[v]);

end

else //不再堆中

begin

inc(size);

heap[size]:=v;

dis[v]:=dis[u]+cost[e];

Loc[v]:=size;

Inh[v]:=true;

Shift_up(Loc[v]);

end;

e:=pre[e];

end;

end;

writeln(dis[t]);

end;
http://ke..com/view/7839.htm

http://ke..com/view/1939816.htm

② （4）動力學約束下的路徑規劃

運動學上的約束，比如避障，動力學約束，比如速度，加速度，等
在考慮上述條件的情況下，是不能將機器人簡單的考慮為一個質點，進行路徑規劃的

純學院派的路徑規劃是不在前端考慮的，但是當動力學約束非常復雜的時候，完全依賴後端進行優化是不現實的。

我們希望點之間的連線是滿足動力學
正向方式：離散機器人控制空間，產生很多路徑
反向方式：離散機器人狀態空間，尋找路徑

最開始基於圖的搜索演算法其實就是對機器人的控制空間的離散化，將機器人的控制空間進行四離散或者八離散
基於采樣的搜索演算法其實就是對狀態空間的離散化，將機器人的狀態離散為每個點

首先建立描述機器人狀態的微分方程，s' = f(s,u)
首先知道機器人的初始狀態s0
1、離散化控制空間，給系統一個固定的u激勵，保持一個時間T，正向模擬系統
知道S0，給定u和T，進行模擬，積分就好了，但是沒有目標導向，規劃效率比較低
2、離散化狀態空間，選擇一個新狀態Sf，從Sf和S0解析出一個軌跡(u,T)，在求解困難的情況下，可以固定時間T，求解u，反向求解系統，難以實現特定的演算法，但是效率很高，任務導向性很高

控制空間離散化，從樹里選擇一點，然後衍生lattice grauph，給定時間，再去往前積分，選擇路徑

狀態空間離散化，選擇一點，反算是如何到達的

③ 基於神經網路的路徑規劃演算法，怎樣判斷點是否在障礙物內部的

遺傳演算法在很多領域都得到應用；從神經網路研究的角度上考慮，最關心的是遺傳演算法在神經網路的應用。在遺傳演算法應用中，應先明確其特點和關鍵問題，才能對這種演算法深入了解，靈活應用，以及進一步研究開發。一、遺傳演算法的特點1．遺傳演算法從問

④ 基於激光雷達的SLAM和路徑規劃演算法研究與實現

本文僅供學習使用，並非商業用途，全文是針對哈爾濱工業大學劉文之的論文《移動機器人的路徑規劃與定位技術研究》進行提煉與學習。論文來源中國知網，引用格式如下：
[1]劉文之. 基於激光雷達的SLAM和路徑規劃演算法研究與實現[D].哈爾濱工業大學,2018.

相關坐標系轉換原理已經在前一篇文章寫完了，直接上轉換方程。

這里他的運動模型選擇的是基於里程計的運動模型，還有一種基於速度的運動模型，其實都差不多，整體思想都一樣。里程計是通過計算一定時間內光電編碼器輸出脈沖數來估計機器人運動位移的裝置，主要是使用光電碼盤。根據光電碼盤計算出此時輪子的速度，然後通過已知的輪子半徑來獲得單位時間 每個輪子 的位移增量。

高等數學可知單位時間位移增量就是速度，對速度在一定時間上進行積分就得到這一段時間所走過的路程。

根據上圖，我們可以求出來機器人航向角角速度、圓弧運動半徑和機器人角度變化量，由此可以解的機器人在當前時刻的位姿。

實際上也是有誤差，所以單獨依靠里程計會與實際結果產生較大誤差，所以必須引入其他的外部感測器對外部環境的觀測來修正這些誤差，從而提高定位精度。

首先肯定需要將激光雷達所測得的端點坐標從極坐標、機器人坐標中轉換到世界坐標中。

這張略過，暫時不需要看這個

路徑規劃演算法介紹：

因為該演算法會產生大量的無用臨時途徑，簡單說就是很慢，所以有了其他演算法。

了解兩種代價之後，對於每一個方塊我們採用預估代價與當前路徑代價相加的方法，這樣可以表示每一個路徑點距離終點的距離。在BFS搜索過程的基礎上，優先挑選總代價最低的那個路徑進行搜索，就可以少走不少彎路。（演算法講解 https://www.bilibili.com/video/BV1bv411y79P?from=search&seid=3623681329596549549 ）

在局部路徑規劃演算法之中，我們選用DWA演算法（dynamic window approach），又叫動態窗口法。動態窗口法主要是在速度(v, w)空間中采樣多組速度，並模擬機器人在這些速度下一定時間內的軌跡。在得到多組軌跡後，對這些軌跡進行評價，選取最優的軌跡所對應的速度來驅動機器人運動。
state sampling就是按照之前給出的全局路徑規劃，無論是Dijkstra還是A* 都可以方便的得到state sampling，DWA演算法所需要提前建立的action sampling有兩種：

但是無論是什麼情況，上述所做的工作就是把機器人的位移轉化到世界坐標中來，而不是機器人坐標系。速度采樣結束之後，只需要對小車的軌跡進行評判，就可以得到最優解了。下面介紹速度采樣的辦法。

對速度進行采樣一般有以下三個限制：

當確定了速度范圍之後，就需要根據速度解析度來對小車速度離散化，在每一時刻將小車在不同直線速度角速度組合下所即將要行駛的距離都可視化出來。

其中每一條軌跡都是很多小直線連接起來的。

需要用評價函數來對上述軌跡進行選擇，選擇最適合的軌跡

最後為了讓三個參數在評價函數里所發揮的作用均等，我們使用歸一化處理來計算權重。

演算法流程整體如下：

⑤ 遺傳演算法路徑規劃是什麼原理

遺傳演算法有相當大的引用。遺傳演算法在游戲中應用的現狀在遺傳編碼時, 一般將瓦片的坐標作為基因進行實數編碼, 染色體的第一個基因為起點坐標, 最後一個基因為終點坐標, 中間的基因為路徑經過的每一個瓦片的坐標。在生成染色體時, 由起點出發, 隨機選擇當前結點的鄰居節點中的可通過節點, 將其坐標加入染色體, 依此循環, 直到找到目標點為止, 生成了一條染色體。重復上述操作, 直到達到指定的種群規模。遺傳演算法的優點：1、遺傳演算法是以決策變數的編碼作為運算對象，可以直接對集合、序列、矩陣、樹、圖等結構對象進行操作。這樣的方式一方面有助於模擬生物的基因、染色體和遺傳進化的過程，方便遺傳操作運算元的運用。另一方面也使得遺傳演算法具有廣泛的應用領域，如函數優化、生產調度、自動控制、圖像處理、機器學習、數據挖掘等領域。2、遺傳演算法直接以目標函數值作為搜索信息。它僅僅使用適應度函數值來度量個體的優良程度，不涉及目標函數值求導求微分的過程。因為在現實中很多目標函數是很難求導的，甚至是不存在導數的，所以這一點也使得遺傳演算法顯示出高度的優越性。3、遺傳演算法具有群體搜索的特性。它的搜索過程是從一個具有多個個體的初始群體P(0)開始的，一方面可以有效地避免搜索一些不必搜索的點。另一方面由於傳統的單點搜索方法在對多峰分布的搜索空間進行搜索時很容易陷入局部某個單峰的極值點，而遺傳演算法的群體搜索特性卻可以避免這樣的問題，因而可以體現出遺傳演算法的並行化和較好的全局搜索性。4、遺傳演算法基於概率規則，而不是確定性規則。這使得搜索更為靈活，參數對其搜索效果的影響也盡可能的小。5、遺傳演算法具有可擴展性，易於與其他技術混合使用。以上幾點便是遺傳演算法作為優化演算法所具備的優點。遺傳演算法的缺點：遺傳演算法在進行編碼時容易出現不規范不準確的問題。

⑥ 機器人路徑規劃演算法是什麼

機器人路徑規劃演算法是 路徑規劃的目的是在給定起點和目標點的空間里規劃出一條從起點到目標點的無碰撞路徑。

移動機器人的路徑規劃,就是移動機器人在所處的環境中尋找到一條從起始點到目標點的無碰路徑,尤其是移動機器人在沒有人為干預的情況下的自主運動,這就需要各種智能演算法融入到機器人自身控制系統中,使得移動機器人自主做出判斷和決策。

⑦ 關於時間依賴的最短路徑演算法

Dijkstra 最短路徑演算法的一種高效率實現*

隨著計算機的普及以及地理信息科學的發展，GIS因其強大的功能得到日益廣泛和深入的應用。網路分析作為GIS最主要的功能之一，在電子導航、交通旅遊、城市規劃以及電力、通訊等各種管網、管線的布局設計中發揮了重要的作用，而網路分析中最基本最關鍵的問題是最短路徑問題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他的度量，如時間、費用、線路容量等。相應地，最短路徑問題就成為最快路徑問題、最低費用問題等。由於最短路徑問題在實際中常用於汽車導航系統以及各種應急系統等（如110報警、119火警以及醫療救護系統），這些系統一般要求計算出到出事地點的最佳路線的時間應該在1 s～3 s內，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現應該是高效率的。其實,無論是距離最短、時間最快還是費用最低，它們的核心演算法都是最短路徑演算法。經典的最短路徑演算法——Dijkstra演算法是目前多數系統解決最短路徑問題採用的理論基礎，只是不同系統對Dijkstra演算法採用了不同的實現方法。
據統計，目前提出的此類最短路徑的演算法大約有17種。F.Benjamin Zhan等人對其中的15種進行了測試，結果顯示有3種效果比較好，它們分別是：TQQ（graph growth with two queues）、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstra�s algorithm implemented with double buckets )，這些演算法的具體內容可以參見文獻〔1〕。其中TQQ演算法的基礎是圖增長理論，較適合於計算單源點到其他所有點間的最短距離；後兩種演算法則是基於Dijkstra的演算法，更適合於計算兩點間的最短路徑問題〔1〕。總體來說，這些演算法採用的數據結構及其實現方法由於受到當時計算機硬體發展水平的限制，將空間存儲問題放到了一個很重要的位置，以犧牲適當的時間效率來換取空間節省。目前，空間存儲問題已不是要考慮的主要問題，因此有必要對已有的演算法重新進行考慮並進行改進，可以用空間換時間來提高最短路徑演算法的效率。
1 經典Dijkstra演算法的主要思想
Dijkstra演算法的基本思路是：假設每個點都有一對標號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等於零)；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑演算法的基本過程如下：
1) 初始化。起源點設置為：① ds=0, ps為空;② 所有其他點: di=∞, pi= ;③ 標記起源點s，記k=s,其他所有點設為未標記的。
2) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，並設置：
dj=min〔dj, dk+lkj〕
式中，lkj是從點k到j的直接連接距離。
3) 選取下一個點。從所有未標記的結點中，選取dj 中最小的一個i：
di=min〔dj, 所有未標記的點j〕
點i就被選為最短路徑中的一點，並設為已標記的。
4) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點,設置：
i=j*
5) 標記點i。如果所有點已標記，則演算法完全推出，否則，記k=i，轉到2) 再繼續。
2 已有的Dijkstra演算法的實現
從上面可以看出，在按標記法實現Dijkstra演算法的過程中，核心步驟就是從未標記的點中選擇一個權值最小的弧段，即上面所述演算法的2)～5)步。這是一個循環比較的過程，如果不採用任何技巧，未標記點將以無序的形式存放在一個鏈表或數組中。那麼要選擇一個權值最小的弧段就必須把所有的點都掃描一遍，在大數據量的情況下，這無疑是一個制約計算速度的瓶頸。要解決這個問題，最有效的做法就是將這些要掃描的點按其所在邊的權值進行順序排列，這樣每循環一次即可取到符合條件的點，可大大提高演算法的執行效率。另外，GIS中的數據 (如道路、管網、線路等)要進行最短路徑的計算，就必須首先將其按結點和邊的關系抽象為圖的結構，這在GIS中稱為構建網路的拓撲關系 (由於這里的計算與面無關，所以拓撲關系中只記錄了線與結點的關系而無線與面的關系，是不完備的拓撲關系)。如果用一個矩陣來表示這個網路，不但所需空間巨大，而且效率會很低。下面主要就如何用一個簡潔高效的結構表示網的拓撲關系以及快速搜索技術的實現進行討論。
網路在數學和計算機領域中被抽象為圖，所以其基礎是圖的存儲表示。一般而言，無向圖可以用鄰接矩陣和鄰接多重表來表示，而有向圖則可以用鄰接表和十字鏈表〔4〕 表示，其優缺點的比較見表 1。
表 1 幾種圖的存儲結構的比較
Tab. 1 The Comparsion of Several Graph for Storing Structures
名 稱 實現方法 優 點 缺 點 時間復雜度
鄰接矩陣 二維數組 1. 易判斷兩點間的關系 佔用空間大 O(n2+m*n)
2. 容易求得頂點的度
鄰接表 鏈表 1. 節省空間 1. 不易判斷兩點間的關系 O(n+m)或O(n*m)
2. 易得到頂點的出度 2. 不易得到頂點的入度
十字鏈表 鏈表 1. 空間要求較小 結構較復雜 同鄰接表
2.易求得頂點的出度和入度
鄰接多重表 鏈表 1. 節省空間 結構較復雜 同鄰接表
2. 易判斷兩點間的關系

目前,對於演算法中快速搜索技術的實現，主要有桶結構法、隊列法以及堆棧實現法。TQQ、DKA 以及 DKD 在這方面是比較典型的代表。TQQ雖然是基於圖增長理論的，但是快速搜索技術同樣是其演算法實現的關鍵，它用兩個FIFO的隊列實現了一個雙端隊列結構來支持搜索過程〔1〕。
DKA和DKD是採用如圖 1 所示的桶結構來支持這個運算，其演算法的命名也來源於此。在DKA演算法中，第i個桶內裝有權值落在 〔b*i, (i+1)*b) 范圍內的可供掃描的點，其中b是視網路中邊的權值分布情況而定的一個常數。每一個桶用隊列來維護，這樣每個點有可能被多次掃描，但最多次數不會超過b次。最壞情況下，DKA的時間復雜度將會是O(m*b+n(b+C/b))，其中，C為圖中邊的最大權值。DKD將點按權值的范圍大小分裝在兩個級別的桶內，高級別的桶保存權值較大的點，相應的權值較小的點都放在低級別的桶內，每次掃描都只針對低級別桶中的點。當然隨著點的插入和刪除，兩個桶內的點是需要動態調整的。在DKA演算法中，給每個桶一定的范圍以及DKD中使用雙桶，在一定程度上都是以空間換時間的做法，需要改進。

圖 1 一個桶結構的示例
Fig. 1 An Example of the Bucket Data Structure
3 本文提出的Dijkstra演算法實現
3.1 網路拓撲關系的建立
上面介紹的各種圖的存儲結構考慮了圖在理論上的各種特徵，如有向、無向、帶權、出度、入度等。而GIS中的網路一般為各種道路、管網、管線等，這些網路在具有圖理論中的基本特徵的同時，更具有自己在實際中的一些特點。首先，在GIS中大多數網路都是有向帶權圖，如道路有單雙向問題，電流、水流都有方向（如果是無向圖也可歸為有向圖的特例），且不同的方向可能有不同的權值。更重要的一點是，根據最短路徑演算法的特性可以知道，頂點的出度是個重要指標，但是其入度在演算法里則不必考慮。綜合以上4種存儲結構的優缺點， 筆者採用了兩個數組來存儲網路圖，一個用來存儲和弧段相關的數據（Net-Arc List），另一個則存儲和頂點相關的數據（Net-Node Index）。Net-Arc List用一個數組維護並且以以弧段起點的點號來順序排列，同一起點的弧段可以任意排序。這個數組類似於鄰接矩陣的壓縮存儲方式，其內容則具有鄰接多重表的特點，即一條邊以兩頂點表示。Net-Node Index則相當於一個記錄了頂點出度的索引表，通過它可以很容易地得到此頂點的出度以及與它相連的第一條弧段在弧段數組中的位置。此外，屬性數據作為GIS不可少的一部分也是必須記錄的。這樣，計算最佳路徑所需的網路信息已經完備了。在頂點已編號的情況下，建立Net-Arc List和Net-Node Index兩個表以及對Net-Arc List的排序，其時間復雜度共為O(2n+lgn)，否則為O(m+2n+lgn)。這個結構所需的空間也是必要條件下最小的，記錄了m個頂點以及n條邊的相關信息，與鄰接多重表是相同的。圖 2 是採用這個結構的示意圖。
3.2 快速搜索技術的實現
無論何種演算法，一個基本思想都是將點按權值的大小順序排列，以節省操作時間。前面已經提到過，這兩個演算法都是以時間換空間的演算法，所以在這里有必要討論存儲空間問題 (這部分空間的大小依賴於點的個數及其出度)。根據圖中頂點和邊的個數可以求出頂點的平均出度e=m/n（m為邊數，n為頂點數），這個數值代表了圖的連通程度，一般在GIS的網路圖中，e∈〔2,5〕。這樣,如果當前永久標記的點為t個，那麼，下一步需掃描點的個數就約為t～4t個。如果採用鏈表結構，按實際應用中的網路規模大小，所需的總存儲空間一般不會超過100 K。所以完全沒有必要採用以時間換空間的做法，相反以空間換時間的做法是完全可行的。在實現這部分時，筆者採用了一個FIFO隊列，相應的操作主要是插入、排序和刪除，插入和刪除的時間復雜度都是O(1)，所以關鍵問題在於選擇一個合適的排序演算法。一般可供選擇的排序演算法有快速排序、堆排序以及歸並排序等，其實現的平均時間都為O(nlgn)。經過比較實驗，筆者選擇了快速排序法。另外，Visual C++提供的run-time庫也提供了現成的快速排序的函數qsort( )可供使用。

圖 2 基於最佳路徑計算的網路拓撲表示
Fig. 2 The Presentation of the Network Topology
Used for Computing the Shortest Path
按照以上思路，筆者用Visual C++實現了吉奧之星（GeoStar）中的最佳路徑模塊。以北京的街道為數據（共6 313個結點，9 214條弧段(雙向)），在主頻為133、硬碟為1 G、內存為32 M的機器上，計算一條貫穿全城、長為155.06 km的線路，約需1 s～2 s。如圖 3所示。

圖 3 GeoStar中最佳路徑實現示意圖

ps:圖片沒有辦法貼上去.
你可以參考《演算法導論》第二版

⑧ 全局路徑規劃演算法

全局路徑規劃，主要演算法有
1、網格法、
2、拓撲法、
3、視圖法。

⑨ 路徑規劃演算法

強化學習比較好吧

⑩ 代碼！！！－－基於遺傳演算法在路徑規劃優化中的應用

遺傳演算法， 是人工智慧的一種演算法的。

以前圖書館有看到， 很多相關的書的，不要寄望於自己什麼都不做，就找人家幫忙啦。