室內導航路徑最優演算法

A. 高清地圖的路徑規劃是為

一、何謂路徑規劃？

路徑規劃是指導航中物體從起點移動到終點時在地圖上做出路線選擇行為。

一般情況下，路徑規劃主要功能是搜索起止點之間的 最優路徑。注意，路徑規劃並不一定尋找最短路徑，路徑規劃有一套系統的衡量指標——時間最短、距離最短或者時間/距離綜合等等。

因此，路徑規劃根據衡量標准，可以大致分為一下類型：

最短路徑：只考慮時間，不考慮距離或其他因素；

最快路徑：只考慮距離，不考慮時間或其他因素；

50/50路徑：同時考慮時間和距離因素。

發展至今，導航路徑規劃已經不僅僅限於以上三類，隨著技術發展逐漸能夠滿足人們多種個性化的導航需求，實際上生活中我們還會體驗到如下的導航技術：

實際上，路徑規劃是根據一定需求在地圖上進行路線選擇。紅綠燈少，是一種導航需求，隨著移動互聯網和大數據發展，這類導航需求將逐漸被滿足，但是萬變不離宗，所有導航需求，歸根結底，還是在討論距離和時間的問題。

二、我們導航路線是如何被規劃出來的？

從過程上講，導航路線的確定過程可以拆解成以下步驟：

輸入：目的地、當前位置

計算：導航引擎在得到目的地與自身位置信息後，就需要根據地圖，選擇演算法，計算出最優的路徑。

輸出：最優路徑，或多條備選路徑

按照演算法，路徑規劃可以區分為靜態路徑規劃和動態路徑規劃，靜態路徑規劃演算法的研究已經比較成熟，但目前在終端上的路徑規劃，當路程很長時，有時仍然存在資源利用率高，系統響應慢等問題。因此，目前我們日常基礎到的基本上是動態路徑規劃。

那麼，路徑規劃的演算法有哪些？

實際上，路徑規劃有很多演算法，在導航中，經常提到的就是Dijkstra演算法和A*演算法。

Dijkstra演算法，中文譯名為迪傑斯特拉演算法，是由荷蘭計算機科學家狄克斯特拉於1959 年提出的。從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。迪傑斯特拉演算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

Dijkstra演算法原理圖

A*演算法是導航路徑計算中的標准演算法。它比Dijkstra演算法多了一個估算函數，若估算函數為0，A*演算法也就退化為Dijkstra演算法。

但在一般的嵌入式硬體上，基於性能和內存的限制與要求，不能直接使用A*演算法計算路徑。所以，也有很多改進的方法。

例如：

1. 應用地圖數據分層的思想，簡化地圖中道路的網路結構，也能提高路徑規劃的性能；

2. 起始點與目的地的方向考慮進去，擴展時，有方向性進行擴展，可以大大減少計算量和存儲空間；

3. 保存曾經的規劃記錄，也能達到快速檢索的能力。Google的地圖規劃好像就採用的這種思想；

4.合理優化路網結構，降低參與路徑計算的路網規模；

5.合理優化路徑規劃演算法數據結構，提高路徑計算效率；

實際上，平時中長距離的導航路徑規劃一般都是分層做的。譬如說你要從廣州到北京，開車怎麼走，當然不可能直接在路上規劃吧，這樣計算量太大了。比較理想的方法是，我先知道到底要經過多少城市，從每一個城市到下一個城市之間如何走才能用高速連接起來，你需要訪問的數據就小得多。當最後約束到一個區那麼大的地方的時候，直接上DP還是可以在可接受的時間內做出來的。

三、常見導航路徑規劃示例

1.打開地圖應用，獲取定位信息，自動獲取出發地



如果定位位置，不是出發地，可以點擊路線，手動輸入出發地

2.定位成功後，在搜索欄輸入目的地

確定目的地，一般地圖會顯示目的地周邊信息，然後點選詳細信息，確認導航到次目的地。

3.確定進行路線規劃

