問題タブ [branch-and-bound]

未知のグラフ (A) と部分グラフ (B) にパスのセットがあり、B が段階的に生成されて成長している近似マッチング問題に取り組んでいます。

問題は、パスとグラフ全体のエッジの順序を維持しながら、パスのエッジをグラフ B に一致させることです。私の問題では、グラフノードは重要ではなく、エッジには、マッチングが実行される一意ではないラベルがあります。また、マッチングがグラフ B に対して行われている間に、マッチング対象のパスに任意のエッジを追加/削除することができます。現在のソリューションに満足できない場合は、オラクルに問い合わせることができます。これにより、より完全な (より大きな) グラフが得られます (つまり、成長とはどういう意味ですか) しかし、グラフは潜在的に無限になる可能性があるため、クエリを最小限に抑えたいと考えています。

アイテムのセットを含むことができる最小のビンの寸法を見つけるために、3D シングル ビン パッキング アルゴリズムを一般化するにはどうすればよいですか?

分岐限定アルゴリズムを検討していますが、現在の最適解ではなく、分岐を切断できる条件はありますか?

十分に明確であることを願っています。

次のようなBABツリー構造を実現したい

R、matlab、および CPLEX を使用しようとしていますが、わかりません。

軸平行線でポイントをカバーするための分岐限定手法を実装しようとしています。サブ問題ごとに、LP ソリューションを LB と見なし、反復丸めソリューションを UB と見なしています。最初は分数値変数 (LP を適用した後) を検討しており、0 と 1 の値については、SP1 と SP2 を副問題と考えています。前述のように、各 SP1 には UB1 と LB1 があり、各 SP2 には UB2 と LB2 があります。それから私はチェックしています

i) (LB1=UB1 または LB2=UB2) の場合は停止します。

ii) (UB1 >= LB2) の場合、SP2 を解く

iii) (UB2 >= LB1) の場合、SP1 を解く

よくわかりませんが、正しいアプローチを検討しています。ほとんどのノードで ii) と iii) の両方のケースが発生しているためです (ただし、一度に実行されるのは 1 つの「if」のみです)。私は正しいアプローチを使用していますか?? どんな助けでも大歓迎です。

ありがとう。

私は、分岐限定アルゴリズムで解決しなければならない問題に取り組んでいます。出発点からの距離の値が異なる n 個のガソリンスタンドがあるとします。ステーションにはさまざまな利益があります。利益を最大化したいのですが、各ステーションは少なくとも K の長さ離れている必要があります。動的アルゴリズムでこの問題を解決しましたが、分岐限定アルゴリズムの解決策を見つけることができませんでした。実際、境界を決定するには適切な目的関数が必要です。多くの機能を試しましたが、すべて失敗しました。ありがとう。

例：n=5 k=10

距離値 l1= 5、l2=15、l3=23、l4=30、l5=38

利益: p1=7、p2=3、p3=10、p4=12、p5=6

バックトラッキングでは、bfs と dfs の両方を使用します。分岐限定でも、最小コスト検索に加えて bfs と dfs の両方を使用します。

では、いつバックトラッキングを使用し、いつブランチ アンド バウンドを使用するのですか?

分岐限定を使用すると、時間の複雑さが軽減されますか?

分枝限定法における最小コスト探索とは?

Javaで分岐および境界検索アルゴリズムを実装しようとしています。そのコンセプト (仕組み) は知っていますが、実装方法がわかりません。

Googleでいくつかの例を見つけましたが、それらははるかに複雑で、理解できないようです. 簡単な方法で実装したいと思います。また、それらのほとんどはJavaにはありません。

以下は、検索が開始される関連メソッドです (これは私のコードの一部です)。for ループを適切に変更して、フロンティア ノードとコストを格納し、最小コストのノードを取得してから、目標ノードが累積コストを追加するまで検索を再度実行する必要があると思います。
したがって、これには再帰的な方法が最適であると思います。しかし、実装方法がわかりません。

以下はコンパイルエラーではありませんが、実行時エラーが発生していますNode1 cannot be cast to java.lang.Comparable. 誰かがこの問題を親切に調べてくれますか? 私は何時間もそれをやろうとしてきましたが、解決策が見つからないようです.

また、正しいパスに導く小さなコードは非常に役立ちます。

以下は、ファイル情報を格納する Node1 クラスです。

以下はファイル形式です(startNode endNode コスト)

[編集]：

私は分岐限定検索を実装したいと思います。ここで、プログラムはユーザーに入力startNodeしてから、クラス (ファイルからのデータが格納されている場所) のgoalNodeデータにアクセスするように要求し、プログラムはメソッド (上記のメソッド) に入り、すべてを渡します。startNode が node1[].getStartNode のいずれかに一致する場合、対応する展開されたノードとそれに対応するコストを優先キューに格納します (最小コストを選択するため)。次に、プログラムは優先キューを peeks() し、最小コストのノード (キューの先頭) を選択してから、その特定のノードを startNode として再度検索し (上記の検索メソッドを再帰的に呼び出しますか?)、検索を続行します。Node1searchnodesstartNodelength of nodes(size)frontierNodesfrontierCosts
プログラムが新しいノードに到達すると、各新しいノードのコストは、これまでに訪れたパスの累積コストを取得し、プログラムはパスとコストを出力する必要があります。

分岐限定アルゴリズムの再帰関数を実装しようとしています。アルゴリズムを再帰的に呼び出すたびに、再帰呼び出しで lb と ub の値を変更しています。エラーが表示されていますUB must be a real valued nx by 1 column vertor error in MATLAB。私のコードは以下に添付されています：

と のエラーが表示されub(round_value)=0ていlb(round_value)=1ます。どんな助けでも大歓迎です

単純なグラフ G =(V; E) を考えます。よく知られているパス カバー問題 ( https://en.wikipedia.org/wiki/Path_cover ) は、ハミルトニアン パス問題が NP 完全であるすべてのグラフ クラス (平面グラフ、2 部グラフ、および弦グラフを含む) で NP 完全です。多くの多項式アルゴリズムが、この問題が多項式である特別なグラフ クラスの文献で提案されていますが、2 部グラフ (または平面グラフや弦グラフ) の最小の頂点分離パス カバーを見つけるための正確な方法は見つかりませんでした。 、特に分岐限定アルゴリズム。

この問題が NP 困難であるグラフ クラス (2 部グラフ、平面グラフ、弦グラフ) でのパス カバー問題の正確な方法、特に分岐限定アルゴリズムを知っていますか?

前もって感謝します。