ネットワーク最適化問題の解法高速化・高精度化に関する研究

本研究の目的は,ネットワーク最適化問題に対する解法の高速化あるいは高精度の近似解法の設計に関する研究を行うことであった.一般的にこの種の最適化問題は総当たり的解法を余儀なくされるため,一つの研究方向として,いかに高速に解くか,あるいは高速に解ける問題の族を発見することがある.他方,問題によっては規模の増大が避けられない場合もあり,これに対しては高速な近似解法の設計がある.並列・分散処理による高速化に向かって研究を進めるためには逐次処理についての検討が不可欠である.今年度の研究ではこれに重点を置いた.その成果(次ページの研究発表の項に示す15件)を以下の1〜5にまとめる.1.耐故障ネットワーク構成問題について:リンク故障への対応の抽象化である辺連結度に関する辺付加問題について,局故障への対応の抽象化である点連結度に関する辺付加問題について,合せて4件(次ページの1,6,7,15番目)を発表した.2.通信プロトコル等の設計検証に関して:デットロック検出について3件(5,8,9番目)の成果を発表した.3.スケジューリング問題解法に関して:その解法の基礎であるペトリネットの発火系列問題について1件(2番目),実時間スケジューリングについて1件(4番目),スケジューリングのペトリネットによるモデル化について1件(3番目)の成果を,それぞれ発表した.4.プリント基板設計問題に関して:所与の形状を持つプリント基板の設計法について2件(11,13番目),3層配線問題について1件(12番目)を、それぞれ発表した.5.グラフ描画に関して:上記の1と4の両方に関連するが,グラフやネットワークに対する所与の制約条件を満たす描画法について2件(10,14番目)を発表した.

本研究の目的は,ネットワーク最適化問題に対する解法の高速化あるいは高精度の近似解法の設計に関する研究を行うことであった.一般的にこの種の最適化問題は総当たり的解法を余儀なくされるため,一つの研究方向として,いかに高速に解くか,あるいは高速に解ける問題の族を発見することがある.他方,問題によっては規模の増大が避けられない場合もあり,これに対しては高速な近似解法の設計がある.並列・分散処理による高速化に向かって研究を進めるためには逐次処理についての検討が不可欠である.今年度の研究ではこれに重点を置いた.その成果(次ページの研究発表の項に示す15件)を以下の1〜5にまとめる.1.耐故障ネットワーク構成問題について:リンク故障への対応の抽象化である辺連結度に関する辺付加問題について,局故障への対応の抽象化である点連結度に関する辺付加問題について,合せて4件(次ページの1,6,7,15番目)を発表した.2.通信プロトコル等の設計検証に関して:デットロック検出について3件(5,8,9番目)の成果を発表した.3.スケジューリング問題解法に関して:その解法の基礎であるペトリネットの発火系列問題について1件(2番目),実時間スケジューリングについて1件(4番目),スケジューリングのペトリネットによるモデル化について1件(3番目)の成果を,それぞれ発表した.4.プリント基板設計問題に関して:所与の形状を持つプリント基板の設計法について2件(11,13番目),3層配線問題について1件(12番目)を、それぞれ発表した.5.グラフ描画に関して:上記の1と4の両方に関連するが,グラフやネットワークに対する所与の制約条件を満たす描画法について2件(10,14番目)を発表した.