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

提高网络优化问题求解方法速度和精度的研究

基本信息

批准号：
08680371
负责人：
渡邉敏正
金额：
$ 1.47万
依托单位：
Hiroshima University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

项目摘要

本研究の目的は,ネットワーク最適化問題に対する解法の高速化あるいは高精度の近似解法の設計に関する研究を行うことであった.一般的にこの種の最適化問題は総当たり的解法を余儀なくされるため,一つの研究方向として,いかに高速に解くか,あるいは高速に解ける問題の族を発見することがある.他方,問題によっては規模の増大が避けられない場合もあり,これに対しては高速な近似解法の設計がある.並列・分散処理による高速化に向かって研究を進めるためには逐次処理についての検討が不可欠である.今年度の研究ではこれに重点を置いた.その成果(次ページの研究発表の項に示す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番目)を発表した.

本研究的目的是对网络优化问题的加速求解或设计高精度的近似解进行研究。通常，此类优化问题需要暴力求解方法，因此，一个研究方向是如何解决。快速解决问题，或者发现一系列可以快速解决的问题。另一方面，根据问题的不同，有时规模的增加是不可避免的，为此，有必要设计近似解法为了继续加速并行和分布式处理的研究，有必要考虑顺序处理。今年的研究集中于此。结果（见下页的研究介绍）第1节中所示的15个案例）是总结如下1至5 1.关于容错网络配置问题：关于边缘连通性相关的边缘添加问题，这是处理链路故障的抽象，处理站点故障的抽象。关于该问题，共进行了4次演示（下页第1、6、7、15号）。 2.关于通信协议等的设计验证：3个案例的结果（第5、8号）。，和9）关于死锁检测3.关于调度问题解决方法：一篇关于Petri网的发射序列问题的论文（第二期），这是解决方法的基础，一篇关于实时调度的论文（第四期）。），以及使用 Petri 网的调度模型。 4.关于印刷电路板设计问题：给定形状的印刷电路板设计方法的2个结果（第11和第13），以及3层布线问题5.关于图形绘制：与上述1和4相关，两篇论文（10、14）公布。