6

抽象的な言葉での質問:

クエリ時に排他的な頂点のサブセットを含む有向非巡回グラフ (DAG) があります (サブセットごとに 1 つのアイテムのみがクエリの結果に存在する必要があります)。グラフ構造を照会するとき、グラフ内の頂点の既知のサブセットから単一のアイテムのみを選択しながら、特定の頂点から流れる頂点のセットを取得したいと考えています。

具体的な質問:

アセンブリ (頂点) とその依存関係 (エッジ) を格納する DAG があります。アセンブリまたはアセンブリのセットを指定すると、関連するすべてのアセンブリとその依存関係のセットを取得するためにクエリを実行する必要があります。難しいのは、各アセンブリには複数のバージョンがあり、アセンブリの 1 つのインスタンスしかプロセスにロードできないことです。特定のアセンブリの依存関係は、アセンブリのさまざまなバージョン間で異なります。

この問題または一連の問題に名前はありますか? 解決策を見つけるために調査できる標準アルゴリズムは?

考えられるソリューション分野:

推移閉包は良い解決策に近いように見えますが、サブセット (アセンブリ バージョン) から選択されたアイテムは、グラフを通過するパスに応じて変化します。おそらく複数の分岐を通過するため、グラフを通過するパスをトレースして生成する必要があります。推移閉包。

グラフデータベースはかなり役立つかもしれませんが、絶対に必要でない限り、今はその道をたどりたくありません。

4

1 に答える 1

1

与えられた選択肢から流れる頂点のセットは、実際には根本的な最適化または満足の問題があるため、混乱しているように見えると思います: アセンブリ A が与えられた場合、B1 または B2 または B3 を介してその依存関係を満たすことができ、それらの選択肢のそれぞれは、独自のノックオンの結果。

これを論理満足度の問題と見なすと、アセンブリが 2 つのバージョン (A1 または A2 など) しか存在しない場合の問題を考えることができます。次に、(a or b or not c) などの句は、A1、B1、または C2 を必要とする上位レベルのアセンブリに変換されます (X1、X2、および X3 を介して間接的に行われる可能性があります)。すべての上位レベル アセンブリを必要とするレベル アセンブリ。したがって、一般的な問題を効率的に解くことができれば、3-SAT を効率的に解くことができ、P = NP になると思います。

不思議なことに、各タイプ (A1 または A2 または A3 で、一度に複数のアセンブリ) のアセンブリを 1 つだけ許可するという制限がない場合、問題は非常に簡単にホーン節に変換されます (Knuth Vol 4 セクション 7.1. 1 P 57) は、充足可能性問題を効率的に解くことができます。これを行うには、自然変数の逆数を使用して、X1 は A1 が含まれていないことを意味します。次に、ホーン節のバージョンを問題を緩和する方法として扱う場合、各アセンブリの最大 1 つのバージョンをサポートできるという制約を無視することによって、得られるのは、一部のアセンブリ バージョン A1が存在できないことを通知するメカニズムです。 X1 = not A1 は Horn ソリューションのコアで真であり、したがってすべての満足する割り当てで真であるためです。

于 2011-09-23T05:04:44.533 に答える