2

各ノードに任意の依存関係が含まれているか、他のノードと競合している可能性があるグラフを考えると、循環参照や矛盾参照を含むあらゆる配置が可能になります。

すべての制約を尊重できるノードのリストを最大限に含む安定した結果リストを計算しようとしています。必要な解決策がある場合は、可能な解決策を1つ見つける必要があります。

以下の例では、「A が B に依存する」は、A が真であるためには B が真でなければならないことを意味します。「B が A と競合する」とは、B が true であることを意味し、A が true であってはなりません。依存関係と競合の両方に優先順位はなく、重みが等しく、同時に適用されます。

3番目の例では、Bと競合するDに依存しているため、「A」は表示されません。AもBを必要とするため.. Dの競合とAの依存関係により禁止されているため、Aは存在できません。

A depends on B
B conflicts with A
= B

A depends on B
B depends on A
= A and B

A depends on B
A depends on D
B depends on C
D conflicts with B
D conflicts with C
= B and C or D

A conflicts with B
B conflicts with C
C conflicts with D
D conflicts with A
= A and C or B and D

私は機能するアルゴリズムを考え出そうとしていますが、これまでのところ、自明ではないグラフで見事に失敗するヒューリスティックなゴブリングックに似ています。洞察、読み物へのポインタ、またはアルゴリズムの名前をいただければ幸いです。

4

2 に答える 2

2

私はそれを仮定します

  • 「A は B に依存する」とは、A が B を暗示し、
  • 「B conflicts with A」は、B が A ではないことを意味します。

ここで、A は B = not A or Bを意味し、 B は not A = not B or not Aを意味します。これは、問題が要約すると、各節が 2 つの引数 (A ではなく A、B、または B ではない) を持つ選言の結合 (節とも呼ばれる) の解決策を見つけることになることを意味します。

この問題は、2-充足可能性として知られています。Web で多項式時間アルゴリズムを見つけます。たとえば、http://en.wikipedia.org/wiki/2-satisfiabilityから始めます。

最新の SAT ソルバーの解像度を理解している限り、独自のアルゴリズムを作成する必要はありません。SAT ソルバーは、このようなインスタンスを多項式時間で自動的に解決できる必要があります。

于 2013-02-01T07:58:45.943 に答える
1

質問で使用されている言語をブール式に変換すると、次のようになります。

「A は B に依存する」 => 「(a と b) または (a ではない)」

と

「B は A と衝突する」 => 「(b であり、a ではない) または (b ではない)」

したがって、これを (Python 3 で) 記述する簡単な方法は、デカルト積を生成し (すべての可能な選択肢を与える)、制約が満たされるケースのみを選択することです。簡単にするために、入力に文字の代わりにインデックスを使用しているため、 などy[0]と同等Aです。ただし、出力を文字に変換しました。

n ノードの場合、このアプローチは 2^n のすべての可能なケースを生成してテストします。より複雑だが潜在的に効率的なアプローチについては、以下を参照してください。

import itertools

bbb = (True,False)

def resolve(n,test):
    return [x for x in itertools.product(bbb,repeat=n) if test(x)]

def dependsOn(a,b):
    return (a and b) or (not a)

def conflictsWith(b,a):
    return (b and not a) or (not b)

letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def pr(d):
    for dd in d:
        s = [letters[i] for i in range(len(dd)) if dd[i] ]
        if (len(s) > 0):
            print(s,end = " ")
    print()

pr(list(resolve(2,lambda y: 
    dependsOn(y[0],y[1]) and 
    conflictsWith(y[1],y[0])
    )))
pr(list(resolve(2,lambda y: 
    dependsOn(y[0],y[1]) and 
    dependsOn(y[1],y[0]) 
    )))
pr(list(resolve(4,lambda y: 
    dependsOn(y[0],y[1]) and 
    dependsOn(y[0],y[3]) and
    dependsOn(y[1],y[2]) and 
    conflictsWith(y[3],y[1]) and 
    conflictsWith(y[3],y[2])
    )))
pr(list(resolve(4,lambda y: 
    conflictsWith(y[0],y[1]) and
    conflictsWith(y[1],y[2]) and
    conflictsWith(y[2],y[3]) and
    conflictsWith(y[3],y[0])
    )))

これにより、次の結果が得られます。

['B']
['A', 'B']
['B', 'C'] ['C'] ['D']
['A', 'C'] ['A'] ['B', 'D'] ['B'] ['C'] ['D']

... 4 つのテスト ケースの場合。

詳細については、Wikipedia の真理値表のエントリを参照してください。

（編集）

多くのノードと多くの制約がある問題に対するより効率的なアプローチは、ノードのリストを徐々に構築し、その部分リストが制約に準拠している場合にのみ、各部分リストから構築を続けることです。遠い。resolve上記の関数を次のバージョンに置き換え、dependsOnおよびconflictsWith関数を一致するように置き換えることで、これを行うことができます。

import queue

# The following constraint functions return True if the constraint is met
# or if one or more of the elements relating to the constraint is None

def dependsOn(a,b):
    if (a != None) and (b != None):
        return (a and b) or (not a)
    else:
        return True

def conflictsWith(b,a):
    if (a != None) and (b != None):
        return (b and not a) or (not b)
    else:
        return True

def resolve(n,test):
    result = []
    testCount = 0
    # initialise the list with all None
    lst = [None] * n
    q = queue.Queue()
    q.put(lst)
    while not q.empty():
        lst = list(q.get())
        testCount += 1
        if test(lst):
            # the list complies with the constraints, at least
            # as far as it is populated
            if lst[-1] != None:
                # we have a fully-populated list
                result.append(lst)
            else:
                i = lst.index(None)
                lst[i] = True
                q.put(list(lst))
                lst[i] = False
                q.put(list(lst))
    print ("testCount = %d" % testCount)
    return result

これにより、4 つのテスト ケースで同じ結果が得られます。ただし、3 番目と 4 番目のテスト ケースでは、 の値はtestCountそれぞれ 21 と 23 です。これは、デカルト積ソリューションに必要なテストの総数 (n=4 の場合は 16) を超えていますが、さらに多くのノードと多くの制約がある場合、このアプローチでは、テストできないノードのサブセットをテストすることを回避できます。には解が含まれている可能性があるため、デカルト積の解よりもはるかに少ないテストで済みます。もちろん、制約がほとんどまたはまったくない最悪のシナリオでは、このアプローチでは最大 2^(n+1) - 1 回のテストが必要になる可能性があります。実際、これは最初の 2 つのテスト ケース (testCountこのアルゴリズムを使用した場合は 7) で発生します。

ここに示されている実装は粗雑であり、確実に速度を最適化できることに注意してください。

于 2013-01-28T21:58:43.373 に答える