問題タブ [branch-and-bound]

誰かが私のために分岐限定検索手法を説明できますか? 分岐限定探索アルゴリズムを使用して、任意の開始ノードから任意のランダム グラフの終了ノードまでの最小コストのパスを見つける必要があります。

分岐限定アルゴリズムで TSP を解決しようとしています。

コストを含むマトリックスを作成する必要がありますが、この問題があります。座標 x と y を持つ都市があります。

旅費はceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v)+ 市内滞在日数です。Vは速度です。

都市で過ごす日は、w が都市に来る日によって異なります。たとえば、月曜日(t1)に都市 1 に到着した場合、9 日間滞在しますが、火曜日に到着した場合、都市に 4 日間滞在します。

分岐限定アルゴリズムを使用してこの問題を解決するにはどうすればよいですか?

TSP 用の Branch And Bound アルゴリズム、または一般に TSP 用の BnB を含む OR フレームワークの便利な Java 実装があるかどうか疑問に思います。

ご協力いただきありがとうございます！

マルコ

分岐限定アルゴリズムで解決すべき問題がありますが、解決方法を考えるのに苦労しています。分岐限定アルゴリズムを開始する方法がわかりません。

問題は次のとおりです。

車には最大重量と容積容量があり、車に荷物を詰める必要があります。これらのパッケージには、重要性、重量、および容積の決定された値があります。目的は、車の重量と容積の制限を超えずに、重要度が最も高いパッケージの組み合わせを車に搭載することです。

私はこの問題に取り組んでおり、いくつかの結果を得ることができますが、ここで分岐とバインドの方法を実装するのに問題があります。
皆さん、私を助けてくれますか?

建物の倉庫

説明

After winning the lottery, you decide to buy several truks (or lorries). Your goal is to deliver goods to all supermarkets in Coimbra. But now you have to build warehouses to store the goods, and you have to think about possible locations. Ideally, the warehouses should be located close to the supermarkets in order to reduce transportation costs. However, you cannot spend all the money on building warehouses everywhere, so you have to make a clever decision: given the fixed cost of building each warehouse in each possible location and the transportation cost of serving each supermarket from each location in the next 5 years, you want to know where warehouses should be build so that the overall cost (transportation and fixed costs) over that period is minimum. Note that at least one warehouse must be built. Moreover, the computation of the overall transportation cost has to take into account that all supermarkets must be served.

入力

各テスト ケースには、特定の場所に倉庫を建設するための固定費と、各場所とスーパーマーケットに関連する輸送費に関する情報が含まれています。各テスト ケースの最初の行は、倉庫を建設できる可能性のある場所の数 (n<51) とスーパーマーケットの数 (m < 16) を示しています。次に、次の n 行のそれぞれは、その場所に倉庫を建設するコストと、その場所から m 個のスーパーマーケットのそれぞれに商品を供給するのに関連する輸送コストを示します。

出力

出力は、倉庫の建設と運用の最小総コスト (整数) です。例

入力：

4 5

10 8 6 10 8 10

9 1 2 10 4 8

10 6 4 2 1 5

1 10 4 6 9 3

出力:

26

http://pastebin.com/apXCMdxy

私は巡回セールスマン問題の分枝限定アルゴリズムに取り組んでいますが、少し問題が発生しました。頂点（パス）のサブセットを表すノードを持つかなり標準的なキューを使用しています。私はすべてがうまくいったと確信していますが、現時点ではパブリッククラスのキューがあり、その下にプライベートクラスのノードとそのすべてのプロパティ（現在のパス、下限など）があります。

ただし、メインプログラムで、ノードのキューを初期化し、2つの開始ノードを作成しましたが、「ノードをタイプに解決できません」というエラーが表示されます。これは、Queueクラス内にあり、メインプログラムにアクセスできないためだと思いましたが、移動すると、ノードに接続されているアイテムで他のすべての場所でエラーが発生します。

これが理にかなっていることを本当に願っています。他にどのように説明すればよいかわかりませんが、他のすべては問題ないようです。明確にするために、私のコードのスニペットを次に示します。

ここでNodeクラスを宣言し、メインプログラムで実際に使用します。

