室内导航路径最优算法

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芯片，芯片能够接收卫星信号以及解算信息，就能够确定位置了。