2

我已经在这个问题上停留了一段时间，试图找出以下问题的递归关系。

问题描述：

假设在一个市场中，以下交易选项是可能的：

  • 1 金属对 2 木材
  • 1 木材到 0.2 玻璃
  • 1 玻璃比 1.5 金属
  • 1 木材到 0.4 火
  • 1 火对 3 金属

确定是否可以仅通过交易从某个项目上获利。

例如，在上述场景中，我们可以通过以下操作从金属中获利：

1 金属 -> 2 木 -> 0.8 火 -> 2.4 金属

我坚持的部分是应该如何分解子问题。这个问题似乎对括号乘法问题很熟悉，我们试图通过一系列乘法来最大化最终结果，但有更多限制。

我不想要完整的答案，但是可以将我推向正确方向的提示将不胜感激！

谢谢！

4

1 回答 1

1

提示：您可以通过“玩”权重并将其简化为已知的加权最短路径问题来解决此问题。

剧透：详细解释

这可以通过在图上找到负怀特循环很好地解决，权重：

让我们w'(u,v)将一个单位转换为 的u成本v。定义：

w(u,v) = -log(w'(u,v))

这个想法是一条路径v1->v2->...->vk有成本

COST = w(v1,v2) + w(v2,v3) + ... + w(vk-1,vk) = 
     = -log(w'(v1,v2)) + -log(w'(v2,v3)) + ... + -log(w'(vk-1,vk)) = 
     = -log (w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk))

现在，很容易看出 的值w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk)恰好是vk一个单位 的产量v1。

类似地，对于从 some 到它自身的任何循环u：u->v1->v2->v3->...vk->v， 的值w'(u,v1)*w'(v1,v2),...,w'(vk,u)是您可以通过这种方式生产多少个单位，并且该值大于 1 当且仅当-log(w'(u,v1)*w'(v1,v2),...,w'(vk,u) < 0

所以，这个问题可以很容易地简化为一个已知的算法——Bellman-Ford，它可以很容易地检测出负循环的存在。

于 2016-03-13T17:38:44.840 回答