算法来寻找以矩阵的最短路径 [英] Algorithm to find the shortest path in a matrix
问题描述
我试图找到一个算法以下问题，但我不能。
I tried to find an algorithm for the following problem, but I couldn't.
您有一个矩阵，10X6如果它很重要。 （关于Y尺寸X尺寸6 10）。 该算法接收2点，开点和目标点。 该阵列是满的0和1的，它应该发现1的最短路径在它们之间，并返回第一点在此路径（在途中的下一个点到目标）。 但这里的渔获：
you have a matrix, 10X6 if it matters. (10 on x dimension 6 on y dimension). the algorithm receives 2 point, the opening point and the target point. the array is full of 0's and 1's and it should find the shortest path of 1's between them, and return the first point in this path (the next point in the way to the target). But here's the catch:
的每个点可以得到仅由以下各点的值：
each point can get the value only of the following points:
- 在它上面的点。
- 下方的点。
- 在左边的地步。
- 点它的权利。
和使事情更加困难：每点，其他点的值可能会有所不同。例如：
and to make things even harder: for every point, the value of other point may be different. for example:
- 开盘点位是0,0。的0,1的值是1;
- 开盘点位是0,2。的0,1的值是0。
我可以计算的价值，所以应该没有关系的，你... 因此，我认为解决这个问题是递归的，因为最后一个条件，但如果你找到另一种方式，欢迎您的唯一途径。
I can calculate the value so it shouldn't matter for you... So I thought the only way to solve it is with recursion because of the last condition but if you find another way, you're welcome.
该解决方案应该是 LUA C＃或 JAVA
The solution should be in LUA, C# or JAVA.
推荐答案
您可以简单地间preT你的矩阵图。每一个细胞（I，J）对应于节点V（I，j）和两个节点，如果如果其相应的小区是邻居和都设定为1的仅连接
You can simply interpret your matrix as a graph. Every cell (i,j) corresponds to a node v(i,j) and two nodes are connected if an only if their corresponding cells are neighbors and both are set to 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）分离）。
The example matrix below has the four vertices v(0,0), v(0,1), v(1,0), and v(1,1), with edges {v(0,0),v(0,1)} and {v(0,1),v(1,1)} (the vertex v(1,0) is isolated).
1 1
0 1
由于您的图形是不加权的，你可以简单地使用广度优先搜索（BFS）找到最短路径。对于伪code见： http://en.wikipedia.org /维基/广度first_search＃伪code
您的限制，在一个矩阵中的每个条目只知道它的邻接项无所谓。在谈到图形，这意味着曾经顶点知道它的邻居，而这正是你需要的BFS。使用从不同的起点搜索并不能使该问题更难或者当不同的曲线图。
Your restriction that every entry in a matrix only knows its neighboring entries does not matter. When talking about graphs, this means that ever vertex knows its neighbors, which is exactly what you need in the BFS. Using a different graph when searching from different starting points does not make the problem harder either.
就在两个意见的poseudo code上面链接：
Just two comments to the poseudocode linked above:
-
它只是检查是否有连接或不。如果你确实想拥有的最短路径，您需要更改如下。当一个新的顶点u被添加到队列从它的邻居牛逼看时，你要存储一个链接ü指向吨。当你终于找到你的目标，下背部的链接给你的最短路径。
It only checks whether there is a connection or not. If you actually want to have the shortest path, you need to change the following. When a new vertex u is added to the queue when seen from its neighbor t, you have to store a link at u pointing to t. When you finally found your target, following back the links gives you the shortest path.
使用一组存储哪些元素已经访问是低效的。在你的情况下，只需使用同样大小的布尔矩阵的输入矩阵，以纪念顶点访问。
Using a set to store which elements are already visited is inefficient. In your case, just use a boolean matrix of the same size as your input matrix to mark vertices visited.
这篇关于算法来寻找以矩阵的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
