在二维数组中查找最短路径 (Javascript)

Question

我正在尝试实现一个算法，该算法可在以下二维数组中找到最短路径（从左上角到右下角）：

      [ [ 'A', 'A', 'A', 'B', 'A' ],
        [ 'B', 'B', 'B', 'B', 'B' ],
        [ 'A', 'B', 'A', 'A', 'A' ],
        [ 'A', 'B', 'B', 'B', 'B' ],
        [ 'A', 'A', 'A', 'A', 'A' ] ]

规则是，路径必须在A和B之间交替。

输出必须是一个数字，指定穿过数组所需的最小步数。（在示例中，期望的输出为13）

有没有人知道一个简单的图实现，可以帮助我解决这个问题？

- Boris Grunwald

---

从哪里到哪里的最短路径？ - nick zoum

数组中每个值是什么？您能提供一下您期望从提供的数据中得到的样本输出吗？ - Dipak

你能否提供更多的输入来解释你的问题？ - Kartikeya Sharma

抱歉，它是从左上角到右下角的。 - Boris Grunwald

我已经更新了问题，请告诉我是否需要更多信息。 - Boris Grunwald

Answer 1

因为它代表了一个不定向的无权图，所以您可以简单地使用BFS：

const m =
  [ [ 'A', 'A', 'A', 'B', 'A' ],
    [ 'B', 'B', 'B', 'B', 'B' ],
    [ 'A', 'B', 'A', 'A', 'A' ],
    [ 'A', 'B', 'B', 'B', 'B' ],
    [ 'A', 'A', 'A', 'A', 'A' ] ]

let successors = (root, m) => {
  let connectedCells = [
    [root[0] - 1, root[1]],
    [root[0], root[1] - 1],
    [root[0] + 1, root[1]],
    [root[0], root[1] + 1]
  ]

  const validCells = connectedCells.filter(
    (cell) => (
      cell[0] >= 0 && cell[0] < m.length 
      && cell[1] >= 0 && cell[1] < m[0].length)
  )

  const successors = validCells.filter(
    (cell) => (m[cell[0]][cell[1]] !== m[root[0]][root[1]])
  )

  return successors
}

const buildPath = (traversalTree, to) => {
  let path = [to]
  let parent = traversalTree[to]
  while (parent) {
    path.push(parent)
    parent = traversalTree[parent]
  }
  return path.reverse()
}

const bfs = (from, to) => {
  let traversalTree = []
  let visited = new Set
  let queue = []
  queue.push(from)

  while (queue.length) {
    let subtreeRoot = queue.shift()
    visited.add(subtreeRoot.toString())

    if (subtreeRoot.toString() == to.toString()) return buildPath(traversalTree, to)

    for (child of successors(subtreeRoot, m)) {
      if (!visited.has(child.toString())){
        traversalTree[child] = subtreeRoot
        queue.push(child)
      }
    }
  }
}


console.log(bfs([0,0], [4,4]).length) // => 13

- akurtser

Answer 2

你可以直接使用网格作为图形，而无需将其转换为常规的图形邻接列表表示。

因此，每对（行、列）都是一个节点，

只有当2个节点是相邻且具有不同的值时，您才能进入下一个节点，

邻接列表的目的是高效地获取相邻节点，但是对于网格单元格，您只需始终检查所有4个方向并处理存在的节点即可。

示例代码：

最初的回答：

let A = [ [ 'A', 'A', 'A', 'B', 'A' ],
        [ 'B', 'B', 'B', 'B', 'B' ],
        [ 'A', 'B', 'A', 'A', 'A' ],
        [ 'A', 'B', 'B', 'B', 'B' ],
        [ 'A', 'A', 'A', 'A', 'A' ] ];
  
let visited = new Set();
let rows = A.length;
let columns = A[0].length;
let distance = Array(rows).fill().map(() => Array(columns).fill(-1));
distance[0][0]=0;
let Q = []; //Queue
Q.push([0,0]);
visited.add([0,0].toString());

let dr = [-1,1,0,0]; 
let dc = [0,0,-1,1]; 

while(Q.length > 0)
{
 let cur = Q.shift();
 let row = cur[0];
 let col = cur[1];
 
 for(let k=0; k<4; k++)
 {
  let newRow = row + dr[k];
  let newCol = col + dc[k];
  
  if(!visited.has([newRow,newCol].toString()) && newRow>=0 && newCol >=0 && newRow < rows && newCol < columns && A[newRow][newCol] !== A[row][col])
  {
   visited.add([newRow,newCol].toString());
   distance[newRow][newCol] = distance[row][col] + 1;
   Q.push([newRow,newCol]);
  }
 }
}

if(distance[rows-1][columns-1] === -1)console.log("Path does not exist");
else console.log(distance[rows-1][columns-1]);

- Photon

Answer 3

一种解决问题的方法是首先将您的二维数组表示为一个图，其中每个字母都是一个节点，如果它们代表的字母在数组中相邻且不同（一个是A，一个是B），则两个节点之间存在一条边。
然后，您只需要使用经典的最短路径算法，例如Dijkstra或A*，来查找图的两个节点之间的最短路径。这相当于找到数组中两个字母之间的最短路径。

编辑：以下是回答您在评论中提出的问题的伪代码。

nodes = init_a_2d_array_of_graph_nodes(ARRAY_WIDTH, ARRAY_HEIGHT)
for i from 1 to ARRAY_WIDTH:
    for j from 1 to ARRAY_HEIGHT:
        if i < ARRAY_WIDTH and array[i][j] != array[i+1][j]:
            add_edge(nodes[i][j], nodes[i+1][j])
        if j < ARRAY_HEIGHT and array[i][j] != array[i][j+1]:
            add_edge(nodes[i][j], nodes[i][j+1])

首先，您需要初始化一个图形结构。如果您不知道如何做到这一点，请在网上查找，肯定有很多方法可以实现，这是相当简单的。

然后，您需要为数组中的每个字母创建一个节点。将这些节点存储在2D数组中很方便，这样您就可以轻松地找出哪个字母对应于图中的哪个节点。

然后，对于所有相邻的字母，您需要检查这些字母是否不同（这是在两个if条件中检查的）。如果是这种情况，则使用边连接这两个节点。

之后，您需要在源节点和目标节点之间的图上运行最短路径算法。Dijkstra算法是最好的最短路径算法入门方式，它是最广泛使用的，并且在大多数情况下都足够快。

最后，一旦您拥有路径，您需要检索图中节点的索引（行和列），这将为您提供字母数组中对应的路径。

如果您仍有不理解的地方，请随时再次评论。

- m.raynal

---

这正是我现在正在尝试做的事情。我现在遇到的问题是，找不到一种从数组创建邻接表的方法。 - Boris Grunwald

Answer 4

有谁知道一个简单的图表实现可以帮助我解决这个问题吗？ Dijkstra算法用于查找两个节点之间的最短路径。您的二维数组中的每个位置代表一个节点，边缘从满足“交替”规则的周围节点动态派生。

您可以使用双向搜索和目标度量（A*）进一步优化它以适应您的用例。

- Bergi

---

在我看来，对于无向非加权图，使用BFS会更简单（并且在任何意义下——渐近地更快）。 - akurtser