2D阵列路径查找

Question

我想找到2D数组的两个索引之间的最小加权路径。我曾尝试实现Dijkstra的最短路径算法和A*，但我做不到。下面是一个例子。我想给出路径的起点和终点，路径应该由算法返回。

0 25 8 8 9

51 27 9 8

9 825 7 8

8 82 2 29

9 7 6 327

8 8 6 5 3 5

有人能推荐其他算法或指导我有关算法的知识吗？

我已经研究了好几天了，我认为这根本不是一个具有挑战性的问题。但我发了脾气，无法思考健康。例如，我甚至不明白a*和dijkstra最短的路径是否与我想做的事情直接相关。或者它们适用于0和1之类的结构，如果有墙，你就不能从那里通过，如果没有，你就可以。在我的问题中，你可以从任何地方通过，但我想找到成本最低的路径等。

Answer 1

将问题建模为"适合"算法设计：
试着首先从你的网格中构建一个图，这可能会帮助你理解这些算法并实现它们。由于这两种算法都是为图[可以建模网格]设计的，我认为当你在"通用图"上实现它们并为你的特定问题构建图时，你可能会发现更容易理解这些算法。

您的图形将是G = (V,E)，其中V = { (i,j) | (i,j) is a possible index) }[网格中的所有正方形]和E = { (v,u) | v and u are adjacent vertices on the grid }。
您还需要边上的加权函数。w:E->N。它将是CCD_ 5[与CCD_。

现在，用您的facorite语言为图G实现dijkstra。最短路径的权重是dijkstra+matrix[source.x][source.y]找到的路径的权重[因为我们没有将该值添加到最短路径上的任何边]。

要找到实际路径，不仅要找到它的重量-你还需要持有一个map:V->V，它将从每个顶点映射到发现它的顶点。类似于本文中解释的想法。

从更简单的Dijkstram开始，然后转到A*：
我会从dijkstra而不是A*开始，因为A*基本上是一个知情的dijkstra-所以你应该能够在实现A*之前实现dijkstra，因为它[dijkstra]更简单。

其他最短路径算法：
你还应该知道，还有另一种常见的最短路径算法——著名的Bellman-Ford（与dijkstra不同，它也可以处理负权重）。

Answer 2

这是我制作的一个似乎有效的示例。为了提高效率，您需要在搜索下一个最短距离节点时实现最小堆。

private static int FindMin(int[,] indexWeights, Tuple<int, int> src, Tuple<int, int> dst)
{
    List<Node> allNodes = new List<Node>(indexWeights.GetLength(0)*indexWeights.GetLength(1));
    Node[,] graph = GenerateGraph(indexWeights, allNodes);
    Queue<Node> queue = new Queue<Node>();
    Node currentNode = graph[src.Item1, src.Item2];
    // 0 ? or the weight value at the index? This was not too clear from your example
    // Setting the starting distance to 0 means that a->b != b->a because the starting value
    // at index b is not the same as the starting value at index a
    currentNode.Distance = indexWeights[src.Item1, src.Item2];
    queue.Enqueue(currentNode);
    while (queue.Count > 0)
    {
        currentNode = queue.Dequeue();
        currentNode.Visited = true;
        if (currentNode.XCoord == dst.Item1 && currentNode.YCoord == dst.Item2)
            break;
        // Calculate tentative distances
        foreach (Node neighbor in currentNode.Neighbors)
        {
            neighbor.Distance = Math.Min(neighbor.Distance,
                                         currentNode.Distance + indexWeights[neighbor.XCoord, neighbor.YCoord]);
        }
        // Find the node with the minimum distance that hasn't been visited, and visit that next. 
        // A min-heap would be BEST for getting the next node, but I'll leave that as an exercise for you
        Node nonVisitedMinNode = allNodes.Where(a => !a.Visited)
            .Aggregate((currMin, currNode) => currMin.Distance < currNode.Distance ? currMin : currNode);
        queue.Enqueue(nonVisitedMinNode);
    }
    return graph[dst.Item1, dst.Item2].Distance;
}
public class Node
{
    public Node(int xCoord, int yCoord)
    {
        XCoord = xCoord;
        YCoord = yCoord;
        Distance = int.MaxValue;
        Visited = false;
        Neighbors = new List<Node>();
    }
    public int XCoord { get; set; }
    public int YCoord { get; set; }
    public int Distance { get; set; }
    public bool Visited { get; set; }
    public List<Node> Neighbors { get; set; }
}
public static Node[,] GenerateGraph(int[,] weight, List<Node> allNodes)
{
    Node[,] nodes = new Node[weight.GetLength(0),weight.GetLength(1)];
    for (int i = 0; i < weight.GetLength(0); i++)
    {
        for (int j = 0; j < weight.GetLength(1); j++)
        {
            nodes[i, j] = new Node(i, j);
            allNodes.Add(nodes[i, j]);
        }
    }
    // Couldn't think of a way to combine the two loops together to set neighbors
    for (int i = 0; i < weight.GetLength(0); i++)
    {
        for (int j = 0; j < weight.GetLength(1); j++)
        {
            if (0 <= (i - 1))
                nodes[i, j].Neighbors.Add(nodes[i - 1, j]);
            if (weight.GetLength(0) > (i + 1))
                nodes[i, j].Neighbors.Add(nodes[i + 1, j]);
            if (0 <= (j - 1))
                nodes[i, j].Neighbors.Add(nodes[i, j - 1]);
            if (weight.GetLength(1) > (j + 1))
                nodes[i, j].Neighbors.Add(nodes[i, j + 1]);
        }
    }
    return nodes;
}

我想不出一种非笨拙的方法来生成图形。。。也许现在已经太迟了。无论如何，您可能需要根据我们在评论中讨论的内容来调整currentNode.Dance的初始化。在您的示例中，[0,0]0是因为它是起始索引，还是因为值从0开始？如果您举另一个例子，其中起始索引不是的值为0，那么将更容易理解规则。

Answer 3

您正在寻找的是2D阵列中2个点之间的最短路径，因此Dijkstra或a*都很适合您。您提到的1和0只不过是2D阵列中的路径查找问题，这是上述算法的更具体的情况，可以使用简单的BFS来实现。

至于实现，正如其他人所提到的，您需要决定如何对解决方案进行建模，使其适合您正在使用的算法的设计。我能想到的两种可能的方法之一是：

• 将2D数组转换为图形，并在Source和Destination节点之间运行算法
• 以某种方式表示每个单元格，这样您就可以运行算法，而无需将其转换为图形

考虑到Dijkstra，这个问题的示例实现如下：

//Controls the size of your 2D array. Made static for simplicity. Can be allocated dynamically.
#define MAX_NODES 10
/* Your 2D Point Structure. Stores information of each cell of your 2D array */
typedef struct Point
{
    int x, y;    //x and y co-ordinate of your point
    int cost;    //Cell's actual cost
    int cost_from_src;     //Cell's cost from the Source node. This gets updated when algorithm runs
    unsigned int visited;    //Keeps track of nodes that have been popped out of the Queue
    struct Point *par;     //Keeps track of Parent Node
}Point_t, *Point_p;
/* 2D array of Point structure */
Point_t adjMArr[MAX_NODES][MAX_NODES];
/* Finds SP in Weighted 2D-Matrix */
Point_p SPDijkstra(Point_t src, Point_t dest)
{
    Queue_p q = NULL; // You can use your own implementation of a Queue
    // Source is initially put into the Queue
    adjMArr[src.x][src.y].cost_from_src = 0;
    adjMArr[src.x][src.y].par = NULL;
    q = push(q, adjMArr[src.x][src.y]);
    while (!isEmpty(q))
    {
        Point_t pt = extractMin(q); // Get the point with minimum value of "cost_from_src" from the Queue
        int x = pt.x, y = pt.y, new_cost, i;
        adjMArr[x][y].visited = 1;
        q = deleteQ(q, pt); // Delete this point from the Queue and mark it as visited. This point will not be visited again
        if (dest.x == x && dest.y == y)
            return &adjMArr[x][y]; // Destination Point
        /*Check for all the neighbours of Point(x,y) and update the costs of its neighbours add them to the Queue*/
        // Horizontal Left
        if ((x - 1 >= 0) && y < MAX_NODES && !adjMArr[x - 1][y].visited)
        {
            new_cost = adjMArr[x][y].cost_from_src + adjMArr[x - 1][y].cost;
            if (new_cost < adjMArr[x - 1][y].cost_from_src)
            {
                adjMArr[x - 1][y].cost_from_src = new_cost;
                /* To keep track of parent so that once you reach the destination node, you can traverse all the way back to parent */
                adjMArr[x - 1][y].par = &adjMArr[x][y];
                q = push(q, adjMArr[x - 1][y]);
            }
        }
        // Horizontal Right
        if ((x + 1 < MAX_NODES) && y < MAX_NODES && !adjMArr[x + 1][y].visited)
        {
            new_cost = adjMArr[x][y].cost_from_src + adjMArr[x + 1][y].cost;
            if (new_cost < adjMArr[x + 1][y].cost_from_src)
            {
                adjMArr[x + 1][y].cost_from_src = new_cost;
                adjMArr[x + 1][y].par = &adjMArr[x][y];
                q = push(q, adjMArr[x + 1][y]);
            }
        }
        // Vertical Up
        if ((y - 1 >= 0) && x < MAX_NODES && !adjMArr[x][y - 1].visited)
        {
            new_cost = adjMArr[x][y].cost_from_src + adjMArr[x][y - 1].cost;
            if (new_cost < adjMArr[x][y - 1].cost_from_src)
            {
                adjMArr[x][y - 1].cost_from_src = new_cost;
                adjMArr[x][y - 1].par = &adjMArr[x][y];
                q = push(q, adjMArr[x][y - 1]);
            }
        }
        // Vertical Down
        if ((y + 1 < MAX_NODES) && x < MAX_NODES && !adjMArr[x][y + 1].visited)
        {
            new_cost = adjMArr[x][y].cost_from_src + adjMArr[x][y + 1].cost;
            if (new_cost < adjMArr[x][y + 1].cost_from_src)
            {
                adjMArr[x][y + 1].cost_from_src = new_cost;
                adjMArr[x][y + 1].par = &adjMArr[x][y];
                q = push(q, adjMArr[x][y + 1]);
            }
        }
    }
    return NULL; // No path exists
}