多種路徑可選，時間最少，路徑最短，不堵車，無收費站，有ETC，少走高速，沿途有休息區，或者必過某個城市等等。圖例展示的地圖，有一個嚴重缺陷，就是缺少路況信息，進行實施調整，實際上，從北京到秦皇島，選擇路線3，走進京津高速，路況較好，不堵車，有可能比系統默認推薦的路線1早到家。

B. 路徑分析的最優路徑分析方法

1．道路預處理
進行道路數據錄入時，往往在道路的交叉接合處出現重疊或相離的情況，不宜計算機處理。因此，需要對原始數據進行預處理，使道路接合符合處理要求。進行預處理時，取每條線段的首末節點坐標為圓心，以給定的閾值為半徑作圓域，判斷其他線段是否與圓域相交，如果相交，則相交的各個線對象共用一個節點號。
2．道路自動斷鏈
對道路進行預處理之後即可獲得比較理想的數據，在此基礎上再進行道路的自動斷鏈。步驟如下：
（1）取出所有線段記錄數n，從第一條線段開始；
（2）找出所有與之相交的線段並求出交點數m；
（3）將m個交點和該線段節點在判斷無重合後進行排序；
（4）根據交點數量，該線段被分成m+1段；
（5）第一段在原始位置不變，後m段從記錄尾開始遞增；
（6）重復（2）～（5），循環至n。
3．節點匹配
拓撲關系需使用統一的節點。節點匹配方法是按記錄順序將所有線段的始末點加上相應節點號，坐標相同的節點共用一個節點號，與前面所有線段首末點都不相同的節點按自然順序遞增1。
4．迪傑克斯特拉（Dijkstra）演算法
經典的圖論與計算機演算法的有效結合，使得新的最短路徑演算法不斷涌現。目前提出的最短路徑演算法中，使用最多、計算速度比較快，又比較適合於計算兩點之間的最短路徑問題的數學模型就是經典的Dijkstra演算法。
該演算法是典型的單源最短路徑演算法，由Dijkstra EW於1959年提出，適用於所有弧的權均為非負的情況，主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。該演算法的基本思想是：認為兩節點間最佳路徑要麼是直接相連，要麼是通過其他已找到的與起始點的最佳路徑的節點中轉點。定出起始點P0後，定能找出一個與之直接相連且路徑長度最短的節點，設為P1，P0到P1就是它們間的最佳路徑。
Dijkstra演算法的基本流程如下：首先將網路中所有節點分成兩組，一組包含了已經確定屬於最短路徑中點的集合，記為S（該集合在初始狀態只有一個源節點，以後每求得一條最短路徑，就將其加入到集合S中，直到全部頂點都加入到S中，演算法就結束了）；另一組是尚未確定最短路徑的節點的集合，記為V，按照最短路徑長度遞增的次序依次把第二組的頂點加入到第一組中，在加入的過程中總保持從源點到S中各頂點的最短路徑長度不大於從源點到V中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點距離就是從源點到此頂點的最短路徑長度，V中的頂點距離是從源點到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

C. 現在車載導航儀都是用的什麼尋徑演算法

一般有五種尋徑方法：1：推薦路線 2：最少收費 3：最短路徑 4：多走高速 5：少走高速

D. "最短路徑優先演算法"的優缺點

這個演算法一般出現在網路中，用於路由器的路由定址，我也只了解這方面的優缺點。如果不對，LZ就別看了。
所謂最短路徑，實際上說的是跳數。比如從一條路走會經過三個路由器，而從另一條路走，會經過兩個路由器，那麼此演算法會判斷2跳比3跳要短，但具體每一跳會花多長時間，經過多長路程，它不會考慮的。所以不一定演算法的最短路徑就是真實的最短。因為很多因素演算法沒有考慮，比如通信質量，網線長度……
C語言我只看過一個模擬現實的例子，大概是說公車走什麼路線長度最短，那個演算法考慮的是路線的長短，而不是跳數，優點當然就是路線的絕對最短，缺點就是沒考慮到其他現實因素，比如是否堵車（相當於網路通信質量）之類。
總之不管什麼演算法，考慮到的因素就是它的優點，反過來說，缺點往往就是演算法忽略的因素。
補充一下，如果說的不是演算法本身的優劣，而是細節的實現方面，那就是從時間復雜度和空間復雜度兩個方面去考慮了，希望對LZ有用。

