手法の説明

制約の表現

　実際の問題では、問題解決に必要な制約条件が多種多様であり、計算機上での表現が困難である。

例１）　時間割編成問題（一部）

1. 教官は同時に２つ以上の科目を担当できない。
2. 裏番組は異なるグループの重複可能な科目同士でのみ作ることができる。
3. コマ単位の２科目間に「連続性」があり、その関係を満たさなければならない。
4. 低学年および高学年の必修科目をなるべく同時に実施しない。
5. 同曜日に実施される同分野の科目の時間数をなるべく制限する。

例２）　室内レイアウト問題（一部）

1. 機器を利用するための必要最低限のスペースを確保しなければならない。
2. 出入口の周囲にスペースを空けなけばならない。
3. 出入口と各機器とを結ぶ通路が存在しなければならない。
4. 類似・関連する機器同士は近くに配置する。

例３）　日本語点字変換（1996年度研究テーマ、一部）

1. 字種の変わり目（ひらがな→｛カタカナ or 漢字｝）で区切る。
2. 補助用言の前で区切る。
3. 助詞の後ろを区切る。
4. 助詞が連続した場合、一番最後でのみ区切る。

　これらの制約を計算機で効率よく扱うためには、制約を整理・分類することが必要であると考えられる。 その際に考えられる点は以下の通りである。

• 何に対する（もしくは何と何の関係に対する）制約であるのか？
• 参照するデータは何であるのか？
• 必ず満たさなければならないのか？（重要度）
• 実現可能か？（複雑さ、計算コスト）

　本研究では、制約条件を分析することで、それぞれの性質により分類できることに注目した。 乱雑な大量のルールでは冗長性を多く含み、計算にかかるコストが大きくなる。 そこで、本研究では、実際問題に適応できる制約表現の枠組みを提案することを目的として、現在研究を行っている。

探索手法

　探索とは、多くの可能性の中から、特定の問題の条件に合った解を見つけ出すための戦略である。 ここで対象とする組合せ最適化問題は、ＮＰ困難であるという、 計算の複雑さの意味で本質的に困難であることの理論的根拠があり、汎用な解法は存在しない。

　制約充足問題などの組合せ探索問題の解法は、大きく次の２通りに分けることができる。

• 厳密解法
• 近似解法

　以下に、それぞれの解法を簡単に紹介し、本研究で用いた解法を説明する。 ここで紹介する解法については、次のマップカラーリング問題を用いる。 この問題は、各ノード（変数）に色（値）を割り当てる問題であるが、 隣接するノード間には同じ色を塗らないという制約がある。

厳密解法

《具体的な探索手法の例》

　木探索法の具体例を以下に示す。ここでは、rootから、変数V1,V2,V3の順に値を割り当て、 制約を満たさなくなると、バックトラックにより別の割当を試みる。 このように値の割当順で結果が異なる。さらに、変数の割当順でも結果は異なる。

《特徴》

• アルゴリズムの有限性が保証されている。
• 探索空間が膨大であると、実用時間内に解が求まらない。

近似解法

《具体的な探索手法の例》

　山登り法の具体例を以下に示す。それぞれ四角で囲まれたものは、解候補である。 ×印は、その変数が制約に違反していることを示す。 図４）のように探索が失敗することがある（局所最適解という）。

《特徴》

• アルゴリズムの有限性は満たされない。
• 探索空間が膨大であっても、実用時間内にそれなりに良質な解が得られる。
• 探索の成否や計算コストは、初期値に依存する。

本研究で用いた解法

　本研究で扱う問題は、探索空間が膨大であるため、近似解法の山登り法を用いることにした。 また、制約の表現の問題点からも、既存の探索法をそのまま使うのでは対処しきれないため、 人間とシステムが対話によって協調して探索を進めるようにした。

　 　以下に、本研究で開発した時間割編成システムの処理の流れを図で示す。