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)
© Copyright 2024 ExpyDoc