Welcome to Hirata Lab's home page

研究領域

　平田研究室で現在または近年研究されていた内容などを簡単に紹介します。
 レイアウト設計
 近似アルゴリズム
 ＶＬＳＩ
 暗号理論
 画像処理アルゴリズム
 並列アルゴリズム
 グラフアルゴリズム
 組合わせ最適化問題
 量子計算

アルゴリズムについて

アルゴリズムは情報工学・情報科学の基礎を支える重要な分野である。今日、情報処理の対象は、音声や画像、さらに記号や知識処理などへとますます多様化しており、また、情報処理の形態も、シングルプロセッサでの比較的単純な処理から、複数プロセッサによる並列・協調処理や、ネットワークを介しての分散処理へと移行している。そのような新しい情報処理を指向したアルゴリズムやデータ構造について、理論面および応用面の研究を行っている。

近似保証付きアルゴリズムの設計

グラフ問題や組合わせ問題のような離散構造をもつ問題のほとんどはＮＰ完全(最適化問題の場合はNP困難)であり、現在の計算機では計算時間が膨大になり手に負えない問題である。しかし、たとえＮＰ困難であっても、計算機を用いて解かなければならない離散最適化問題が情報処理の現場ではますます増えている。たとえば、ＯＲの分野では、より大規模なネットワーク上での資源割り当て問題やスケジューリング問題を解かなければならない。また、人工知能の分野では推論処理のような高度な計算を要求する問題がつぎつぎと発生している。このような現実を踏まえ、たとえ求まる解が最適でなくとも、それに十分近いことを理論的に保証できる近似アルゴリズムの設計論が今日の重要な研究テーマとなっている。
本研究室では、グラフ問題を中心とした代表的離散最適化問題に対する高性能近似アルゴリズムを開発するとともに、これまでに提案されている近似アルゴリズムを設計手法の立場から調査・分類し一般的設計法の構築に向けて研究している。グラフ問題に関しては次のような成果をあげている。
・均等辺彩色問題の高性能アルゴリズムの開発
・重み付き独立集合問題に対する近似アルゴリズムの開発
・ネットワーク設計問題に対する組合わせ的近似アルゴリズムの開発

近似困難性

ＮＰ困難である組合わせ最適化問題に対し、最適解とアルゴリズムの出力する解(近似解)との比を保証するアルゴリズムを近似アルゴリズムといい、その日を近似比率(または近似保証)という。近似困難性の研究では、その近似比率の限界を求めることを目標とする。グラフの性能πに対しその最小辺縮約問題とは、与えられたグラフの辺を縮約してそのグラフがπを満たすようにする際の最小本数の縮約辺を求める問題であり、ＮＰ困難であることが知られている。本研究室ではこの問題の近似アルゴリズムが達成する近似比率に対し下界を示した。

発見的アルゴリズム

社会で現れる様々な問題は多くの場合、ＮＰ困難な問題で、現実的な計算時間で最適解を得ることは非常に困難である。良質の解を少ない計算時間で探索するための基本戦略として、局所探索法がよく知られている。局所探索法とは、適当な解から始めて、現在の解xの近傍N(x)内に改善解があれば移動するという操作を反復する手法である。局所探索法は、単純な手法であり実装が容易であるため多くの問題に自然に適用することができる基本的な最適化ツールとなっている。しかし現実には、単純な局所探索法のみでは満足のいく結果が得られず、より高性能なアルゴリズムが必要となることも多い。この目的のために、近年ではメタヒューリスティクスと呼ばれる手法がよく用いられる。メタヒューリスティクスとは、最適化問題(特に組合わせ最適化問題)に対する実用的な探索手法を設計するための一般的な枠組みを与えるものである。これには数多くの手法やアイデアが含まれるが、その中には、局所探索法を基本として、その性能を高めるための手法と位置づけられているものが多数存在する。代表的なものとしては、GRASP法(greedy randomized adaptive search procedure)、反復局所探索法(iterated local search)、アニーリング法(simulated annealing)、タブー探索法(tabu search)などが挙げられている。本研究室では、様々な問題に対して実用的なアルゴリズムの開発を行っている。