二维数组寻路 [英] 2D array path finding

问题描述

我想找到一个二维数组的两个指标之间的最小加权路径。我试图实现Dijkstra的最短路径算法和A *，但我不能。有以下的例子。我想给起止点的路径和路径应该由算法返回。

I want to find the minimum weighted path between two indexes of an 2D array. I have tried to implement Dijkstra's shortest path algorithm and A* but I couldn't. There is an example below. I want to give starting and ending point of path and the path should be returned by the algorithm.

0 2 5 8 8 9

5 1 2 7 9 8

9月8日的 2 5 7 8

9 8 2 5 7 8

8 8 2 2 2 9

9 7 6 3 2 7

9 7 6 3 2 7

8 8 6 5 3 5

8 8 6 5 3 5

任何人都可以reccomend其他算法或指导我有关的算法？

Can anybody reccomend other algorithms or guide me about the algorithms?

我工作的这几天，我不认为这是一个具有挑战性的问题都没有。但是，我失去了我的脾气，不能认为希尔蒂。例如，我甚至无法理解是否*和Dijkstra的shorthest路径，直接关系到了我想做的事情。或者，他们为0和1状结构，如果有一堵墙，你无法从那里，如果没有你可以通过工作。在我的问题，你可以通过从任何地方，但我想找到的最低成本路径等。

I am working on this for days and I don't think it is a challenging problem at all. But I lost my temper and cannot think healty. For example, I even could not understand whether a* and dijkstra's shorthest path is directly related to what I want to do. Or they work for 0 and 1 like structures that if there is a wall you cannot pass from there if not you can. In my problem you can pass from anywhere but I want to find the least cost path etc.

推荐答案

下面是一个示例我刮起，似乎工作。为了更有效率，你寻找下一个最短距离节点时，需要实现一个最小堆。

Here's a sample I whipped up that seems to work. To be more efficient, you need to implement a min heap when searching for the next shortest distance node.

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，那么这将是比较容易理解的规则。

I couldn't think of a non clunky way to generate the graph... maybe it's too late here. Anyway, you may need to tweak the initialization of currentNode.Distance based on what we discussed in the comments. Is [0,0] 0 in your example because it is the starting index, or is it because the value is 0 to begin with? If you give another example where the starting index does not have a value of 0, then it would be easier to understand the rules.

这篇关于二维数组寻路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！