ネットワーク最適化問題の効率的解法に関する研究

本研究の目的は,ネットワーク最適化問題に対する効率的な解法の設計あるいは解法の高速化に関する研究を行うことであった。一般的にこの種の最適化問題は総当たり的解法を余儀なくされるため,一つの研究方法として,いかに高速に解くか,あるいは高速に解ける問題の族を発見することがある。他方,問題によっては規模の増大が避けられない場合もあり,これに対しては高速な近似解法の設計がある.並列・分散処理による高速化に向かって研究を進めるためには逐次処理についての検討が不可欠である.今年度の研究ではこれに重点を置いた.その成果(次ページの研究発表の項に示す11件)を以下の(1)〜(4)にまとめる.(1)耐故障ネットワーク構成問題について:リンク故障への対応の抽象化である,辺連結度に関する辺付加問題について2件,局故障への対応の抽象化である点連結度に関する辺付加問題について1件,それぞれの成果を発表した.また,(故障監視点の設置問題の抽象化として)点被覆及び連結点被覆問題について1件の発表を行なった.(2)通信プロトコル等の設計検証に関して:デットロック検出について2件の成果を発表した.(3)スケジューリング問題解法に関して:その解法の基礎であるペトリネットの発火系列問題について2件の成果を発表した.(4)プリント基板設計問題に関して:所与の形状を持つプリント基板の設計法について1件,回路設計に有用なFPGA(Field-Programmable Gate Arrays)テクノロジーマッピングについて1件,それぞれ発表した.

本研究の目的は,ネットワーク最適化問題に対する効率的な解法の設計あるいは解法の高速化に関する研究を行うことであった。一般的にこの種の最適化問題は総当たり的解法を余儀なくされるため,一つの研究方法として,いかに高速に解くか,あるいは高速に解ける問題の族を発見することがある。他方,問題によっては規模の増大が避けられない場合もあり,これに対しては高速な近似解法の設計がある.並列・分散処理による高速化に向かって研究を進めるためには逐次処理についての検討が不可欠である.今年度の研究ではこれに重点を置いた.その成果(次ページの研究発表の項に示す11件)を以下の(1)〜(4)にまとめる.(1)耐故障ネットワーク構成問題について:リンク故障への対応の抽象化である,辺連結度に関する辺付加問題について2件,局故障への対応の抽象化である点連結度に関する辺付加問題について1件,それぞれの成果を発表した.また,(故障監視点の設置問題の抽象化として)点被覆及び連結点被覆問題について1件の発表を行なった.(2)通信プロトコル等の設計検証に関して:デットロック検出について2件の成果を発表した.(3)スケジューリング問題解法に関して:その解法の基礎であるペトリネットの発火系列問題について2件の成果を発表した.(4)プリント基板設計問題に関して:所与の形状を持つプリント基板の設計法について1件,回路設計に有用なFPGA(Field-Programmable Gate Arrays)テクノロジーマッピングについて1件,それぞれ発表した.