解决这个迷宫的最佳算法？

3 回答

• 0

  它仍然可以用Dijkstra / A *解决，需要改变的是邻居的配置 .

  ---

  一点背景，第一：

  Dijkstra和A *是在图上制定的一般路径寻找算法 . 当我们在网格上移动一个角色而不是图形时，图形的位置可能不那么明显 . 但它仍然存在，构建图形的一种方法如下：

  • 图的节点对应于网格的单元格

  • 节点之间存在与相邻单元格对应的边缘 .

  实际上，在涉及它们之间的一些配置和转换的大多数问题中，可以构造相应的图形，并应用Dijkstra / A * . 因此，也可以解决诸如sliding puzzle，rubik's cube等问题，这些问题显然与在网格上移动的角色显着不同 . 但是它们具有状态，并且状态之间存在转换，因此可以尝试图搜索方法（这些方法，尤其是不知情的方法，例如Dijkstra _845307可以应用它们） .

  ---

  在您提到的问题中，图表与具有典型字符移动的图表没有太大区别：

  • 节点仍然可以是网格的单元格

  • 现在将存在从节点到节点的对应于有效运动的边缘（在边界或障碍物附近结束），在这种情况下，这些边缘将不总是与网格单元的四个空间直接邻居重合 .

  ---

  正如Tamas Hegedus在评论部分所指出的，如果使用A *，应该选择什么样的启发函数并不明显 .

  基于曼哈顿或欧几里德距离的标准启发式算法在这里无效，因为它们可能会高估与目标的距离 .

  一个有效的启发式算法是id（row！= destination_row）id（col！= destination_col），其中id是标识函数，id（false）= 0且id（true）= 1 .

  回复于 2024-05-05T17:41:50+08:00
• 1

  Dijkstra / A *很好 . 你需要的是仔细考虑你认为图形节点和图形边缘的内容 .

  站在蓝色单元格（让我们称之为 5,5 ），你有三个有效的举动：

  • 向右移动一个单元格（至 6,5 ）

  • 向左移动四个单元格（至 1,5 ）

  • 向上移动五个单元格（至 5,1 ）

  请注意，您不能从 5,5 转到 4,5 或 5,4 . 将相同的推理应用于新节点（例如，从 5,1 您可以转到 1,1 ， 10,1 和 5,5 ），您将获得运行Dijkstra / A *的图表 .

  回复于 2024-05-05T17:41:50+08:00
• 0

  您需要评估每个可能的移动并采取最小距离的移动 . 类似于以下内容：

  int minDistance(int x, int y, int prevX, int prevY, int distance) {
    if (CollionWithBorder(x, y)  // can't take this path
      return int.MAX_VALUE;
  
    if (NoCollionWithBorder(x, y)  // it's OK to take this path
    {
      // update the distance only when there is a long change in direction
      if (LongDirectionChange(x, y, prevX, prevY))
        distance = distance + 1;
    )
  
    if (ReachedDestination(x, y)  // we're done
      return distance;
  
    // find the path with the minimum distance      
    return min(minDistance(x, y + 1, x, y, distance),  // go right
               minDistance(x + 1, y, x, y, distance),  // go up
               minDistance(x - 1, y, x, y, distance),  // go down
               minDistance(x, y - 1, x, y, distance)); // go left
  }
  
  bool LongDirectionChange(x, y, prevX, prevY) {
    if (y-2 == prevY && x == prevX) ||(y == prevY && x-2 == prevX)
      return true;
    return false;
  }
  

  这是假设不允许对角线移动 . 如果是，请将它们添加到min（）调用：

  minDistance(x + 1, y + 1, distance),  // go up diagonally to right
    minDistance(x - 1, y - 1, distance),  // go down diagonally to left
    minDistance(x + 1, y - 1, distance),  // go up diagonally to left
    minDistance(x - 1, y + 1, distance),  // go down diagonally to right
  

  回复于 2024-05-05T17:41:50+08:00