E. 常用的導航/路徑規劃軟體都用到哪些演算法

一般都是分層做的。譬如說你要從廣州到北京，開車怎麼走，當然不可能直接在路上規劃吧，這樣計算量太大了。比較理想的方法是，我先知道到底要經過多少城市，從每一個城市到下一個城市之間如何走才能用高速連接起來，你需要訪問的數據就小得多。當最後約束到一個區那麼大的地方的時候，直接上DP還是可以在可接受的時間內做出來的。

F. 機場室內導航，可以實現嗎

基於藍牙iBeacon的室內導航是可以通過手機APP或者是小程序來實現的。

藍牙信標主動定位

由已嵌入或下載好SDK軟體包的智能終端設備（安卓/iOS手機、平板電腦等）和藍牙iBeacon設備、雲端數據傳輸、定位引擎和地圖伺服器組成。

工作原理：

1）在需要定位的區域內鋪設藍牙信標（iBeacon），一般至少需要鋪設3個藍牙信標（iBeacon）（因為定位演算法要求至少知道三個點的RSSI值才能准確地計算定位）；

2）藍牙信標（iBeacon）會每隔一定的時間廣播一個數據包到周圍；

3）當終端設備（智能手機、藍牙工卡等，為藍牙主機角色。）進入藍牙信標（iBeacon）的信號覆蓋范圍內，藍牙主機在執行掃描動作時，會間隔地接收到藍牙信標（iBeacon）廣播出來的數據包；

4）在藍牙主機接收到的廣播包時，會顯示該廣播包來自於哪一個藍牙信標；

5）（iBeacon）從機的 MAC 地址和當前的接收發送信號強度指示值 RSSI；RSSI 值是確定藍牙主機位置和藍牙信標（iBeacon）之間遠近距離的依據；

6）通過內置的定位演算法，以及和地圖引擎資料庫的交互，就可以測算出藍牙主機（終端設備）當前的具體位置。

G. 求最優路徑的演算法

以下是C寫的廣度優先的最短路徑窮舉法,希望對你有所幫助.
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define SIGHTS 4 //自定義景點個數為4，以後可以擴充

class Sight //景點類信息，以後可以擴充
{
public:
Sight(string name, string sd) { sname = name; sight_detial = sd; }
string Sight_Name() { return sname; }
string Sight_detial() { return sight_detial; }
protected:
string sname; //景點名稱
string sight_detial; //景點備注
};

struct SI
{
string sname; //景點名稱
int index; //景點編碼
};

SI SightInfo[SIGHTS];

map<int, string>results; //距離與路徑的映射結構體，可以動態擴充
vector<Sight> sights; //VECTOR向量保存景點信息，目前的作用只是保存
//但是其強大的功能完全可以應付以後的功能擴充

int MinDistanct = 50000; //假定最小距離為一個很大的值
string Sight_Names = "楓林園蛟橋園青山園麥廬園 "; //目標字元串
string Best_Path; //保存最佳路徑的STRING字元串

int DISTANCE[4][4] = { //查找表，用於儲存接點之間距離的信息
0, 1500, 2500, 2400,
1500, 0, 800, 0,
2500, 800, 0, 200,
2400, 0, 200, 0
};

bool connect[4][4] = { //查找表，用於儲存接點之間連通的信息
0, 1, 1, 1,
1, 0, 1, 0,
1, 1, 0, 1,
1, 0, 1, 0
};