私は、b&b ナップザックの問題のために、この (ひどい) 疑似 Java コードを実装することに頭を悩ませています(私は疑問に思います: なぜ人々はそんなことをするのでしょうか?)。これはこれまでの私の実装で、最大 80 を出力します (教科書サンプルの項目の場合、90 を出力する必要があります)。要素をアルゴリズムに渡す前に Pi/Wi で並べ替える Comparator (LinkedList 上) を作成しましたが、この入力では既に並べ替え済みです。私は今デバッグ中です（そして投稿されたコードを更新しています）、それは配列のインデックス付けの問題だと思います...または境界関数に間違いがありますか？

入力：

Haskellを使用してバイオインフォマティクスの領域からモチーフ検索アルゴリズムを実装しています。分枝限定法による中央値文字列検索以外のアルゴリズムの詳細については説明しません。マルチコアの速度を上げるために、並行アプローチ（および後でSTMアプローチ）を実装することによって実装をより面白くすることを計画していましたが、フォローフラグを使用してコンパイルした後

プロファイルを印刷すると、何か面白い（そしておそらく明らかな）ものが見つかりました：

マルチコアプログラミングに近づくことなく、驚くべきスピードアップが得られることは明らかです（ただし、それは実行されており、いくつかの優れたテストデータを見つけて、そのための基準を整理する必要があります）。

とにかく、これらの機能は両方とも純粋に機能的であり、決して同時ではありません。とてもシンプルなこともしているので、時間がかかってびっくりしました。それらのコードは次のとおりです。

hammingDistanceに対する2つの引数のうち、改善の余地がある場合は、xsがxの長さになり、ysがそれ以下になると実際に想定できることに注意してください。

ご覧のとおり、hammingDistanceは、ヌクレオチドのリストである2つのモチーフ間のハミング距離を計算します。モチーフ関数は数値とリストを受け取り、その長さのすべてのサブ文字列を返します。例：

関連するアルゴリズムプロセスは非常に単純なので、これをさらに最適化する方法を考えることはできません。しかし、私はどこに向かうべきかについて2つの推測があります。

1. HammingDistance：私が使用しているデータ型（NukeTidesと[]）は遅い/不器用です。私はそれらの実装に精通していないので、これは単なる推測ですが、自分のデータ型を定義することは、より読みやすくなりますが、おそらく私が意図するよりも多くのオーバーヘッドを伴うと思います。また、パターンマッチングは私にとって異質であり、それが些細なことなのか、費用がかかるのかはわかりません。
2. モチーフ：これを正しく読んでいると、すべてのメモリ割り当ての70％がモチーフによって行われ、いつかガベージコレクションが必要になると思います。繰り返しになりますが、万能リストを使用すると、コストが非常に不明確になるため、速度が低下したり、リストの理解が遅くなったりする可能性があります。

ここでの通常の手順について誰かアドバイスはありますか？データ型が問題である場合、配列は正しい答えでしょうか？（箱に入っていると聞きました）

助けてくれてありがとう。

編集：これらの2つの関数が呼び出される方法を説明すると便利かもしれないと思いました。

この関数は別の関数の結果であり、ツリー内のノードに渡されます。ツリーの各ノードで、totalDistanceを使用してノードをスコアリングし、ヌクレオチドの評価（長さ<= n、つまり== nの場合はリーフノード）が実行されます。それ以降は、典型的な分枝限定アルゴリズムになります。

編集：ジョンは、モチーフのコストを実質的に排除するために行った変更を印刷するように依頼しました。

元の投稿では明確にしませんでしたが、scoreFunctionは1回だけ呼び出され、結果はツリートラバーサル/分枝限定法で渡され、バインドされてノードの評価に使用されます。振り返ってみると、あらゆる段階でモチーフを再計算することは、私が行った中で最も明るいことの1つではありません。

最も効率的な方法で問題を解決するアルゴリズムを探しています。

問題の説明:

アイテムのリスト（正の整数のみが許可されています）と、同じ容量の固定数のビンがあります。これまで分枝限定アルゴリズムについて考えてきましたが、この場合、それが最善のアプローチであるかどうかはよくわかりません。

例：

アイテムのリストが与えられた場合:

そして、それぞれ9個の容量の3つのビンを詰める必要がありますこれ: (アイテムの順序は関係ありません)

これはビンパッキング問題 (NP 完全であることはわかっています) の変種だと思いますが、使用するビンの数を最小化しようとしていないので、より良い解決策があるのではないかと思います。