算法面试题：基于外汇汇率矩阵的最大套利方案求解

题目描述 #

给定一个n×n的外汇汇率矩阵F，F[i][j] = f的含义是1单位货币i可以兑换f单位货币j。其中F[i][i] = 1，且不保证F[i][j] * F[j][i] = 1。要求基于该矩阵计算可获得的最大套利收益。
示例：假设1欧元可兑换2美元，1美元可兑换0.6欧元，那么走「欧元→美元→欧元」的路径，1欧元最终可兑换得到1.2欧元，即存在20%的套利空间。

约束澄清 #

原问题表述存在未明确的规则限制，无约束的前提下问题无实际求解意义：

• 若不对兑换路径做任何限制，只要存在任意正收益的套利环，理论上可以无限次循环套利获得无限收益，不存在最大收益的说法
• 目前行业内通用的合理约束有两类：
  • 限定最多兑换次数k，且要求起始货币与终止货币必须相同，比如k=3时路径为「货币1→货币2→货币3→货币1」
  • 要求套利路径为无重复节点的简单环，避免重复进入同一个节点循环套利

解法说明 #

• 常规的Bellman-Ford算法仅能判断汇率图中是否存在套利机会（通常将汇率取自然对数后转乘法为加法计算，正收益的乘积对应负权环），无法直接求解最大套利收益
• 若采用无重复节点的简单环约束，可使用深度优先搜索+剪枝或者状态压缩动态规划的方案求解：记录当前到达的货币节点、已访问的节点集合、当前累计兑换收益，遍历所有合法的简单环后取收益最大值即可

内容的提问来源于stack exchange，提问作者user6703592