图论问题(名称未知)

Question

我正试图解决以下问题。我不知道是否已经有了这个名字，或者一个解决方案；不过，我敢打赌肯定有。我希望有人能为我指明解决方案的方向，或者至少告诉我问题的名称？

假设一个旅行者有一定数量的金币和一些铜币。他必须创建一个城市A，然后去B市，然后是C市，最后是D市。

从A到B有两条(或更多)道路，标有AB1和AB2 (等)。路标AB1有5枚金币，AB2有5枚铜币。

从B市到C市的道路: BC1收费10枚硬币，可以是任何一种货币。BC2需要8枚金币。

从C到D的道路也有类似的设置。

假设我们知道旅行者有多少钱，而且铜币和金币之间没有可能的交换:是否有一种方法可以确定旅行者是否有足够的钱从A到B，到C，最后到D？

这就是我需要解决的问题.这个问题有名字吗？这个问题有解决办法(除了暴力之外)吗？我假设这是一个类似于流问题的问题，但我不知道如何处理它。

Answer 1

如果我正确地理解了你的问题，你的问题有两个有趣的特性：

1. 图是顺序连接的，A->B->C->D节点之间可能有多条边，但从来没有“跳过”节点(A->C，B->D)或循环回(C->A)的边。
2. 最终目标是可行性和最优性。也就是说，你想知道一个旅行者是否有足够的钱，而哪条路的花费是最低的。

对吗？如果是这样的话，有一些技巧可用。

首先，计算每座城市之间的黄金和青铜的期望值。期望值将是您期望支付的最低值。给定AB1 =5金，AB2 =5铜，AB3 = 10金或青铜(我在添加说明一点的方法)，您永远不会选择AB3。AB1或AB2为您提供了一个更好的解决方案，而不管您使用的是什么硬币。因此，A和B之间的期望值为5金5青铜。B与C之间的期望值为8金10青铜。同样，我们永远不会选择BC1 (10金或青铜)当消费黄金，因为BC2 (8黄金)总是更便宜。继续计算路径其余部分的期望值。

接下来，每枚硬币的期望值合计。你基本上就像是用一枚硬币付了所有的通行费，但这两种方式都是一蹴而就的。如果您的预期值是：

• A->B5金，5铜
• B->C8金，10铜
• C->D10金，7铜

你的总数是23金22铜。如果你从23枚或更多的金牌和22枚或更多的铜牌开始，你就完蛋了。你知道有一个可行的解决方案。更有可能的是，您的预期总数将大于您的硬币可用。

在这种情况下，在期望值对和考虑这两个选项之间做出选择。如果你缺金，那就把铜花在黄金回收量最高的地方。例如，如果我从13金开始，我可以选择C->D之间的青铜支付选项来创建一个可行的解决方案。如果我从5铜开始，我可以选择B->C和C->D之间的黄金支付选项来创造一个可行的解决方案。

再说一次，这可能是一厢情愿的想法。很可能你会同时做空黄金和铜牌。如果是这样的话，从一个启发式开始来解决期望值:如果你有一个较大的黄金赤字，选择的期望值在解决铜之前产生最大的黄金节省，试着用最少的“选择”来弥补赤字，等等。最后，您可能仍然需要尝试各种期望值组合，以证明可行的解决方案确实存在或不存在。

请注意，这并不包括涉及两种货币的通行费。一个2金5铜的数字破坏了我的期望值诡计。

Answer 2

我不确定它是否与流算法有关，因为一个流问题将允许您部分沿着AB1，而部分沿着AB2，例如。

我认为你基本上是坚持深度优先搜索，但你有机会修剪。例如，如果一条路需要8枚金币，而同一两座城市之间的另一条路需要10枚金币，你就不需要费心穿越后者了。这就给你留下了一条金子，一条铜器，还有一条“任一条”的路在每座城市之间。另外，请记住，从算法的角度来看，您访问城市的顺序并不重要。如果CD路的成本都比AB路高，你可以先移动它们来加快速度。

Answer 3

如果你的旅行者不得不回到起点，那将是http://en.wikipedia.org/wiki/Travelling_推销员_问题的一个变化。实际上，这只是一个路径优化问题。我会用深度优先搜索来解决这个问题，但那是因为它是我从研究生院记得的仅有的两三种图遍历算法之一。