2D矩阵中两个位置之间的最短路径
本文关键字:位置 两个 之间 最短路径 2D | 更新日期: 2023-09-27 18:20:37
这里有一个代码,它从索引[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;
}
}
您的算法似乎是一个简单的递归洪泛填充搜索。它将搜索每个位置,然后检查周围的所有位置。您已经正确地为网格边缘和已经搜索的位置实现了"提前退出",看起来您将矩阵值0视为"墙",因为它们也会触发"提前退出"。
你提出这个问题的方式很不传统。您提到搜索值9。这种类型的搜索大多与到达特定的目标位置有关(例如,值9在矩阵的位置4,4中),对于这种搜索类型,a*算法或Dijkstra修改将在找到目的地之前搜索较少的位置。
原则上,您需要指定在这种情况下什么是"更好的"?对于我提到的搜索类型,通常的判断是,减少搜索位置的数量"更好"。然而,在某些情况下,代码的简单性可能更重要,或者不需要知道路径是什么(正如您的示例所暗示的那样),有时您需要有保证的最短路径,有时您只想要一个合理的体面路径。这些案例中的每一个以及更多案例都经过了详细的考虑!
你可能还想重新表述你的问题,因为你所做的并不是严格意义上的路径探索。你提供的算法只指示路径是否存在,而不是该路径的步骤
特定递归函数的扩展将导致它垂直向下搜索,直到碰到墙或网格边缘。然后它将向右搜索一个正方形,然后再次尝试向下搜索。如果你打印出搜索到的位置,你会很快明白我的意思,我说这种特定的算法将以一种非常古怪的方式进行搜索,并且只对"碰巧"出现在扩展模式早期的搜索目的地有效。