algorithm - 寻找最有利的货币兑换顺序

Question

我正在使用我书中的以下练习：

最短路径算法可以应用于货币交易。让 c ₁ , c ₂ , . . . , c _n是各种货币；例如，c ₁可能是美元、c ₂英镑和 c ₃里拉。对于任何两种货币 c _i和 c _j，都有一个汇率 r _i,j；这意味着您可以购买 r _i,j个单位的货币 c _j来换取一个单位的 c _i。这些汇率满足 r _i,j · r _j,i < 1 的条件，所以如果你从货币单位 c _i，将其转换为货币 c _j，然后再转换回货币 c _i，您最终会得到少于一个单位的货币 c _i（差额是交易成本）。(a) 为以下问题给出一个有效的算法：给定一组汇率 ri _,j和两种货币 s 和 t，找到将货币 s 转换为货币 t 的最有利的货币兑换序列。为了实现这个目标，您应该用边长为实数的图形来表示货币和汇率。

---

所以基本上我们想要做的不是最小化，我们需要最大化利润。因此，我们需要找到从 s 到 t 的最长路径。我们被断言存在从 s 到 t 的最短路径。

我想解决这个问题的方法是遵循这个算法：

1. 否定图的所有边
2. 运行有向无环图的最短路径算法。

我相信这会奏效，但我不确定。在谷歌上，我发现了一些解决方案，其中包括另一个步骤：使用对数将比率的乘法转换为加法。我认为这一步对她来说是不必要的，但我仍然不确定。

Answer 1

不要再尝试使用 Google 或 StackOverflow 来寻找解决方案，而是想一想。虽然许多问题可以通过从各种来源收集资源、信息和想法来解决，但有些问题却不能。让您的计算机进入睡眠状态。去找个安静的地方。想一想，直到你有一个想法。在废纸或白板上绘制示例图表。试试看。看看它是否有效。如果它不考虑为什么不尝试寻找新的想法。如果是这样，请尝试考虑一个无效的图表。当您确信自己拥有适用于所有图形的算法时，您就完成了。仅仅让我们告诉您解决方案，您不会学到很多东西。