我想知道如何为最短路径问题分配最大成本值。在我的问题中,节点与风险相关。因此,我希望最小化风险,但同时希望在找到解决方案时限制节点数量(例如,从节点A到节点B找到最小风险,同时确保解决方案不超过n个节点)。非常感谢。
我想知道如何为最短路径问题分配最大成本值。在我的问题中,节点与风险相关。因此,我希望最小化风险,但同时希望在找到解决方案时限制节点数量(例如,从节点A到节点B找到最小风险,同时确保解决方案不超过n个节点)。非常感谢。
Dijkstra算法是最佳优先搜索,即我们应该确保到达最佳节点的距离永远不会变得更好。它适用于具有非负边缘的最小Dijkstra情况。在一般情况下,您可以使用Ford-Bellman。如果您想要使用不超过n个顶点,则可以建议您使用动态规划dp[vertex][used_vertex_count],其复杂度为O(|V| * n)状态和内存以及O(|E| * n)时间。或者创建图的邻接矩阵,主对角线上为零,不存在边缘的地方为无穷大,并计算其n次幂。a_{ij}将是使用不超过n个顶点从i到j的最小路径。
我认为在这里使用一些涉及启发式的算法会更加适合,启发式是指每一步离目标有多“接近”的概念,以及哪个节点将使你更接近目标。如果没有这个,我认为我们需要在最坏情况下运行一个指数级算法(当只使用n
个节点无法到达目标时)。在这种情况下,我们将查看所有使用n
个节点的路径,然后才得出问题无法解决的结论。
使用非启发式算法的一个例子是:以常规方式运行Dijkstra算法,选择风险最小的节点。在此过程中,跟踪您访问的节点数量。如果节点数超过n
,则放弃当前路线并回溯到先前的节点,并使用具有下一个最低风险的节点。自然地,您不能仅回溯到n
的上一级,因为如果目标在下一级,则会被选中。因此,您要回溯到n-2
级并继续进行。这也将是指数级的,因为没有真正的方法来确定不存在性而不检查所有路径。
也可能是我漏掉了什么。