夢ナビ夢ナビは、さまざまな言葉をデータベースから検索・閲覧し、将来の進路を決める“きっかけ”を提供します。

講義No.06145

アルゴリズムの工夫が、さまざまな問題を解決する

カーナビにも数学が生かされている!?

 目的地は決まっているけれど、ルートがわからないときに頼りになるカーナビは、出発地から目的地までの最短ルートを計算し表示してくれます。実はこれには、数学の「離散最適化問題」の一つである「最短路問題」のアルゴリズム(解を求めるための計算方法や手順)が使われているのです。このアルゴリズムはいろいろな問題に応用が可能で、例えば、ギターやピアノを弾くとき最適な指の運び方を導きだすときにも役立ちます。

モデル化・抽象化して問題を見通す

 離散最適化問題を解くために最初に行う作業は、構成する要素の「つながり方」に注目し、モデル化することです。例えば、道路網における交差点を○(マル)、目的地に向かう道路を矢印の線、距離を数値で表し、ネットワークを簡単なグラフ(図形)に置き換えます。問題を抽象化して考えることで、問題の見通しをよくするのです。
 このような方法で解く代表的な問題として、もう一つ、「最小木(さいしょうぎ)問題」があります。これはすべての地点をつないだときに線の長さが最も短くなる解を見つける問題で、例えば、通信網をできるだけ安い費用で設計する場合や、画像処理ソフトで背景を自動抽出するプログラムなどにも応用されています。

より効率的な計算方法を考えるアルゴリズム研究

 こうした問題を解くときは、コンピュータにアルゴリズムを指示するためにプログラミングを行います。しかし、組合せがともすれば膨大なパターンになるため、単純なアルゴリズムでは、スーパーコンピュータで計算しても解けないほどの長い時間がかかってしまいます。そこで重要なのが、高速に計算するためにアルゴリズムを「工夫すること」です。設定するパラメーターを調節したり、プログラムの書き方を変えたり、新たなアルゴリズムを開発したりすることに、この研究の面白さと醍醐味があります。アルゴリズムを工夫することが、生活に関わるさまざまな問題を解決することにつながるのです。

アイコン

講義を視聴する(1分)

アイコン

講義を視聴する(1分 その2)

アイコン

講義を視聴する(1分 その3)

アイコン

講義を視聴する(30分)

この学問が向いているかも 離散数学、離散最適化

静岡大学
工学部 数理システム工学科 准教授
安藤 和敏 先生

メッセージ

 私は、「離散最適化アルゴリズム」の研究をしています。耳慣れないかもしれませんが、実はこの分野は、私たちの生活に深く関係しています。例えばカーナビで現在地から目的地までの最短経路を見つけることも、離散最適化の問題の一つです。離散最適化問題はいろいろな方法で答えを出すことができますが、単純な計算方法では時間がかかりすぎる場合もあります。そういうときは、より高速に答えを出すための工夫が必要で、その知識の集積が「アルゴリズムの理論」です。ぜひあなたも私の研究室で、一緒に研究してみませんか。

大学アイコン
安藤 和敏 先生がいらっしゃる
静岡大学に関心を持ったら

 静岡大学は、6学部19学科と全学横断型教育プログラム「地域創造学環」を擁する総合大学のメリットを生かし、学生の知的探究心に応えることができる幅広い学問領域の教育を実施しています。大学のビジョンは「自由啓発・未来創成」であり、これは自由によってこそ自己啓発を可能にし、それを通じて、平和かつ幸福な未来を創り出すとの力強い思いを表明しています。

TOPへもどる