平均時間的に高速な組合せ最適化アルゴリズムとその実験的評価法の研究

閲覧数: 2
ダウンロード数: 0
このエントリーをはてなブックマークに追加

平均時間的に高速な組合せ最適化アルゴリズムとその実験的評価法の研究

フォーマット:
助成・補助金
Kyushu Univ. Production 九州大学成果文献
タイトル(他言語):
Studies on Averagingly Fast Combinatorial Algorithms and Experimental Evaluation of Their Performances
責任表示:
岩間 一雄(九州大学・工学部・教授)
IWAMA Kazuo(九州大学・工学部・教授)
本文言語:
日本語
研究期間:
1992-1993
概要(最新報告):
1.論理式の充足可能性問題に対するアルゴリズムを実験的に評価するためのテスト例題生成システムの実働化を行なった。生成例題の答である充足可能か否かを外部から指定して例題を生成できるようにし,さらに,アルゴリズムの性能を様々な角度から測定できるように生成例題のパラメータを制御できるようにした。各論理変数の出現頻度,和項と変数の数の比,さらには充足可能例題の場合の充足解の個数等のパラメータである。我々の生成した例題が,ベル研等米国東部の主要研究機関で組織されたコンソーシアムであるDIMACSの公式ベンチマークに選ばれ,世界的に広く利用されている。 2.局所探索法については,項の重み付けという新種法を発見し,40変数程度でも100倍以上性能が改良されることを示した。 3.このような例題生成の基本的考え方を,論理最適化システムの評価のための例題生成へと発展させた。テストのための論理回路生成の基本的考え方は,(簡単な)初期回路から論理関数の等価性を保存する基本変換の繰り返し適用によって(複雑な)テスト回路へと変換していくことである。任意の回路から任意の等価な回路へ変換が可能な完全な基本変換の集合を,NAND回路とAND-OR-NOT回路に対して既に得ている。代表的な論理最適化システムであるSISの評価に応用され,興味深い結果を得た。本年度のDACでの発表が決まっている。 続きを見る
本文を見る

類似資料:

3
定理自動証明技術の計算論的研究 by 岩間 一雄; IWAMA Kazuo
10
Fusion360操作ガイド : 次世代クラウドベース3DCAD : 3Dプリンターのデータ作成にも最適!! by スリプリ(3Dワークス株式会社); 三谷, 大暁; 別所, 智広; 坂元, 浩二
3.
定理自動証明技術の計算論的研究 by 岩間 一雄; IWAMA Kazuo
10.
Fusion360操作ガイド : 次世代クラウドベース3DCAD : 3Dプリンターのデータ作成にも最適!! by スリプリ(3Dワークス株式会社); 三谷, 大暁; 別所, 智広; 坂元, 浩二
11.
CAGDのための曲線・曲面理論 : 実践的利用法 by Farin, Gerald E.; 山口, 泰