問題タブ [branch-and-bound]

いくつかの制約に従って、s = c1*x1 + c2*x2 + c3*x3 + c4*x4 のような式を最大化するアルゴリズムを使用する必要があるボードをフラッシュしています。

たとえば、x+y <= 2, 3x+y >= 4 を条件として p = x+y を最大化します。最適解: p = 2; x = 1、y = 1

どこかで使用できる無料のコードはありますか?

ありがとうございました

アイテムの順序が保持され、結果のリストが 1 つの整数に連結された場合に可能な限り小さくなるように、整数の 2 つのリストからアイテムを結合する方法がわかりません。

この質問に似ている可能性がありますが、与えられた答えは私のサイズの制約に対応していません: Interleave different length lists, elimating duplicates and preserve order in Python

たとえば、次のようになります。

これら 2 つのリストの最短の組み合わせは次のようになります。

連結された整数値 34574928 を使用

数値の順序がリストの長さに影響しないが、連結された整数のサイズに影響する場合があります。上記の例では、項目の順序を維持しながら 4 と 9 を入れ替えることができますが、最終的な数字は必要以上に大きくなります。

さらに明確にするために：

最終的なリストには、元の 2 つのリストからの各数字のすべてのインスタンスが含まれている必要があります。上記の例で 2 つの組み合わせをより適切に表すには、次のようにします。

もちろん、いつもきれいにうまくいくとは限りません。この場合、2 つのリストの 4 つの数字 (3、5、7、および 2) を完全にマージできます。4 つの数字 (4、4、9、および 8) は、より大きなリストを作成しないと結合できませんでした。例えば：

この場合、3 と 4 のうちの 1 つだけを組み合わせました。これら 2 つの結果例の項目を連結すると、次のようになります。

どちらも順序付け要件を満たしていますが、順序付け要件を満たしているが、整数に連結したときに bad_c よりも小さい別の結果があるため、bad_c は正しくない結果です。

問題：

各頂点のブール状態が、接続された頂点の状態が与えられた論理関係によって制約されるグラフがあります。エッジは反応を表し、各反応には一連のアクティベーター (それを促進する)、リプレッサー (反応を阻害する)、および生成物 (反応が発生したときにオンにすることができます) があります。いくつかの頂点については、それらがどの状態にあるべきかの既知のブール割り当てがあります。私の目標は、グラフの論理的制約に従いながら、既知の割り当てとの一致を最大化するグラフ内のすべてのブール値の割り当てを見つけることです。

編集: ILP の目的と、使用することを提案している制約は次のとおりです。

基本的に、私の目的は、データから知られている「真の」状態の割り当て (M) と最もよく一致する、グラフ内のすべての種への状態の割り当てを見つけることです。グラフ内のすべての種に既知の状態があるわけではありません。

最初の制約は、すべての活性化種が TRUE で、阻害種がどれも TRUE でない場合にのみ反応が発生することを指定します。

2 番目の制約は、種を生成する反応の 1 つが TRUE である場合、または入力ノードとして指定されている場合に、種が TRUE になる可能性があることを示しています。

これまで読んだことから、この問題は B&B アプローチの良い候補です。しかし、B&B とブルート フォース検索の時間の複雑さを見積もるのに苦労しています。私の推測では、ブルート フォース検索は 2^n (n = 頂点の数) になると思います。これは、最悪の場合に B&B ツリーによって生成されるノードの総数だからです。しかし、評価する必要がある制約の数も、B&B とブルート フォースの複雑さを考慮に入れる必要があるようですが、その方法はわかりません。

非常に小さなアイテムのセット、中規模および非常に大規模なアイテムのセットを考えると、最適なアルゴリズム (動的プログラミング、貪欲、分岐および境界) とその効率が何であるかを考えていました。

4 つのアイテム (重みが異なる) と 3000 の容量がある場合、複雑さ O(nW) を考えると、動的計画法は最適なソリューションではない可能性がありますが、Greedy でさえ最適なソリューションは得られません。サイズは、これら 3 つから選択するアルゴリズムに影響しますか?

巡回セールスマン問題の B&B アルゴリズムの疑似コードを探しています。私はこれを見つけました: TSP - 分岐してバインドされ ていますが、誰かが答えとしてそこに与えたリンクは、これまでのところ役に立ちませんでした。疑似コードのOSの例はありますか?

前もって感謝します！

http://youtu.be/gGQ-vAmdAOI?t=23m14sで作業していた 23:14 の時点で、「拡張リスト」を使用したブランチ & バウンドは Dijkstra のアルゴリズムに非常に似ていると感じました。講義の後半で、許容可能なヒューリスティックを使用してアルゴリズムを再度拡張すると、A* が得られます。

そのため、ダイクストラのアルゴリズムはまさに分岐限定のサブクラスであると考えるようになりました。そうですか？

講義を要約すると：

検索アルゴリズムが調査されます。具体的には、単純なブランチ & バウンド ソリューションから開始します。

宛先ノードが訪問される (拡張される) まで、ソースから最短距離のノードを訪問し、その後続ノードを訪問するノードの優先キューに追加します (最小距離でソート)。これはまだサイクルを検出しておらず (例: ノードを 2 回以上訪問する)、組み合わせ爆発のためにかなり非効率的です。

単純な拡張により、アルゴリズムのパフォーマンスが大幅に向上します。どのノードが既にアクセスされたかを記憶します (拡張された、したがって拡張リスト)。ノードが 2 回アクセスされることはなくなり、アルゴリズムのパフォーマンスが大幅に向上しました。

最後の部分では、A* を取得するために許容可能なヒューリスティックがミックスに追加されます。

これが十分な情報であり、講義の例をコピーする必要がないことを願っています. そうでない場合はお知らせください。

colSum と rowSum という 2 つの 10 進数の変数があり、これらの合計に基づいてバイナリ値のマトリックスを作成したいものを使用します。rowSum 配列変数は、各行のすべての 1 を追加した結果です。

だから、あなたが持っているなら

次の配列を適切に構築する必要があります

私は PHP でこのメソッドを使用しています。これは 3x3 マトリックスでは機能しますが、8x8 などのより大きなマトリックスでは機能しません。まず、rowSum 値を使用して行のすべての 1 を埋めます。次に、2 つの列の間違った合計値を見つけようとします。ピボットを使用して、colSum の正しい値を取得するまで、同じ行でそれらを交換します (1 つは cero 値)。しかし、2 つの列の同じ行で 1 と 0 を変更するには、基準をある程度制御する必要があるため、機能しません...

これは私が使用している方法です。

この行列があるとしましょう (N=3 -> NxN):

次に、次の配列があります

ステップ1

各行に R0(i) と同じ数の 1 を使用して、NxN 配列を作成して塗りつぶします。

この新しい行列の合計を計算します: R1 = {0,1,2} C1 = {2,1,0}

ステップ2

作成した行列の列和のすべての要素が C0 (原点) と同じ値を持っているかどうかを確認します

列を置き換えるには、条件を掘り下げる必要があります。C0(0) = 1 != C1(0) = 2 最初の列の合計は、replace を呼び出す条件を満たしているので、

ステップ 3

分岐限定法を適用するための条件を選択し、グローバル条件 (すべての列の合計) を満たす列を変更するのに最適な行を見つけます。

列の合計の差の変化量は次のとおりです。

この例では |C0(0)-C1(0)| = 1 回の変更。変更によって列の合計の差が大きくなる場合は、戻る条件にする必要があります。

では、この方法は本当に機能するのでしょうか?