标签归档：最短路径

Dijkstra算法求解最短路径分析
广度优先搜索解决“营救公主”问题
迷宫营救公主算法

Dijkstra算法求解最短路径分析

作者：童燕群 | 发布日期：七月 12, 2014 | 阅读次数（14,924） | 评论（1）

最短路径是图论算法中的经典问题。图分为有向图、无向图，路径权值有正值、负值，针对不同的情况需要分别选用不同的算法。在维基上面给出了各种不同的场景应用不同的算法的基本原则：最短路问题。

针对无向图，正权值路径，采取Dijkstra算法。

Dijkstra_Animation

如上图，是求a到b的最短路径，这里并不限定b节点，修改为到任意节点的路径，问题是完全一样的。

阅读全文 »

(4.92分 - 13票)

Loading ... | 归档目录：Java, 算法数据结构 | 同时打有标签：Dijkstra算法, 迪杰斯特拉算法 |

广度优先搜索解决“营救公主”问题

作者：童燕群 | 发布日期：十月 14, 2013 | 阅读次数（10,259） | 评论（6）

在之前的一篇文章（迷宫营救公主算法）中提供了一个半成品的解决方案，之所以说他是半成品，是因为首先选择的算法就不对，采用的是深度优先搜索，其次也没有真正的用对深度优先算法，走过的点应该标记为已经走过，而不应该重复遍历该节点。下面的文章对于广度优先和深度优先两种算法的解释非常到位。今天准备把这个问题再完整的用正确的算法解答一遍。

文章链接：【图论】广度优先搜索和深度优先搜索。

就营救公主的问题而言，这里不再重复描述问题了，请点击这里查看题目分析：链接。这次选用广度优先算法来解决该问题。上面的算法介绍文章中对该算法已经分析得非常清晰了。先给解决本问题的算法伪代码：

这里每个节点有三种状态：

阅读全文 »

(5.00分 - 3票)

Loading ... | 归档目录：Java, 算法数据结构 | 同时打有标签：图, 广度优先, 搜索, 深度优先, 营救公主 |

迷宫营救公主算法

作者：童燕群 | 发布日期：八月 10, 2013 | 阅读次数（10,719） | 评论（2）

今天下班前在公司的技术题库中看到这道题目，思路很快就有了，递归遍历每一条可能的路径，然后找出最短的路径。回家把代码写出来了。发现算法效率实在是太低了，在矩阵较小的时候还好，当矩阵稍微大一点时根本算不过来，感觉复杂度像是O((N*M)^(N*M))这个数值太庞大了，也完全没有意义。公主等到花儿都谢啦。。

貌似这位同学的算法还不错，还没来得及研究，先做个链接：http://blog.csdn.net/joseph_1118/article/details/9390301

应付较小的矩阵下面的方法还是能蒙混过关的。先发到这里，后面再继续研究优化。题目和代码都在一起：

/**
* 公主被魔王抓走了，王子需要拯救出美丽的公主。他进入了魔王的城堡，魔王的城堡是一座很大的迷宫。
* 为了使问题简单化，我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙，王子不能通过。王子只
* 能移动到相邻（上下左右四个方向)的方格内，并且一秒只能移动一步。地图由’S’，’P’，’.’，’*’
* 四种符号构成，’.’表示王子可以通过，’*’表示墙，王子不能通过；’S’表示王子的位置；’P’表示公主
* 的位置；T表示公主存活的剩余时间，王子必须在T秒内到达公主的位置，才能救活公主。如下图所示：
*/

阅读全文 »

(5.00分 - 9票)

Loading ... | 归档目录：Java, 算法数据结构 | 同时打有标签：营救公主 |