Approximation algorithm for CSP - 電気通信大学

Technical english Abstract
Approximation algorithm for CSP
1131106 Tatsuhiro Fukuzawa
Advisor:Jun Tarui
1
Introduction
In the real world, problem of combination, such as allocation or transportaion or scheduling, is often main problem. Therefore, I pay attention to CSP(Constraint Satisfaction Problem)
which have high capablity of formularization for
these combination problem in this research. The
objective of this research is implementation of
argorithm that can get better approximate solution. アルゴリズムの評価は approximation
rate(=アルゴリズムによって得られた解が満たし
た制約数 ÷ 最適解が満たす制約数) を用いて行う。
本研究で例題として用いるのは主に同研究室の下
重が実装した例題生成プログラム [2] による問題
である。
2
Objective
As a Objective of this resaearch, どのような問
題に対してもなるべく高い近似率が保証できる近
似アルゴリズムの実装をすることにした。
3
3.1
Summary of CSP
What’s CSP?
CSP is an abbreviation of ”Constraint Satisfaction Problem” CSP is defined prooblem whose
objective is finding solution that satisfies plural
constraints. 本研究で取り扱う問題は 0-1 から成る
ビット列である解といくつかの制約条件によって
構成される。2CSP とは制約条件が 2 個以下の変数
に関する制約となっている CSP であり、3CSP と
は制約条件が 3 個以下の変数に関する制約となっ
ている CSP である。本研究では解の変数の数を
n、制約条件の数を m で表現するものとする。
3.2
Form of constraints
CSP の制約条件は、変数を表現する 10 進数と
制約条件の内容に関するビットにより構成される。
2CSP の場合、各ビットはそれぞれ図.1 のような
意味を持つ。図の例では”(X2 , X5 ) は (0,0) もしく
は (1,0) である”という意味の制約となる。
Literal number
2
5
0
0
1 0
1 0
0
1
1
0
1
1
Pairing of numbers
Fig 1: Form of constraint
3.3
Only constraint
We defined Only constraint as constraint
which admit only one pairing of numbers. For
example,
1 3 0001
2 4 0100
3.4
Symmetry constraint
制約条件の中で、制約の内容を表す n ビット列
X = X0 , X1 , . . . , Xn−1 において
Xi = 1(0 ≤ i ≤ n − 1) であれば Xn−1−i = 1 を
満たしている制約を対称制約と呼ぶことにする。
つまり”ある変数の値の組み合わせを許していれ
ばその組み合わせをフリップした解も許す”といっ
た性質を持つ制約を対称制約と呼ぶ。
例えば以下に示すような制約はすべて対称制約
である。
1 3 1001
1 2 0110
3.5
Planted solution
planted solution is a special method of generation problems. It can generate problems
which has optimal solution that satisfies all constraint. planted solution による問題作成のイメー
ジを次の図.2 に示す。
4
Results
1. Only constarint is an effective hint for problem by Planted solution.
2. ランダムに作成された問題では全ての制約を
均等に着目して解を探索するアルゴリズムが
有効
Solution which is planted
X0
X1
X2
X3
X4
1
0
0
1
0
NG
OK
1 4 0100
1: 制約条件 m = 1000 の問題
literal
AR
Only
100
100% 119
120
99.6% 144
150
99.1% 133
180
93.5% 122
190
96.3% 129
200
94.5% 121
300
90.9% 130
400
89.9% 133
500
85.6% 120
OK
1 3 1111
1 2 1000
Constraint which is generate at random
Fig 2: Generation by Planted solution
3. theorem1. 対 称 制 約 の み で 構 成 さ れ る
planted solution による問題は最適解を 2 つ
持つ
7
Conclusion
7.1
5
Algorithms
result of research
開発・実装したアルゴリズムのうち特に有用で
あった次の 3 つについて述べる。Above all, この中
でも planted solution による例題に対して r-sort
は特に有効であった。
どのような問題に対しても良い近似ができる万
能なアルゴリズムの実装を目標とした本研究であっ
たが結果は planted solution によって作成された
問題に対してのみ有効な r-sort の実装に留まった。
また目標にはなかったが、理論的な問題解析の
過程で命題を 1 つみつけた。
5.1
7.2
sort
sort is algorithm which は制約を厳しい順に
ソートしてから解を求めるというアルゴリズムで
ある。満たしづらい制約を優先的に満たすように
解の値を決定することで、より多くの制約を満た
せるのではないかと考えこのアルゴリズムを実装
した。このアルゴリズムはそのままでは良い近似
ではなかったが後述の r-sort などに改良すること
で様々な種類の問題に対応できるようになった。
5.2
order
order は解の変数それぞれに対して 0,1 のどち
らの値の方がより多くの制約を満たせるかの判定
を行い、解を決定するアルゴリズムである。この
アルゴリズムは問題の種類に関わらず良い近似が
得られたが、後述の r-sort ほど planted solution
の例題に対して有効とは言えなかった。
5.3
r-sort
r-sort は制約を厳しい順にソートし、最厳制約
に基づいて解を決定した後、決定されなかった変
数に対してランダム探索をするというアルゴリズ
ムである。”planted solution による問題では最厳
制約が示す値 = 最適解”という性質を利用したも
ので planted solution の問題には非常に良い近似
が得られた。
6
アルゴリズム r-sort の分析
ここでは planted solution の問題に対して最も
有効だと考えられる r-sort のアルゴリズムでど
れくらいのサイズまで良い近似が得られるのかを
試したデータを示す。変数の数、近似率に加えて
r-sort のアルゴリズムにおいては重要な最厳制約
の数も示す。問題はすべて 2CSP とする。
Open questions
未解決である課題を下に挙げておく。
1. order をベースにしたアルゴリズムの改良
order のアルゴリズムは一番さまざまな問題に
対応できるものであることが結果からわかる。そ
こでさらに解の変数の値を少し変えていくという
処理を追加すると、さまざまな問題に対してより
高い近似率を保証できるアルゴリズムとなるので
はないかと考えた。
参考文献
[1] 野々部 宏司/茨木 俊秀 (1997)「汎用アルゴ
リズムとしての CSP(制約充足問題) に対する
タブー探索アプローチ」
『数理解析研究所講究
録』1015 巻(1997 年) pp.124-136. 京都大学
数理解析研究所
[2] 下重政廣 (2011)「CSP の例題生成アルゴリズ
ム」『2011 年電気通信大学情報通信工学科卒
業論文』
[3] 「 制 約 充 足 問 題 」OR 辞 典 Wiki
http://www.orsj.or.jp/wiki/wiki/index.php
(アクセス 1/21, 2011)