void InitSights()
{ //初始化景點的各類信息
SightInfo[0].index=0;
SightInfo[0].sname = "麥廬園";
SightInfo[1].index=1;
SightInfo[1].sname = "楓林園";
SightInfo[2].index=2;
SightInfo[2].sname = "蛟橋園";
SightInfo[3].index=3;
SightInfo[3].sname = "青山園";

Sight s1("楓林園",
"楓林園以計算機系的理工科學生為主，是江西財經大學的唯一一個計算機學院");
sights.push_back(s1);
Sight s2("蛟橋園",
"蛟橋園是江西財經大學的會計、貿易等財務教學為主的教學樓群，為本部");
sights.push_back(s2);
Sight s3("青山園",
"青山園是江西財經大學的會計、貿易等財務教學為主的學生的宿舍群");
sights.push_back(s3);
Sight s4("麥廬園",
"麥廬園是江西財經大學的外語、藝術等人文科學為主的學習園地");
sights.push_back(s4);
}

void Find_Ways(string start, string end, int DIST, string path, int depth)
{ //遞歸調用，逐層尋找可連通的路徑，並以該路徑繼續重復循環查找，根據分析可以
//知道，所有最優解即最短路徑所經過的接點數目必定小於N，於是採用廣度優先遍歷，
//設置count為循環深度，當count大於SIGHTS時退出循環
int count = 1;
int i,j;
int start1 = 0,end1 = 0;
int distanct = 0, storeDist = 0;
string temp, target, pathway, storePath; //臨時儲存體，用於恢復遞歸調用後會
//改變的數據，以便之後無差別使用

count += depth;

if(count > SIGHTS)
return;

distanct += DIST; //距離累加

if(path=="") //第一次時，pathway初始化為第一個接點名稱
{
pathway = start;
pathway += "=>";
}
if(path!="")
pathway = path;

storeDist = distanct; //填充臨時儲存值
storePath = pathway;

for(i = 0; i < SIGHTS; ++i) //通過遍歷，查找景點名稱對應的編號
{
if(start == SightInfo[i].sname)
start1 = SightInfo[i].index;
if(end == SightInfo[i].sname)
end1 = SightInfo[i].index;
}

for(i = 0; i < SIGHTS; i++) //演算法核心步驟
{
if(connect[start1][i] != 0)
{
if(i==end1) //如果找到了一條路徑，則保存之
{
distanct += DISTANCE[start1][end1];
for(j = 0; j < SIGHTS; ++j)
{
if(end1==SightInfo[j].index)
target = SightInfo[j].sname;
}
pathway += target;
results.insert(make_pair(distanct, pathway)); //保存結果路徑信息

distanct = storeDist; //恢復數據供下次使用
pathway = storePath;
}
else //分支路徑
{
for(j = 0; j < SIGHTS; ++j)
{
if(i==SightInfo[j].index)
temp = SightInfo[j].sname;
}
pathway += temp;
pathway += "=>";
distanct += DISTANCE[start1][i];

Find_Ways(temp, end, distanct, pathway, count); //以該連通的分支
//路徑繼續遞歸調用，查找子層路徑信息。

distanct = storeDist; //恢復數據
pathway = storePath;
}
}
}
}

void Find_Best_Way()
{ //該函數建立在上述函數執行完畢之後，在map映射結構中通過對比每條路徑的長度，來
//選擇最優解
map<int, string>::iterator itor = results.begin();

while(itor!=results.end()) //尋找最小值
{
// cout<<"distanct = "<<itor->first<<endl;
if(itor->first < MinDistanct)
MinDistanct = itor->first;
itor++;
}

itor = results.begin();

while(itor!=results.end()) //尋找最小值所對應的整個路徑字元串
{
if(itor->first == MinDistanct)
Best_Path = itor->second;
itor++;
}
}

