【研究分野】情報学基礎

【研究領域課題番号】21300003 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / 組合せ剛性理論 / 最速フロー / 最速避難計画 / パネルヒンジフレームワーク / 分子剛性予想 / Lamanの定理 / 組合せ剛性 / 避難計画問題 / 普遍的最速フロー / 計算幾何学 / 剛性理論 / 避難計画 / 時間拡大ネットワーク / 動的ネットワーク

【研究成果の概要】

(1)分子構造をモデル化した分子フレームワークはたんぱく質の挙動解明に用いられるなど応用上非常に重要なモデルであるが、その剛性に関する重要な未解決予想であったMolecular剛性予想を、このプロジェクトを通じてこの未解決問題を肯定的に解決する事に成功した.
(2)最適な避難計画を求める問題をモデル化した動的ネットワークフローに対する研究に関して,グリッドネットワークを一般化したネットワークにおける普遍的最速流問題に対する多項式時間アルゴリズムの開発という理論的な成果と,動的ネットワークフローを用いた京都における避難所の収容人数の評価という応用的な成果を得ることができた.さらにこのモデルと手法は、徳島市沖洲地区に関する津波避難ビルデータへ適用し、新し知見を得ることができた。

【研究種目】基盤研究(B)

【研究期間】2009 - 2012

【配分額】11,440千円 (直接経費: 8,800千円、間接経費: 2,640千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】15740062 (KAKENデータベースで見る）

【研究キーワード】

応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 / 組合せ最適化 / 計算幾何学 / 離散数学

【研究成果の概要】

巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。
TSPの近似解法を考える際、木は重要な概念の1つである。この木は、グラフ理論においてもさまざまな研究がなされている。例えば、与えられたグラフG_1,…,G_k,Hに対し、HがG_1,…,G_kを辺素に含むことができるかどうかを判定する問題はNP完全に属しており、一般にその判定は難しい。そこで、さまざまなグラフのクラスに関する十分条件について研究されてきた。この問題に対し、特にHを平面グラフにした場合どのようなグラフを辺素に含むことができるかに興味を持っている。今年度は2つの木の平面グラフへの埋め込みに関する研究を行った。
Garciaら(2002)は、2つのスターでない木はある平面グラフに辺素に埋め込むことができると予想した。同じ論文で、Garciaらは、スターでない木とパスはある平面グラフに辺素に埋め込めることを示している。予想の解決を目標に、より広い木のクラスについて考えた。まず、スターのいくつかの辺を1回細分して得られるグラフとスターでない木に、2つのキャタピラ、について榎本,太田,神田,枡井とともに示した。また、直径5以下のキャタピラとスターでない木に関して構成的に証明し、最終的にスターでないキャタピラとスターでない木について太田とともに示した。この証明方法が予想の解決の糸口にならないかを考察することが今後の課題である。

【研究種目】若手研究(B)

【研究期間】2003 - 2005

【配分額】3,700千円 (直接経費: 3,700千円)

【研究分野】システム工学

【研究領域課題番号】06855045 (KAKENデータベースで見る）

【研究キーワード】

LSI / 設計自動化 / CAD / レイアウト / アルゴリズム / データ構造 / 計算幾何学

【研究成果の概要】

本研究は、素子や配線を図形そのものとしてとらえることによってLSIのレイアウト設計を行う、複雑な設計規則に柔軟に対応する新設計方式を確立することを目的として行われた。本研究の成果を以下にまとめる。
1.スケッチ表現に基づく多層レイアウトシステムの開発:配線情報のラフスケッチを計算機上で表現する方式として「スケッチ表現」を提案し、計算機上に実装した。これは、三角形分割を基本としたデータ構造に基づいており、概略配線、配置および概略配線の微調整、コンパクション、最終配線形状への変換といった基本ソフトウェアからなっている。特に本年度は、概略配線手法、配線可能性検証手法、および、スケッチ最適化手法に焦点をあて、提案手法を学会で発表した。これにより、柔軟性の格段に高いレイアウト設計が可能となった。また、提案手法がLSIの信号線の設計のみならず、クロック配線、電源・グランド配線やパッケージの設計にも適用可能であることを示した。
2.最適グラフ描画手法の構築:与えられたレベル付きグラフを枝の交差が最小となるように平面上に描画する問題に対して最適解を求める手法を構築した。また、計算機に実装することにより、その有効性を示した。基本的データ構造に二分決定グラフ(BDD:Binary Decision Diagram)を用いることにより、従来では実用的な時間内に解くことができなかった規模の問題が解けることを示した。これは単に問題を解いたというだけではなく、実現可能解のすべてを陰に列挙可能としているところに価値がある。この手法はデータフローグラフの描画、ネットリストの描画などに応用される。

【研究種目】奨励研究(A)

【研究期間】1994

【配分額】900千円 (直接経費: 900千円)

【研究分野】情報工学

【研究領域課題番号】02302047 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / 並列処理 / 組合せ問題 / 離散構造 / 計算幾何学 / ネットワ-ク / 分散処理

【研究成果の概要】

初年度には離散構造を処理するアルゴリズムについて種々の観点から調査・検討を行った.これにより現在のアルゴリズムの限界や新しいアルゴリズム論に関する知見を得るに至った.特に並列・分散アルゴリズムに関して現状の調査・検討が行われ,新しいアルゴリズムの設計のための土台が築かれた.さらに,最終年度には,前年において得られた研究成果を土台として,総合的見地から種々の新しいアルゴリズムを設計解析した.現在から将来に向け有用となる近似・確率・並列・分散・ハ-ドウェアアルゴリズムに関する新しい知見を得るに至った.さらに計算理論に関する成果も種々得られた.代表的な成果を以下に示す.
1.VLSIのレイアウト設計における重要な問題に一つに回路分割問題があり,これまでに様々なアルゴリズムが提案されてきている.本研究では回路を構成するモジュ-ルの集合とネットリストが与えられたとき,モジュ-ル集合を2分割して左右の部分の面積をほぼ等しくし,かつ両方の部分に跨る配線の本数を最小にする問題に関するアルゴリズムを与えた.グラフの表現に基づいた方法と平面上の点集合に写像した上で点集合の2分割問題を解く方法を比較した.この結果はアルゴリズムを構成するときにグラフモデルと幾何モデルのいずれを用いるかを決定するために有用である.
2.NP完全問題などの複雑さの高い問題に対して,平均時間的には効率良く解くと主張されるアルゴリズムが数多く開発されている.それらの評価は通常解析的になされるが,実際的立場の研究者からは,実際に計算機実験によっても行われるべきだとの指摘がある.本研究では充足可能性問題に対するこのようなアルゴリズムの評価に用いるべき例題生成はいかにあるべきかについて調査・検討した.さらに,その要求を満足するような例題生成アルゴリズムが存在することを示した.

【研究種目】総合研究(A)

【研究期間】1990 - 1991

【配分額】10,800千円 (直接経費: 10,800千円)