分枝限定法の一般的な説明
ウィキペディアの分枝限定法から:
このステップはプルーニングと呼ばれ、通常、これまでに調べたすべてのサブ領域で見られる最小の上限を記録するグローバル変数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のようなもっと純粋に機能的な言語で可能ですか?