int main(int argc, char *argv[])
{
int choice;
size_t t1=0,t2=0;
string source, termination;

InitSights();

do{
cout<<"////////////////////////////////////////////////////////\n"
<<"**** 請輸入您所需要的服務號碼: ********\n"
<<"**** 1.楓林園介紹 ********\n"
<<"**** 2.蛟橋園介紹 ********\n"
<<"**** 3.青山園介紹 ********\n"
<<"**** 4.麥廬園介紹 ********\n"
<<"**** 5.查詢地圖路徑 ********\n"
<<"**** 6.退出查詢系統 ********\n"
<<"////////////////////////////////////////////////////////\n"
<<endl;

cin>>choice;

switch(choice)
{
case 1:
cout<<sights[0].Sight_Name()<<endl
<<sights[0].Sight_detial()<<endl;
break;

case 2:
cout<<sights[1].Sight_Name()<<endl
<<sights[1].Sight_detial()<<endl;
break;

case 3:
cout<<sights[2].Sight_Name()<<endl
<<sights[2].Sight_detial()<<endl;
break;

case 4:
cout<<sights[3].Sight_Name()<<endl
<<sights[3].Sight_detial()<<endl;
break;

case 5:
flag1:
cout<<"請輸入路徑的起點"<<endl;
cin>>source;
cout<<"請輸入路徑的終點"<<endl;
cin>>termination;

if((t1=Sight_Names.find(source,t1))==string::npos || (t2=Sight_Names.find(termination,t2))==string::npos)
{ //檢查輸入的數據是否含有非法字元
cerr<<"輸入的路徑結點不存在，請重新輸入:"<<endl;
goto flag1;
}
Find_Ways(source, termination, 0, "",0); //尋找所有可能解
Find_Best_Way(); //在所有可能解中找到最優解

cout<<"最佳路徑是："<< Best_Path <<endl
<<"最小路程為(米):"<< MinDistanct<<endl;

t1 = 0; //恢復字元串下標，以支持下次查詢
t2 = 0;
break;

case 6:
break;

default:
cerr<<"您的選擇超出了范圍，請重新輸入:"<<endl;
break;
}
}while(choice!=6);

system("pause");
return 0;
}

H. 求一個最優路徑演算法的思路

同意樓上，最長路徑是NPC問題，不存在多項式演算法。

證明是簡單的：
1、最長無環路問題的判定版本是「給定有向圖D和整數k，問D中是否存在長度大於或等於k的無環路」（這一表述對有權圖和無權圖都有效）。
2、將Hamilton路問題規約到最長無環路問題（的判定版本）是顯然的：輸入一個n頂點的有向圖D，直接問：有向圖D中是否存在長度大於等於n-1的無環路？

簡言之，對任意n頂點的有向圖D，假如能夠D中的找到最長無環路P，那麼就能立即知道D中是否存在Hamilton路（只需看P的長度是否為n-1即可），從而最長無環路問題是NPC。

小規模就直接DFS吧。大規模的時候DFS剪枝。不過確實不好做呀。

有向無圈圖的話可以用dijstra貪心，或者簡單用folyed演算法就可以了（把最小化變為最大化）。

有圈的話您……或者能縮圈么？可以考慮。總之比較復雜。

I. 「最少換乘、最少用時」，導航是如何幫你規劃路線的

首先是用啟發式演算法來規劃路線。以我們導航中常用的“A*演算法”和“Dijikstra演算法”為代表，從起點出發，以一定的步長展開節點。選擇值(如路徑長度)最小的節點作為擴展節點，擴展過程中需要考慮一些約束條件，如轉彎半徑的限制、風險障礙物的避開等，導致擴展角度不可能是全方位的。

要知道的是世界上使用最廣泛的定位系統是美國的全球衛星定位系統GPS。這是美國軍方從1970年開始研發建立的衛星定位系統。它於1994年完工。它由24顆衛星、一個地面控制站和幾個監測站組成，覆蓋全球98%的區域。用戶只要有GPS接收設備，就可以24小時免費享受定位系統提供的定位時間服務。基於這個原理，只要我們在智能手機上安裝好GPS晶元，晶元能夠接收衛星信號以及解算信息，就能夠確定位置了。