5

AC-1、AC-2、および AC-3 アルゴリズムを説明できる人はいますか? それらを理解し、コードで実装する必要があります。でも、まずは本当によく理解したいのですが、難しすぎて私には理解できません。何か助けてください。ところで、私はバックトラックにあまり慣れていません。私はそれについてのビデオを読んだり見たりしようとしましたが、それでも同じです! ありがとう、

4

1 に答える 1

22

バックトラッキングと AC-3 について簡単に説明します。しかし、これについてさらに詳しく読みたい場合は、次の本を読む必要があります。

人工知能: 最新のアプローチ : スチュアート ラッセルとピーター ノーヴィグ 2003 プレンティス ホール

この本は、AC-3 とバックトラッキングのすべてを説明する制約充足問題 (CSP) に関する章です。

最初に理解する必要があるのは、CSP とは何かです。CSP には以下が含まれます。

  • 値を検索する変数 {A、B、C} のセット。
  • 各変数 Da、Db、Dc のドメインには、変数が取り得る可能な値がそれぞれ含まれています。
  • A > B + 2 および C < B のような制限のセット ...

CSP がある場合、すべての変数に値を割り当て、制限を尊重し続ける必要があります。CSP は、すべての変数が値を持ち、すべての制限を同時に尊重するときに解決されます。

バックトラッキングは、この問題の解決策を見つけることができるアルゴリズムです。したがって、空の状態 {} から開始します。これは、変数に値がないことを意味します。次に、変数セットから 1 つの変数を選択します (選択する変数を選択するために使用する順序は、アルゴリズムのパフォーマンスに影響を与える可能性があります。MRV - 残りの最小値など、これに使用できるヒューリスティックがいくつかあります)。ここで、最初に A を選択し、ドメイン Da から値を取得するとします (この値を選択する順序はヒューリスティックを使用する場合もあります)。Da = {1,2,3} と想像してください。1 を選択します。次に、A = 1 が制限に違反していないかどうかを確認します。違反していない場合、それは適切な帰属ではありません。そうでない場合は、A = 1 に設定しましょう。これで {A=1} の状態になります。では、これを続けましょう。B と値 1 を選択したとします。これは制限 A > に違反します。B + 2. 2 つのオプションがあります。B をテストする別の値がある場合は、それを試すことができます。そうでない場合、これは A = 1 が間違っていることを意味し、状態 {} に戻って A = 2 などを試す必要があります。

バックトラッキングの擬似コードは次のとおりです。

function backtracking (csp) return a solution or fails
    return recursive_backtracking({}, csp) // {} is the initial state

function recursive_backtracking (state, csp) return a solution or fails
    if state is complete then return state // all variable have a value
    var <- selectNotAtributedVariable(csp)
    for each value in orderValues(csp, var) // values of the domain of var
        if var = value is consistent given the restrictions
            add {var = value} to state
            result = recursive_backtracking(state, csp)
            if result != fail then return result
            remove {var = value} from state
    return fail

selectNotAtributedVariable と orderValues はヒューリスティックであることに注意してください (セットの最初の要素を返すだけかもしれません)。

AC-3 とは何ですか? なぜ、いつ使用するのでしょうか? 最初の AC-3 は、前処理ステップとして使用されます。次のように使用します。

function solveCSP(csp)
    ac3(csp)
    return backtracking(csp)

これはいつに答えます。基本的に、AC-3 は、バックトラッキング中に、帰属表示で発生する競合を検出し、それらを削除します。どのように？CSP 内の変数のドメインをカットする。したがって、2 つの変数が制限を共有する場合、両方の間に円弧があると言います。次の場合、A と B の間の弧は一致していると言えます。

  • A->B は一貫しています: A が取ることができる各値 a には、制限に関して B が取ることができる値 b があります。
  • そして B->A は一貫しています: B が取ることができる各値 b には、制限に関して A が取ることができる値 a があります。

次の制限 A > B および B > C があるとします。次の弧のセットがあります: {A->B, B->A, B->C, C->B} さて、AC-3上記のセット、A->B からアークを選択し、A が取ることができる a の値ごとに、制限に関して B が取ることができる値 b があるかどうかをチェックしようとします。その場合、A のドメインは同じままです。そうでない場合は、A のドメインから値 a を削除します。値がドメインから削除されるたびに、A の近隣を再確認する必要があります (この場合)。つまり、アーク B->A を再確認する必要があるということです (上のセットにあるからではありません)。

したがって、ここに疑似コードがあります：

function AC3(csp) returns csp possibly with the domains reduced
    queue, a queue with all the arcs of the CSP
    while queue not empty
         (X,Y) <- getFirst(queue)
         if RemoveConsistentValues(X,Y, csp) then
              foreach Z in neighbor(X) - {Y}
                   add to queue (Z,X)
    return csp

function RemoveConsistentValues(X, Y, csp) returns true if a value was removed
    valueRemoved <- false
    foreach x in domain(X, csp)
        if there's no value of domain(Y, csp) that satisfies the restriction between X and Y then
            remove x from domain(X, csp)
            valueRemoved <- true
    return valueRemoved
于 2015-01-31T23:02:51.467 に答える