研究の成果

研究上の成果

本研究では、以下の成果を得ている。まず、CMGTPとKLICとCLP(FD)との三つの 言語を用いて、チャネルルータを構築し、本研究ではじめてCLP(FD)がチャネ ルルーチング問題に十分応用できることを示した。この成果を以下の論文にま とめてある。

• Neng-Fa Zhou, Channel Routing with Constraint Logic Programming, Manuscript.

• CMGTPは、最初解、あるいは最適解を求めるのには不適切である。特に、解が たくさんあるような問題には不適切である。この問題に対処するために、 Hahnleと白井らが区間表現をサポートできるIV-MGTPを構築した。探索の中間 状態及び解を別別のファクトとして表現するのではなく、区間を用いて表現す ることによって、探索空間を縮め、解をもっとコンパクトに表現できる。

• コンパイルに時間がかかる。CMGTPは、プログラムをKLICに変換してから実行 している。 ルールの左辺に連言リテラルがたくさんあると、生成されたプロ グラムは膨大となる。この問題に対処するために、九大の長谷川研では、プロ グラムを直接実行するインタプリタを構築している。

ソフトウエアとしての成果

• route.mg4 : CMGTPのプログラム(50行)
  ネット数が10である問題を解くプログラムである。これは、CMGTPのベンチマー クとして使える。

• route.kl1,deutsch72.kl1,deutsch218.kl1 : KLICのプログラム (プロ グラム220行+データ300行)
  二つのモジュールからなる。一つは、問題に依存しない探索の部分で、もう一 つは問題における接続要求及びチャネルを記述する部分である。

• route.pl,deutsch72.pl,deutsch218.pl : CLP(FD)のプログラム (プロ グラム430行+データ300行)
  このプログラムでは、問題の記述以外に、バックトラック回数を減らすために、 以下の工夫を行なっている:(1)問題依存のHeuristicsを用いている。(2) グローバルな制約を生成している。例えば、X>YとY>Zとの二つの制約があ る場合に、X>Z+1という新しい制約を追加し、枝苅り効果を向上させる。