【動画講座】CS 188 CSP1

リンク

https://www.youtube.com/watch?v=81z2ANjQcH4

画像

内容

Constraint Satisfaction Problem

CSPはSearch Problemの一つのジャンル。
定義域の中で、ちょうどよい変数$X$を見つけて、制約を満たす変数の割当を行う問題。

大事なのは、
最適でなくてよく、制約を満たせば良いというものである。

問題定義

Domainの中で、変数$X$を動かして、制約の集合内を満たす$X$を見つける。

Constraint Graph

各ノードを変数として、ノード間に不等式などの制約のエッジを設ける。
これによって、どのノードに制約があるかがわかる。

この講義では、エッジは必ず$2$つをつなぐものであり、複数の関係は比べない。

探索方法

  • BFS

幅優先探索、すべて探索するのでCSPでこれをやると死

  • Backtrack

枝刈り方。関係ない、ありえないものを削除していく。
高速化が行える。

Forward Check

実行してから、この頂点以降は正しいか?で枝刈りをするのではなく

操作$v$をしたとき、そこから満たされない頂点を先に枝刈りする。
競プロでもよくある。

Consistency

アークの一貫性。

制約グラフにおいて、各エッジを有向グラフとしてみる。

そして、出る方向の出る元が正しいか?をチェックし続ける。
出る先は正しいという仮定がある。

出る元の頂点にありえる候補を削っていくと、連鎖的に満たさない状態が削られていく。

これによって、高速に無駄な部分を連鎖的に消せる。
定数倍の改善になりそう