 |
 |
群馬大学
 |
群馬大学工学研究科 博士後期課程 電子情報工学専攻1年 岡下 綾 |
 |
当研究トップへ | |
| 1. | はじめに | |
| 2. | アルゴリズムとは何か？ | |
| 3. | 難しい問題を解くためには | |
| 4. | 中野先生の研究について  |
|
| 5. | 中野先生について | |
| 6. | おわりに | |
 |
群馬大学工学部 情報工学科 中野 眞一 助教授 |
| ４．中野先生の研究について ここでは、中野先生が行われている研究について触れたいと思います。世の中の図は美的なセンスを持つデザイナーが手作業で描いたものと、コンピュータが雑に描いたものの2種類があります。例えば、バスの路線図や様々な地図，組織図などの図をどう描くかという問題には、自由度があります。自由度があるばかりに、デザイナーがうまく描くと見やすくなったり、絵心のない人が描くと見にくくなったりします。そのような図を、あたかもデザイナーが描いたように“きれいに”コンピュータに描かせたいというのが、中野先生の研究テーマの一つです。 現在、市販されているドローソフトは、すでにデザインされた図を清書することを目的として作られているため、デザインを自動的に行ってくれません。一部のプレゼンテーション用のソフトには、組織図などの構造が簡単なグラフのみを描画する機能があります。人間が頭の中でもやもやとデザインする作業をコンピュータで自動的に行うことを、自動描画といいます。1990年ごろから自動描画に関する研究が注目されてきています。描画において、その“適切さ”の尺度は状況に応じて異なります。ですから、“適切さ”の尺度を決める問題も重要な課題になります。グラフ（「点」と「点を結ぶ線」とで構成される図形）に関する自動描画の研究は中野先生の研究における主要なテーマの一つです。
グラフを自動的に描画する際の“適切さ”の尺度は、例えば、“できるだけ線の交差を少なくする”，“対称性をできるだけ明確にする”，“点の分布をできるだけ均一にする”，“辺の長さをできるだけ均一にする”，“階層構造を明確にする”，“2辺のなす角の最小値が大きくなるようにする”，“線の折れ曲がりの個数を最小にする”，“描画の幅と高さの比が指定した値に近くなるようにする”などが考えられています。これらの条件をどの順に優先させるのかは、そのグラフが何をモデル化しているのかによって決まります。 一般に、グラフを“適切に”描画する問題は、いくつかの適切さの尺度を、尺度間の優先順位を考慮しながら最適化する問題として定式化できます。このように、いくつかの条件を満たすものの中で最も良いものを見つける問題を最適化問題といいます。最適化問題には、高速なアルゴリズムが知られていない問題や、理論的には高速でもコーディングがとても難しい問題が数多く存在します。中野先生は、最適化問題に対する高速でコーディングが簡単なアルゴリズムに関する研究を行っています。さらに、グラフを自動描画するソフトウェアを開発中です。また、2次元平面でなく3次元空間へグラフを描画することや、構造が次第に変化していくようなグラフをアニメーションを用いて描画することなど、グラフの描画を少し拡張した問題も研究対象となっています。 ところで、コンピュータで扱うことのできる電子地図は拡大や縮小が自由に行えます。しかし、これはそのままの意味での拡大・縮小を意味するわけではありません。例えば地名などの文字は見やすい大きさのままで、また文字は重なりや密集を避けて一番良い位置に配置したままで縮小した方が見やすくなります。地名などの文字を“適切な”場所に配置する問題も中野先生の研究テーマです。このような問題は配置問題と呼ばれており、他にも町内のゴミ集積所やポストをどこに配置するか，LSIにセルをどう配置するかなどの幅広い問題が考えられます。配置問題はコンピュータにとって、とても難しい問題の内の一つです（NP完全問題）。 また、携帯電話や個人用携帯端末（PDA）などで、様々なデータを重要性が分かるような人間にとって見やすい配置はどのようなものか？という研究にも興味を持たれています。 |
|||||||||
