algorithm - 分支定界算法可以纯功能性地实现吗？

Question

分支定界的一般描述

来自维基百科的 Branch and Bound :

This step is called pruning, and is usually implemented by maintaining a global variable m (shared among all nodes of the tree) that records the minimum upper bound seen among all subregions examined so far. Any node whose lower bound is greater than m can be discarded.

实例:旅行商问题

旅行商问题的一个简单解决方案是保留一个变量，例如best，表示目前发现的最短哈密顿回路(上限)。

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

这在 C 语言这样的过程语言中并不难实现，我们可以在 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) 的类型。您不是读取全局变量，而是读取附加参数，而不是写入它，而是在函数完成时返回修改后的值。

这可以用 the state monad 很好地表达.类型Int -> (b, Int) 同构于State Int b，所以我们的类型a -> b 的函数变成了 a -> 状态 Int b。