問題タブ [branch-and-bound]

DPは、TSPのような多くのNP完全問題に対してより良いパフォーマンスを提供することを理解しています。必要なスペースは大きいですが、複雑さを大幅に軽減します。

しかし、ブルートフォース検索と比較して、分枝限定法とバックトラックの効率を理解できませんでした。

最悪の場合、ブルートフォースがb＆bに等しいか、バックトラックに等しいか。

分岐と境界を使用して、このナップザックの問題を C++ で実装しようとしています。この Web サイトには Java バージョンがあります: Implementing branch and bound for knapsack

私のC++バージョンで本来あるべき90を出力しようとしていますが、そうではなく、5を出力しています。

誰がどこに何が問題なのか知っていますか?

CLRS は、バックトラッキング/分岐限定をカバーしていないようです。オンラインでいくつかのリソースを試しましたが、これらの背後にあるアイデアは得られましたが、ナップサックの問題などのコードを書くことができません。したがって、問題を取り上げてこれらの 3 つのアプローチで解決し、少なくとも疑似コードを提供する何かが必要です。または、あなたが知っているリソースが役に立ちます。

http://penguin.ewu.edu/cscd501/Wint-2011/BranchAndBound/Knap01BnB.txtの main() 関数で

上記のコードを使用して、Bandp.txt を実行してみましたが、問題はありませんでした。小数部の値を含む txt ファイルを実行しようとしたときに問題が発生しました。

10 進数値を表示でき、入力の不一致が表示されないように、コードのどの部分を変更する必要がありますか。

私のtxtファイルは以下のとおりです：data.txt

100 20
12.64 8.43 4.21 8.45 17.56 8.31 13.85 12.39 19.32 14.29 4.03 17.14 8.24 1.24 0.79 5.59 6.6 12.18 12.24 1.67 6.45 19.43 9.88 8.75 18.37 15.64 8.24 5.55 3.6111111111111111111111111111111116116116116116116116111616161.45 19.43 9.88 8.75 18.37

そして、これは BandP.txt の値です:

15 7 5 25 11 45 3 12 2 7 2 6 7 10 5 4

分枝限定アルゴリズムを実装する場合、ツリー全体を保存する必要はなく、アクティブノード（私が理解しているのはリーフノード）のリストだけを保存する必要があることを複数の本（Wolseyを含む）で読んだことがあります。

問題は、すべての祖先の境界がないと、分岐した後に新しい境界を計算する方法を理解できなかったということです。

それについてのいくつかの説明をいただければ幸いです。

TSPのすべてのアルゴリズムが同じ最適ルートを提供するかどうか疑問に思っていましたか？これが当てはまると思いましたが、分枝限定法とA *を実装しましたが、どちらも同じ入力に対して非常に異なる結果をもたらします。これは正常かどうか疑問に思っていました。

分枝限定法の一般的な説明

ウィキペディアの分枝限定法から：

このステップはプルーニングと呼ばれ、通常、これまでに調べたすべてのサブ領域で見られる最小の上限を記録するグローバル変数m （ツリーのすべてのノード間で共有）を維持することによって実装されます。下限がmより大きいノードはすべて破棄できます。

実例：巡回セールスマン問題

best巡回セールスマン問題の簡単な解決策は、これまでに見つかった最短のハミルトン閉路（上限）を表す変数を保持することです。

潜在的な新しい回路の新しいステップを検討するたびに、現在のポイントでのパスのコストを計算します。たとえばcost、このパスのコストの下限であり、best変数と比較します。いずれかの時点cost >= bestで、このパスを考慮する必要はありません。このサブパスで始まるすべての潜在的なパスを削除する場合があります。

これは、関数のスコープ内にある変数を作成できるCなどの手続き型言語で実装するのは難しくありません。例えば、

私の実際の質問

そのようなアルゴリズムが純粋に機能的にどのように実装されるかは私にはわかりません。ウィキペディアの定義で言及されているグローバル変数mをシミュレートする方法はありますか？

Lispでグローバル変数を持つのは簡単だと知っていますが、これはHaskellのようなもっと純粋に機能的な言語で可能ですか？

分枝限定によって、解決策を得るために手順を削減できることだけは知っていますが、それは解決空間ツリーを持つ問題にのみ役立ちます。