二维数组路径查找

Question

我想找到一个二维数组中两个索引之间的最小加权路径。我尝试实现Dijkstra和A*算法，但是均未成功。以下是一个示例。我想给出路径的起点和终点，并由算法返回路径。

0 2 5 8 8 9 5 1 2 7 9 8 9 8 2 5 7 8 8 8 2 2 2 9 9 7 6 3 2 7 8 8 6 5 3 5

请问是否有其他算法可供推荐或关于这些算法的指南？

我已经在这个问题上工作了几天，但我不认为这是一个具有挑战性的问题。但我已经失去了耐心，无法健康地思考。例如，我甚至不能理解a*和Dijkstra最短路径是否与我的需求直接相关。或者它们只适用于0和1这样的结构，即如果有墙，则无法通过，否则可以。在我的问题中，您可以从任何地方通过，但我想找到成本最小的路径等。

- user1125953

---

你说你“无法”实现Dijkstra算法，是因为它不适用还是太复杂了？请描述一下你已经尝试过的方法，而不仅仅是要求解决方案。 - Random Dev

@CarstenKönig 在 Dijkstra 算法中有顶点和边。但实际上它们是同一件事。我错了吗？我无法决定这样的问题。一个代码示例将有助于理解，但我不要求直接给出解决方案并复制它。我想知道人们会如何做到这一点？任何帮助都将不胜感激。 - user1125953

这个有用吗？https://dev59.com/VWHVa4cB1Zd3GeqPjyAF#9547524，你可以通过有向图来建模你的环境。 - Saeed Amiri

@SaeedAmiri 你觉得将一个二维数组建模成有向图难吗？这只是一个例子，我的实际二维数组大小至少为300x300。 - user1125953

@Tung 实际上不会出现起始点和结束点相同的情况。我想要的基本上是从一个索引开始，对我传递的值求和，当我到达终点时，总和是最小可能的。 - user1125953

Answer 1

将问题建模以"适应"算法的设计：
首先尝试从网格中构建一个图形，这可能有助于您理解这些算法并实现它们。由于这两个算法都是为图形设计的[可以对网格进行建模]，我认为当您在“通用图形”上实现它们并为您特定的问题建立一个图形时，您可能会更容易地理解这些算法。

您的图形将是G = (V,E)，其中V = { (i,j) | (i,j)是可能的索引)}[网格中的所有正方形]，E = { (v,u) | v和u是网格上相邻的顶点 }。
您还需要一个权重函数在边缘上。w:E->N。它将是w(u,v) = matrix[v.x][v.y][匹配v的条目中矩阵的值]。

现在，在您喜欢的语言中为图形G实现dijkstra。最短路径的权重是通过dijkstra找到的路径的权重+matrix[source.x][source.y][因为我们没有将此值添加到最短路径上的任何边缘]。

要找到实际路径，而不仅仅是它的权重-您还需要保持一个map:V->V，它将从每个顶点映射到发现它的顶点。类似于这篇文章中解释的想法。

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

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

- amit

---

谢谢。我会在C#中实现它。我不知道如何在C#中构建图表，所以现在正在搜索相关信息，谢谢。希望这些对我有所帮助。 - user1125953

@user1125953：你可能想阅读一下关于图形的可能表示方法（http://en.wikipedia.org/wiki/Graph_%28data_structure%29#Representations）。 - amit

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.Distance的初始化。[0,0] 在您的示例中是否为0是因为它是起始索引，还是因为该值开始时为0？如果您提供另一个示例，其中起始索引没有值为0，则更容易理解规则。

- Tung

---

我现在正在尝试你的代码。已经过去了5分钟，它仍在运行，这是一个大问题:) 实际上，我真正感兴趣的不是距离，而是要找到路径。因此，我需要相应地修改你的代码。但无论如何，谢谢你，我会尽力从你的代码中受益。 - user1125953

@user1125953。最小堆是您可以添加到代码中的最大改进之一。我只是使用linq进行线性搜索（这意味着我要在900个节点中搜索最小的未访问节点）。在算法结束时，您可以回溯。由于已访问的节点已计算其距离，并且您拥有Node内的所有邻居，因此您可以通过从目标节点开始跟随具有最小距离的邻居来找到返回路径。 - Tung

起始节点肯定在路径上，所以它的权重并不重要。我想要的结果是：0,0-...-4,4。 - user1125953

Answer 3

你所需要的是在二维数组中两点之间的最短路径，因此Dijkstra或A*算法都可以很好地解决这个问题。你提到的1和0只是2D数组中的路径查找问题，这是上述算法的更具体的情况，并且可以使用简单的BFS实现。

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

• 将你的2D数组转换为图形，并在源节点和目标节点之间运行你的算法。
• 以一种方式表示每个单元格，以便你可以在不必将其转换为图形的情况下运行你的算法。

考虑到你选择了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
}

- Cheshar