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 deﬁned prooblem whose objective is ﬁnding solution that satisﬁes 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 deﬁned 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 satisﬁes all constraint. planted solution による問題作成のイメージを次の図.2 に示す。 4 Results 1. Only constarint is an eﬀective 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)