1

min-conflicts アルゴリズムについて助けてください。

  A B C D
1 _ _ Q Q
2 Q _ _ _
3 _ _ _ _
4 _ Q _ _

この時点で、

  • アルゴリズムはどちらか一方を移動するためにランダムCに選択するか、またはD両方が同じ数の競合を作成するため (Cと競合しているD、Dと競合しているC)、
  • それともD、移動できる最適な場所Cが 3 列目であり、1 つの競合が発生し、選択Dして 3 列目に移動すると競合が 0 になるため、選択しますか。
4

1 に答える 1

0

ウィキペディアのページからの関連行:

 var <-- a randomly chosen variable from the set of conflicted variables CONFLICTED[csp]
 value <-- the value v for var that minimizes CONFLICTS(var,v,current,csp)
 set var = value in current_state
  1. varランダムに選ばれたクイーン C または D の位置を表します。
  2. varボードの残りの部分を考慮して、競合を最小限に抑える前述のクイーンの位置に設定します

したがって、「アルゴリズムは C または D のいずれかをランダムに選択して移動する...」というのが最初の選択ですが、「どちらも同じ数の競合を作成するため」ではありません。C または D は、1 つ以上の競合に参加しているためです。

「競合の最小数を持つ値が複数ある場合、ランダムに1つを選択する」と述べています。アルゴリズムの基本的な定式化を理解すると、最小制約検索と見なされるこの変更があるように見えます。

于 2013-12-30T00:33:06.367 に答える