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)。グローバル変数を読み取る代わりに、追加の引数を読み取り、それを書き込む代わりに、関数の終了時に変更された値を返します。

これは、状態モナドを使用してうまく表現できます。タイプ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 に答える