分支定界算法可以纯函数实现吗？

Question

Branch and Bound 的一般描述

来自维基百科的Branch and Bound：

这一步称为剪枝，通常通过维护一个全局变量m（在树的所有节点之间共享）来实现，该变量记录了迄今为止检查的所有子区域中看到的最小上限。任何下界大于m 的节点都可以被丢弃。

实际示例：旅行商问题

旅行商问题的一个简单解决方案是保留一个变量，例如best，表示迄今为止发现的最短哈密顿回路（上限）。

每次我们考虑潜在的新电路中的新步骤时，我们计算当前点的路径成本，例如cost，这是该路径成本的下限，并将其与best变量进行比较。如果在任何时候cost >= best，我们不需要考虑这条路径；我们可以修剪所有以该子路径开头的潜在路径。

这在诸如 C 之类的过程语言中实现并不困难，我们可以在其中创建一个在函数范围内的变量。例如，

int best = -1; // no best path yet

node* solveTSP() {
    // best can be consulted and has a consistent
    // value across all recursive calls to solveTSP()
    ...
}

我的实际问题

我不清楚这种算法将如何在纯功能上实现。有没有办法模拟维基百科定义中提到的全局变量m？

我知道在 Lisp 中拥有一个全局变量很简单，但是在更纯粹的函数式语言（如 Haskell）中这可能吗？

Answer 1

您只需将当前最佳值作为附加参数传递给递归调用，并返回更新的最佳值作为其结果的一部分。所以如果你有一个类型的函数a -> b，它就会变成类似的东西a -> Int -> (b, Int)。您不是读取全局变量，而是读取附加参数，并且不是写入它，而是在函数完成时返回修改后的值。

这可以使用状态 monad很好地表达。TypeInt -> (b, Int)与 是同构的State Int b，所以我们的 type 函数a -> b就变成了a -> State Int b。