1

我想找到到节点成本最低的路线。它为我找到了几条路线，但没有最低成本的路线。

我的类来存储有关节点的信息：

public class Graph
{
    //public int[][] childNodes;
    //public Graph(int[][] nodes)
    //{
    //    this.childNodes = nodes;
    //}

    public List<Node> nodes = new List<Node>();
}

public class Node
{
    public Node(int node)
    {
        this.node = node;
    }

    public int node { get; set; }
    public List<Tuple<int,int>> endNodes = new List<Tuple<int,int>>();
}

public class Routes
{
    public int depth { get; set; }
    public int cost { get; set; }
    public List<string> nodes = new List<string>();
}

在元组中，我有 int, int - 第一个 int 是结束节点，第二个 int 是到该节点的路由成本

遍历图的类：

public List<string> visited = new List<string>();
public List<Routes> routes = new List<Routes>();





   public void dfs2(Node node, List<Routes> routes, Routes route, int depth)
        {
            depth++;
            foreach (Tuple<int,int> childNode in g.nodes[node.node].endNodes)
            {
                string path = string.Format("{0}{1}", node.node, childNode.Item1);
                string pathReverse = string.Format("{0}{1}", childNode.Item1, node.node);
               // if (!visited.Contains(path)) // && !visited.Contains(pathReverse))
                if(!route.nodes.Contains(path)) // && !route.nodes.Contains(pathReverse))
                {
                    visited.Add(path);
                    if (childNode.Item1 == 6)
                    {
                        Routes newRoutes = new Routes();
                        newRoutes.depth = depth;
                        newRoutes.cost = route.cost + childNode.Item2;
                        newRoutes.nodes.AddRange(route.nodes);
                        newRoutes.nodes.Add(path);
                        routes.Add(newRoutes);
                    }
                    else
                    {
                        route.depth = depth;
                        route.cost += childNode.Item2; // 2;//childNode.
                        route.nodes.Add(path);

                        dfs2(g.nodes[childNode.Item1], routes, route, depth);
                    }
                    Debug.WriteLine("przeszedłem: " + path);

                }
            }
        }

在我的示例中，我想找到到节点 6 的成本最低的路线

4

1 回答 1

0

如果没有简洁但完整的代码示例，很难提供一个好的答案。在您的问题中，我什至没有看到任何可使用的示例图形数据，更不用说清楚地描述发生了什么以及您希望发生什么。

也就是说，您可能有兴趣研究经典的寻路算法及其相关算法： http ://en.wikipedia.org/wiki/A*_search_algorithm

该算法的基本思想是，对于图中的每条边，您需要一个成本值，对于每个节点，您需要一种方法来估计到目的地的剩余成本。请注意，“剩余成本”估计值可以设置为 0，这将导致对所有路径进行呼吸优先搜索……速度很慢，但仍会产生正确的结果（假设您的图表足够小，算法可以在有用的时间）。如果您的数据有助于计算良好的估计值，那就更好了。

该算法的工作原理是跟踪当前节点的成本，并选择一个相邻节点，其中当前成本加上相邻节点的成本加上从该节点到目的地的估计成本最小化。维护按总成本（该节点的成本加上估计成本）排序的节点列表，以便在每次迭代中，总是可以选择成本最低的节点。如果当前路径加估计变得比其他访问节点的路径加估计更昂贵，则算法有效地回溯到成本较低的节点并从那里继续。

从本质上讲，它是在探索图表，根据对剩余距离的有根据的猜测，寻找成本最低的路径。算法的性能将取决于您实现“有根据的猜测”的程度。

于 2014-10-14T20:10:18.323 回答