添加节点的效果未知时寻找最便宜路径的算法
Algorithm for finding cheapest path when effect of adding a node is unknown
我需要在有向加权循环图上找到节点 a 和 b 之间的最便宜路径，最便宜定义为从给定的任意值中引出最小 return 值costfunc。通常 Djikstra 是我认为的最佳选择，除了 costfunc 采用 整个路径 - 添加单个节点的效果未知（我想我可以 运行 costfunc 有和没有给定节点并使用差异...)。
我该怎么做？
在 costfunc 没有一些限制的情况下，没有什么比尝试每条可能的路径更好的了。假设
costfunc = 1 / (sum of edge weights)
那么你的问题（在循环图上）是 NP hard Longest Path Problem。
而对于
costfunc =
sum of edge weights if path length = N
infinity otherwise
你已经熟知 NP 完整 Travelling salesman problem
我需要在有向加权循环图上找到节点 a 和 b 之间的最便宜路径，最便宜定义为从给定的任意值中引出最小 return 值costfunc。通常 Djikstra 是我认为的最佳选择，除了 costfunc 采用 整个路径 - 添加单个节点的效果未知（我想我可以 运行 costfunc 有和没有给定节点并使用差异...)。
我该怎么做？
在 costfunc 没有一些限制的情况下，没有什么比尝试每条可能的路径更好的了。假设
costfunc = 1 / (sum of edge weights)
那么你的问题（在循环图上）是 NP hard Longest Path Problem。
而对于
costfunc =
sum of edge weights if path length = N
infinity otherwise
你已经熟知 NP 完整 Travelling salesman problem