在矩阵中寻找最短路径的算法

2013-11-29 18:16:45
收藏：0
阅读：115
评论：1

我试图找到下面问题的算法，但我找不到。

您有一个矩阵，大小为10x6（如果重要）。 （x维度为10，y维度为6）。 算法接收两个点，打开点和目标点。 该数组充满了0和1，并且它应该找到它们之间1的最短路径，并返回这条路径上的第一个点（通向目标的下一个点）。 但是这里有个陷阱：

每个点仅可以获取以下点的值：

1.它上面的点。 2.它下面的点。 3.它左边的点。 4.它右边的点。

并且要使事情变得更加困难：对于每个点，其他点的值可能不同。例如：

1.开放点为0,0。 0,1的值为1； 2.开放点为0,2。 0,1的值为0。

我可以计算出该值，因此对您来说不应该有任何问题... 因此，如果您找到其他方法，则认为递归是解决它的唯一方法，则欢迎您。

解决方案应在LUA，C#或JAVA中提供。

点赞
用户3033731
用户3033731

你可以将你的矩阵简单地解释为一个图。每个元素 (i,j) 对应一个节点v(i,j)，仅当它们对应的元素相邻且均为1时，这两个节点才相连。

例如下面的矩阵有四个顶点v(0,0), v(0,1), v(1,0) 和 v(1,1)，边集为{v(0,0),v(0,1)}和{v(0,1),v(1,1)} (顶点v(1,0)是孤立的)。

1 1
0 1

由于你的图是无权图，你可以简单地使用广度优先搜索 (BFS) 来找到最短路径。伪代码请参见：http://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

你对矩阵中的每个元素都只知道它的相邻元素，这并不重要。当谈论图的话，这意味着每个顶点都知道它的邻居，这正是你在BFS中所需要的。使用不同的图搜索不同的起始点也不会使问题变得更加困难。

仅两点针对链接的伪代码：

  1. 它仅检查是否存在连接。如果你想要最短路径，你需要进行以下更改。当从它的邻居t中查看时添加新顶点u到队列中时，你必须在u处存储一个指向t的链接。当你最终找到目标时，回溯链接将给出最短路径。

  2. 使用set来存储哪些元素已经被访问是低效的。在你的情况下，只需要使用与输入矩阵大小相同的布尔矩阵来标记顶点是否被访问。

2013-11-29 19:01:49

作者:

用户3050072

用户3050072
推荐文章