問題タブ [branch-and-bound]

私は、動的プログラミングと分岐とバインドを含むナップザックの最適化問題を行っています。問題の容量と項目が大きくなると、動的計画法アルゴリズムの 2D テーブルを埋めるのが指数関数的に遅くなることに気付きました。ある時点で、問題のサイズに応じてアルゴリズムを切り替えると仮定します (講義では 2 種類の最適化が行われたため)。

動的プログラミングからブランチ&バウンドに切り替えるべきポイント(サイズ)をググってみましたが、思うような結果が得られませんでした。

または、問題のサイズに応じてアルゴリズムを切り替えるのではなく、動的計画法と分岐限定を 1 つのアルゴリズムとして組み合わせることができるナップザック問題の別の見方はありますか?

ありがとう。

ボードゲームを解くプログラムを書きたいです。このゲームでは、2 つのボードがあります。1 つはソース ボード S、もう 1 つはターゲット ボード Tです。毎回移動できるアイテムは 1 つだけです。また、隣接するスペースにのみアイテムを移動できます (「~」はスペースを表します)。「～」は複数あっても構いません。そこで、分岐限定アルゴリズムを使用してこの問題を解決したいと考えています。ただし、下限コストを決定する方法がわかりません（現在の状態を目標状態に変更するための動きはほとんどありません）。

次のデータがあります：

容量は 10 です。ノード 0 の上限を計算するにはどうすればよいですか? 次のようにノード 0 の上限を計算しています。

または、値/重量が 12,9,8,5,5 の降順でアイテムを並べ替える必要がありますか? 上限を計算しますか？または、ソートせずに、上限を計算して次の項目に進むことなく、正しく実行していますか?

ソートなしの方法では、ノード0で最大上限を取得できません。そう思います。

ご協力ありがとうございます。

私は非常に複雑な問題に悩まされています:

ニワトリ、ワシ、およびヤードを含むMxNフィールドで、ニワトリはワシから (ヤードに入ることによって) 逃げようとし、ワシはニワトリを捕まえようとします。ニワトリは庭に入ると逃げ、ワシはニワトリと同じ位置にいるニワトリを捕まえます。1 つのステップで、ワシは 1 つまたは 2 つの小さな正方形を移動でき、ニワトリは任意の方向に 1 つの正方形を移動できます。プログラムは、ニワトリが勝てるかどうかを示すメッセージを表示する必要があります。移動を計算し、各ステップでフィールドの現在の構成を出力ファイルに書き込み、画面上で視覚的に表現する必要があります。畑の寸法、ニワトリとワシの位置、庭の寸法がファイルに記載されています。

フィールド（マトリックス）を作成することでその部分を解決しましたが、これを解決する方法がわかりません。後戻りも考えられるかもしれませんが、非常に複雑で、私には扱いきれません。ニワトリと庭の間、ワシと庭の間の距離を見つける方法を見つけて、それを何とかする必要があると思います。それは C でなければなりません。どんな提案、アイデアも大歓迎です! 前もって感謝します！

n 個の整数変数と m 個の制約を使用した ILP (整数線形計画法) 最適化と、正準問題を解決するための分枝限定木を実装する場合、

1. ツリーが全整数最適解に到達するために必要なレベル (ツリーの高さ) はいくつですか?
2. アルゴリズムが全整数最適解に到達するために必要な枝の数は?

おはようございます、

YARN (つまり、MapReduce の 2 番目のバージョン) で mapReduce の例を見つけることができませんでした。常に表示されるのは、MapReduce の最初のバージョンで表示されたものとまったく同じコードである WordCount です。「Hadoop: 決定版ガイド」でさえ、YARN にはコードがありません。

以前のバージョンと最新バージョンでの mapReduce コードの書き方の違いを示すコードを教えてもらえますか?

実際、私は MR1 でブランチとバインドされたコードを書こうとしていましたが、BranchReduce のおかげで YARN がより簡単になることがわかりました。

どんな助けでも大歓迎です、前もって感謝します