优化这个迷宫解算器

Question

我编写了解决迷宫问题的C#代码。它可以工作，但我想优化它，以便它可以给我所有的路径。为了解决迷宫，我在零上行走，并假定决赛达到-3。

const int MAZE_SIZE = 6;
static int[] allowed_move_row = { 0, -1, 0, 1 };
static int[] allowed_move_col = { 1, 0, -1, 0 };
const int MAX_ALLOWED_MOVES = 4;
static int[,] Optmaze = new int[MAZE_SIZE, MAZE_SIZE];
static int[,] maze  = new int[MAZE_SIZE, MAZE_SIZE] { 
                       { -2 , 0  ,  0   , 0  ,  0  ,  -1 },
                       { -1 , 0  , -1   , 0  , -1  ,  0 } ,
                       { -1 , -1 , -1   , 0  ,  0  ,  0 } ,
                       { -1 , 0  , -1   , -1 ,  0  ,  -1 },
                       { -1 , -1 , -1   , 0  ,  0  ,  0 } ,
                       { -1 , 0  , -1   , -3 ,  0  ,  0 } };

static bool Solve(int previous_row, int previous_col, int next_step_no)
{
     for (int i = 0; i < MAX_ALLOWED_MOVES; i++)
     {
          int col = previous_col + allowed_move_col[i];
          int row = previous_row + allowed_move_row[i];
          if (col < 0 || col >= MAZE_SIZE) 
              continue;
          if (row < 0 || row >= MAZE_SIZE) 
              continue;

          if (maze[row, col] == -3)
              return true;

          if (maze[row, col] != 0) 
              continue;

          maze[row, col] = next_step_no;

          if (Solve(row, col, next_step_no + 1))
              return true;

          else maze[row, col] = 0;
     }
            return false;
}

static void Main(string[] args)
{
    Print(maze);
    Console.WriteLine("-----------Solve-------------");
    if (Solve (0, 0, 1) )
        Print( maze);
    else
        Console.WriteLine("No Result");
}

static void Print(int[,] maze)
{
    for (int i = 0; i < maze.GetLength(0); i++)
    {
        for (int j = 0; j < maze.GetLength(1); j++)
        {
            Console.Write(" " + String.Format("{0,3}",maze[i, j]) + " ");
        }
        Console.WriteLine();
    }
}

输出：

-2 0 0 0 0 -1 -1 0 -1 0 -1 0 -1 -1 -1 0 0 0 -1 0 -1 -1 0 -1 -1 -1 -1 0 0 0 -1 0 -1 -3 0 0 -----------Solve------------- -2 1 2 3 0 -1 -1 0 -1 4 -1 0 -1 -1 -1 5 6 0 -1 0 -1 -1 7 -1 -1 -1 -1 0 8 9 -1 0 -1 -3 11 10

Answer 1

行走所有的零确实不是最优的。一个好的第一个优化是优先在零上行走，这会使你更接近终点。

要做到这一点，在每一步，计算毕达哥拉斯之间的x，y坐标之间的x，y坐标，你要考虑步行到，和x，y坐标的数组条目包含-3。这将是步行去那个广场的费用。存储所有计算出来的成本，这样你就不必重新计算它们了。

然后，继续优先选择成本最低的下一个方块，直到你到达终点或死胡同。在死胡同的情况下，只需返回，并选择下一个成本最低的广场尚未通过。要做到这一点，您将需要保留路径层次结构的一些概念，即哪些步骤将导致下一个潜在步骤。自定义节点类型将为您完成此操作。

如果你已经走了这么远，那就恭喜你！您有一个基本的A*路径查找算法。关于实现此算法的有用指南，我建议使用这一资源。

对A*效率还有进一步的改进，例如跳点搜索算法，这对于更多的开放空间是最好的。