地图求百度地图最短路径算法是本地做还是云端

来源：蜘蛛抓取(WebSpider) 时间：2015-04-02 18:15 标签： 百度地图最短路径算法
后使用快捷导航没有帐号？
暂时没有人问过相似的问题，你可以做第一个提问题的人
查看: 5060|回复: 5
百度地图API能提供多条两点间的路径吗？
百度地图API能提供多条两点间的路径吗？（除了最短距离、最少时间、避开高速）
也就是如果遇到规划的路线在实际中不可用时怎么办？还能规划出其他路线吗？比如比最短距离稍微长点的路线能给出吗？
不太明白什么意思？需求是跟百度地图客户端一样，出现多条路线吗？同时出现最短时间、不拥堵这种？
coralreef1217
& & 不是，就是比如在实际导航中发现规划出的最短路径中有一段无法通行，能不能给出一条不包含这个路段的另一条到目的地路径。现在百度API只能给出最少时间、最短距离、避开高速三个策略，也就是能得到三条线路，要是这三条线路都包含这一不能通行的路段怎么办？我的意思就是能否再给出多一些路径，从中筛选出不包含那条不能通行的路段的路径。
这个跟目前的api接口没有关系了，是云端干预的问题了，临时避让某条路段。目前不支持。
coralreef1217
哦，谢谢回复。:)
在驾车导航的时候得到results后不是可以用getNumPlans()获取方案的个数吗？为什么都是只有一条方案？能否提供稍微多点的方案好让我们能够进行一下选择呢？还有每条方案的路线也是只有一条。
var num=results.getNumPlans();
alert(num);
// 获取第一条方案
var plan = results.getPlan(0);
var num1=plan.getNumRoutes() ;
alert(num1);
// 获取方案的驾车线路
var route = plan.getRoute(0);
num和num1都是1，能不能再多提供一些？
Powered by1317人阅读
搜索（10）
以前所接触过的最短路径算法是dijkstra或floyd之类的，都是在已知每两点之间距离的情况下求最短路的。
那么想一下这样的案例
给你一个地图，类似于迷宫一样，中间有些障碍物，再给定起点终点，求该两点间最短路，显然，上述两种算法就不适用了，因为提到的迷宫，我们可能会很容易想到广搜bfs，但一次bfs下来实际上求出了起点到所有点的最短路径，但我们只想知道它与终点间的最短路径，也就是说这个方案里有很多冗余的操作。
说到这里，该步入正题，介绍A*算法。
A*算法；A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好。(取自百度百科)
何谓直接搜索方法，即不进行任何预处理直接进行搜索的方法。
那么它为何可以称为最有效的直接搜索方法呢，我们看到上文说到一个估价值与估价函数。
所以有这么一个式子
f(n) = g(n) + h(n)
先记住这个式子，在讨论这个式子之前，先谈点题外话。
我们都接触过贪心思想，即在对问题求解时，总是做出在当前看来是最好的选择。
从起点开始，它可走的地方是周围的8个点(最多)，平常广搜时多个可能是平等对待，全部考虑。
那么？我们可不可以运用贪心的思想从8个点中选出一个最有可能达到最短路的点来优先进行操作呢？
当然可以，这样我们就是有针对性的搜索，而不是盲目搜索了。
有的道友可能会说了，这样贪心下来求出的只能是接近于最优解的相对最优解，并不能保证一定最优，没错，事实的确是这样。
那么这样就行不通了，因为我们的目的是很明确的，要的是最短路径。
但是往常的贪心算法都是选取当前状态下最好的选择，至于次好选择等等全部就丢掉了，那如果我们仍然保留这些选择，仍与后来的可能进行比较呢，这样就保证最后的解一定是最优解了。
如何将所有可能性都保留下来继续参与后来的比较呢，优先队列是一个不错的法子。
1. 从A开始，将其周围可走且未标记的点，全部加入队列，然后标记A点
2. 从队列中选取优先度最高的点B
3. 对B重复1操作，直到到达终点为止
但优先度如果获得呢，现在我们回到这个式子
f(n) = g(n) + h(n)
g(n)为从起点到点n所花费的代价值
h(n)为点n到终点所花费代价的估价值
两者之和 f(n)就是点n的优先值
例如，对几何地图进行求解时，可以将从起点到点n走的步数作为g(n)，将点n到终点的几何距离作为h(n)估价值，那么此时，f(n)的值越小，优先度越高。
下面贴代码
#include&iostream&
#include&stdio.h&
#include&algorithm&
#include&math.h&
#include&queue&
#include&functional&
#include&set&
using namespace std;
const int N = 10009;
int v[N][N] = {};
int dx[] = {1,1,1,0,0,-1,-1,-1};
int dy[] = {1,0,-1,1,-1,1,-1,0};
int f[N*N];
struct Node
int x,y,f,g;
struct Nodecmp
bool operator() (const Node &a, const Node &b)
return a.f & b.f;
int leng(Node a, Node b)
return sqrt((a.x - b.x)*(a.x - b.x)
+ (a.y - b.y)*(a.y - b.y));
void print(int nid, int n)
if(nid == -1)
print(f[nid],n);
printf("%d %d\n",(nid-1)/n, nid-(nid-1)/n*n);
bool a_start(Node s, Node e, int n)
if(!v[e.x][e.y])
return false;
memset(f, 0, sizeof(f));
priority_queue&Node, vector&Node&, Nodecmp&
int eid = e.x * n + e.y;
f[s.x * n + s.y] = -1;
while(!q.empty())
Node now = q.top();
int nid = now.x * n + now.y;
if(nid == eid)
print(nid, n);
return true;
for(int i=0;i&8;i++)
t.x = dx[i] + now.x;
t.y = dy[i] + now.y;
int tid = t.x * n + t.y;
if(v[t.x][t.y] && f[tid] == 0)
t.g = now.g + 1;
t.f = t.g + leng(t, e);
q.push(t);
return false;
int main()
cin&&n&&s.x&&s.y&&e.x&&e.y;
for(int i=1;i&=n;++i)
for(int j=1;j&=n;++j)
cin&&v[i][j];
if(!a_start(s,e,n))
cout&&"无法到达"&&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：137340次
积分：3080
积分：3080
排名：第10022名
原创：165篇
评论：43条
阅读：2463
文章：99篇
阅读：88184
(2)(6)(2)(12)(3)(5)(5)(2)(3)(2)(13)(12)(24)(36)(14)(10)(3)(1)(3)(3)(13)工具类服务
编辑部专用服务
作者专用服务
矢量地图中一种求最短路径的快速算法
在分析总结了经典Dij kstra-算-法的基础上,提出了求最短路径的一种快速实现算法,根据算法的复杂度与网络节点数n成线性关系即O(n)的特点,给出了该算法的具体实现结构.
作者单位：
株洲县职业中等专业学校,湖南株洲,412100
长沙民政职业技术学院软件系,湖南长沙,410083
年，卷(期)：
机标分类号：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
JAVA实现地图最短路径问题
下载积分：0
内容提示：JAVA实现地图最短路径问题
文档格式：DOC|
浏览次数：125|
上传日期： 18:11:39|
文档星级：
全文阅读已结束，如果下载本文需要使用
 0 积分
下载此文档
该用户还上传了这些文档
JAVA实现地图最短路径问题
官方公共微信503 Service Temporarily Unavailable
503 Service Temporarily Unavailable
openresty/1.9.7.4

我要回帖

更多关于 百度地图最短路径算法 的文章

 

随机推荐