6

分支定界的一般描述

来自维基百科的分支和绑定

此步骤称为修剪,通常通过维护一个全局变量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)中这是否可能?

4

2 回答 2

4

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

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

于 2013-03-27T14:59:06.573 回答
1

具有可变状态的计算并不比没有它的计算强大。一个可以简化为另一个。

特别是,从功能的角度来看,可变单元格变成了一系列连续值,通常在某些排列中,新副本会影响旧副本(例如,在尾递归中)。

于 2013-03-27T07:23:16.900 回答