12

依存関係アルゴリズムに問題があります。依存関係は、厳密なバージョン スコープ ベースであることを除いて、Maven 依存関係に似ています。

例えば：

component A, version 1 depends on: component B, version 1~3; and component C, version 2~3
component D, version 1 depends on: component B, version 2~4; and component C, version 1~2

ここで、コンポーネント A のバージョン 1 とコンポーネント D のバージョン 1 をインストールするときに、依存関係を取得したいと考えています。それらはすべてコンポーネント B と C に依存しているため、B と C の正しいバージョンを取得するには正しいアルゴリズムが必要です。

さらに、コンポーネント A と D をアップグレードする必要がある場合があります。たとえば、次の新しいバージョンがあります。

component A, version 2 depends on: component B, version 3~5; and component C, version 4~5
component A, version 3 depends on: component B, version 6~7; and component C, version 4~5
component D, version 2 depends on: component B, version 3~4; and component C, version 3~4

ここで、アップグレード可能な A と D の正しいバージョンと、それらのすべての依存関係を取得するためのアルゴリズムが必要です。ここでの問題の 1 つは、コンポーネント A のバージョン 3 とコンポーネント D のバージョン 2 に、コンポーネント B の依存関係の競合があることです。

このような問題を解決する既存のアルゴリズムはありますか? または同様の（より簡単な）問題。何か提案はありますか？

大量のデータがあるべきではないため、パフォーマンスは考慮しないでください。

前もって感謝します！

4

2 に答える 2

12

この問題は、次の 3SAT からの還元により NP 困難です。3CNF 式を考えると、変数ごとに 2 つのバージョンを持つコンポーネントがあり、節ごとに 3 つのバージョンを持つコンポーネントがあります。「スーパー」コンポーネントの 1 つのバージョンをインストールしたいと考えています。このコンポーネントは、すべての句コンポーネントに依存しますが、バージョンは気にしません。各句について、句コンポーネント 1 は、句に現れる最初の変数に依存します。リテラルが正の場合はバージョン 1 が必要であり、負の場合は 0 が必要です。節コンポーネント 2 は 2 番目の変数などに依存します。式が満足できる場合に限り、スーパー コンポーネントをインストールできます。

この削減に照らして、問題を制約の充足として定式化することは理にかなっています. 各コンポーネントは、可能な値がそのコンポーネントのバージョンであり、そのコンポーネントがインストールされていないことがオプションである場合は「インストールされていません」です。コンポーネント B のバージョンに依存するバージョンを持つコンポーネント A ごとに、A と B の変数を含む制約があり、バージョンの選択をそれらのドメインの製品の特定のサブセットに制限します。最初の例の A と B の場合、A バージョン 1 は B バージョン 1 ～ 3 に依存するため、これは {(1, 1), (1, 2), (1, 3)} です。A のバージョン 2 も利用できる場合、この制約は {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5) になります。 }。A または B をインストールする必要がなかった場合、{(none, none), (none, 1), (none, 2), (none, 3), (none, 4), (none, 5), (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)}.

インスタンスが小さいため、おそらく制約の伝播を伴う完全なバックトラッキング検索が必要になるでしょう。制約伝播の一般的なアルゴリズムはAC-3です。これはアークの一貫性を強制します。つまり、削除されたものに基づいて、明らかに機能しないすべてのバージョンを考慮から除外します。たとえば、制約 {(1, 1), (1, 2), (1, 3)} が与えられた場合、B = none を削除できます。B の選択肢が制限されたので、B の依存関係 C などについて推論を行うことができます。単純化する必要がなくなったら、推測する必要があります。1 つの戦略は、残っているバージョンが最も少ないコンポーネントを選択し、それらすべてを再帰的に試すことです (バックトラック)。

于 2013-05-02T11:37:39.163 に答える
1

これは充足可能性問題の変形です。osgi もそれに対処する必要があります。そのため、osgi の仕様や実装を調べて、それらがどのように解決されているかを確認できます。

于 2013-04-09T09:43:41.660 に答える