云解决方案提供商查找路径

Question

我能够实现默认的统一成本搜索(python)来查找两个节点之间的最短路径(路径成本)。我遵循了以下伪代码：

Answer 1

这被称为"约束最短路径问题"，并且具有使用Dijkstra算法的伪多项式时间解。我们的新图不仅有节点，还具有(node, spent_fuel)对，这使边和顶点的数量增加了最大燃料预算B的系数。

如果你的原始 Dijkstra 算法在时间O(|E| + |V| log |V|)运行，其中E是你的边集(或操作，在本例中)，V是你的顶点集，新算法将在时间O(B|E| + B|V| log (B|V|))运行。如果您的预算不比图表的大小大多少，这还不错;否则，您将需要更高级的求解方法，因为当预算不受限制时，约束最短路径是NP-Hard。

在这里，我们仍然按距离单调递增的顺序处理(node, fuel_cost)对，因此当我们第一次探索目标时，我们有在预算内到达目标的最小距离。

这是伪代码。有一些可能的优化：如果我们知道该节点的路径fuel <= fuel_cost并且距离小于或等于path_cost，您可以过滤掉(node, fuel_cost, path_cost)。例如，您可以通过为每个节点构建二进制搜索树来做到这一点，并且仅当其路径开销小于任何(node, fuel_cost + c), c >= 0时才考虑(node, fuel_cost)。

function Constrained-Uniform-Cost-Search(problem)
start <- node with State = problem.initial-state, Path-Cost 0

// Elements of frontier are (node, fuel_cost) pairs, ordered by distance. 
frontier <- priority queue, contains (start, 0)
explored <- empty set
while frontier is not empty:
(node, fuel_cost) <- pop(frontier)

if node == target: return Solution(node, fuel_cost)
add (node, fuel_cost) to explored
for action in problem.Actions(node):
(neighbor, neighbor_fuel) <- Child-Node(node, fuel_cost, action)
if neighbor_fuel > problem.Budget: continue
if (neighbor, neighbor_fuel) not in explored or frontier:
frontier <- insert((neighbor, neighbor_fuel), frontier)

else if (neighbor, neighbor_fuel) in frontier with higher Path-Cost:
replace that frontier node with (neighbor, neighbor_fuel)
return Failure