4

我在寻找不超过指定成本的最快路径时遇到问题。

假设我有指定的最大成本和 4 条记录。

// specified cost
    10 
// end point
    5
//(start point) (finish point) (time) (cost)
    2 5 50 5
    3 5 20 9
    1 2 30 5
    1 3 30 7

我必须决定，是否有可能从点 (1) 到 (5)（当没有成本 <= 比我们拥有的路径或当 1-5 之间没有联系时，这是不可能的）如果是这样，什么将是进入那里的最快方式。

此类数据的输出将是：

80 // fastest time
3 1 // number of points that (1 -> 2)  -> (2 -> 5)

请记住，如果有记录说您可以移动1->2

1 2 30 5

它不允许您移动2<-1。

4

2 回答 2

2

使用动态编程，如下所示：

Route(node, length, target, accumulated)

if length <= 0 return -1
if node == target return accumulated

For each adjacent node:
  current length = accumulated + Route(adjacent node, length - connecting edge weight, target, accumulated + connecting edge weight)
  min length = min(current length, min length)

return min length
于 2012-11-15T18:47:03.823 回答
0

网络搜索发现 h​​ttp ://www.cs.elte.hu/~alpar/publications/jour/AKCE_October_25.pdf表明这是一个合理的当前研究问题。在不阅读论文的情况下，我的方法是使用动态编程，其中，对于每个节点，您为每个合理的 K 记录成本 <= K 的最短路径。您只需要在可用的最短路径发生变化时保留 K 值随着 K 的变化。如果成本或时间是可靠的小整数，这可能是可行的。如果没有，您可以构建示例问题，这些问题需要您计算并保持无法管理的部分解决方案数量。

于 2012-11-15T20:39:56.703 回答