1

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

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

4

1 に答える 1

0

割り当てとグラフの同型から標準解を検索しようとしましたが、似たようなものは見つかりませんでした。だから、ここに私が思いついた解決策があります：

  1. 分岐限定アルゴリズムを使用して、パスのすべてのエッジをグラフ (MXN テーブル) のすべてのエッジに一致させています。可能な割り当てごとに、特定の割り当てを含む他の割り当てが可能なものを追跡しています
  2. 境界条件 (& 実現可能性) は、パス内と同じグラフ内のエッジの順序付けによって定義されます。また、2 つのパスを相互の順序に違反するようにマップすることはできません。
  3. この解決策に満足できない場合は、オラクルにクエリを実行し、より大きなグラフを取得して、1 と 2 を繰り返すことができます。それ以外の場合、この手法は可能なエッジ マッピングを出力します。

標準のブランチ & バインド ツリー構造に従わなくなったため、私のソリューションがまだブランチ & バインド アルゴリズムに該当するかどうかはわかりません。また、誰かが最適化またはこれを行うためのより良い方法を指摘できれば、それは素晴らしいことです.

注: 反復ごとに N が変化し、テーブルが水平方向に拡大します。最大の非効率性はステップ 2 にあり、これは安全のためにすべての段階で再計算する必要があります (たとえば、グラフに追加されたループは以前のソリューションを無効にします)。

于 2015-03-29T19:57:15.083 に答える