1

互いにさまざまな依存関係を持つ一連の要素があります。これらの依存関係は厳密な場合があります。aとに依存しbますc。または、一部の要素には代替手段がある場合があります。またはsに依存します。循環依存関係はありません。tu

依存関係情報を使用して、次の 2 つのことを実行しようとしています。

  1. 特定の要素セットのすべての依存関係が解決されているかどうかを判断する
  2. 考えられる完全に解決された要素のセットをすべてリストする

(実際、リソースが許す限り、すべての順列を生成してチェックするだけなので、1 を考えると 2 は自明です。しかし、おそらくそれにはもっと優れたアルゴリズムがあります。)

代替の依存関係を持つ要素に対応するアルゴリズムはありますか? 厳密な依存関係のみを説明するものはたくさん見つかりましたが、検索を絞り込むのに十分な用語を知りません。

4

2 に答える 2

1

あなたの要素がLにリストされているとしましょう。次に、Lの各要素eについて、すべての直接的な依存関係が解決されていることを検証します。各要素eを検証するには、 eの依存関係のリストDを調べて、D内のすべての要素dがLにあることを確認します。代替のケースに対処するために、各dをそれ自体の代替依存関係のリストと考えてください。

for each d in e.D 
    d_ok = false
    for each alt_d in d
        if alt_d in L: d_ok = true, break
    if not d_ok: return false
return true

依存関係を満たすすべての可能なセットを一覧表示するには、順列インデックスを使用して、alt_d可能なすべての異なる順序ですべての を反復処理します。Lの各要素の選択肢の数がわかっているため、これらのインデックスを事前に生成できます。3 つの依存関係を持つ要素aと 2つの依存関係を持つ要素bndgridがあると仮定すると、次のコードのように使用される MATLAB でチェックアウトできます。

[idx_a, idx_b] = ndgrid(1:3, 1:2);
idx = [idx_a(:), idx_b(:)];

これを実装する言語に関係なく、このような事前計算されたインデックスを使用する方法のリファレンスについては。

于 2013-01-22T03:17:59.487 に答える
0

厳密でない依存関係の場合、選択肢が 2 つしかない場合。s は t または u に依存する (これ以上ない) ため、2SAT 問題と見なして解くことができます。

于 2013-01-22T03:27:26.950 に答える