二维矩阵中两个位置之间的最短路径

Question

这里是从索引[0,0]寻找目标，例如值'9'执行路径查找的代码。 BFS或DFS应该比下面的算法做得更好吗？任何建议更好的算法来完成相同的？

using System; 

public class Test 
{ 
    public static int[,] matrix = 
     { 
      {1, 2, 8, 4}, 
      {3, 0, 3, 4}, 
      {4, 0, 2, 3}, 
      {5, 0, 32, 9} 
     }; 

    public static int[,] solution = new int[4,4]; 


    public static void Main() 
    { 
     int rows = matrix.GetLength(0); 
     int cols = matrix.GetLength(1); 

     FindPath(matrix, 9, rows, cols); 
     // your code goes here 
    } 

    public static void FindPath(int[,] matrix, int destination, int rows, int cols) 
    { 
     bool[] visited = new bool[rows * cols]; 

     for(int i=0; i < rows; i++) 
     { 
      for(int j =0; j < cols; j++) 
      { 
       solution[i,j] = 0;     
      } 
     } 

     for(int i=0; i < rows*cols; i++) 
     { 
      visited[i] = false; 
     } 

     CountPath(0, 0, visited, rows, cols, 9); 


     for(int i=0; i < rows; i++) 
     { 
      for(int j =0; j < cols; j++) 
      { 
       Console.Write(" " + solution[i,j]); 
      } 

      Console.WriteLine(""); 
     } 
    } 

    public static bool CountPath(int row, int col, bool[] visited, int rows, int cols, int destination) 
    { 
     if(row < 0 || row >= rows || col < 0 || col >= cols || visited[row * cols + col] || matrix[row,col] == 0) 
     { 
      Console.WriteLine("False..."); 
      return false; 
     } 
     Console.WriteLine(matrix[row,col]); 
     Console.WriteLine(matrix[row,col]); 


     if(matrix[row,col] == destination) 
     { 

      solution[row, col] = matrix[row,col]; 
      Console.Write("Found\n"); 
      return true;  
     } 

     visited[row * cols + col] = true; 
     solution[row, col] = matrix[row,col]; 

     Console.WriteLine(row); 
     Console.Write(col); 
     Console.WriteLine("-------------"); 

     bool hasdestination = CountPath(row + 1, col, visited, rows, cols, destination) || 
     CountPath(row , col + 1, visited, rows, cols, destination) || 
     CountPath(row - 1, col, visited, rows, cols, destination) || 
     CountPath(row , col - 1, visited, rows, cols, destination); 

     if(!hasdestination) 
     { 
      Console.WriteLine("No luck go back..."); 
      solution[row, col] = 0; 
      return false;   
     } 

     return true; 
    } 
} 

Answer 1

你的算法似乎是一个简单的递归洪水填充搜索。它会搜索每个位置，然后检查所有周围的位置。 您已经正确实现了网格边缘和已搜索位置的“早出”，并且您将矩阵值0视为“墙”，因为它们也会触发“早出”出口。

你说这个问题的方式是非常规的。您提到搜索值9.大多数搜索此类型涉及到达特定目标位置（例如，值9位于矩阵的位置4,4），并且对于该类型的搜索，A *算法或Dijkstra在找到目的地之前，修改将搜索更少的位置。

原则上，您需要指定在这种情况下什么会更好？我提到的搜索类型的通常判断是减少搜索的地点数量是“更好的”。然而，有些情况下代码的简单性可能更重要，或者没有必要知道路径是什么（就像你的例子似乎暗示的那样），有时你需要保证的最短路径，有时候你只需要一个合理的路径。这些案例中的每一个以及更多都已经被详细考虑了！

您可能还想更改您的问题，因为您所做的并不是严格的路径寻找。您提供的算法仅指示路径是否存在，而不是该路径的步骤。

扩展您的特定递归函数将导致它垂直向下搜索，直到它碰到墙或网格边缘。然后它将搜索右边的一个方格，然后再次尝试向下。如果您打印出搜索到的位置，您会很快看到我说的这个特定算法将以非常古怪的方式进行搜索时的意思，并且只会对于在扩展模式中提前发生的搜索目标有效。