離散数学から見たおむすび

離散数学から見たおむすび
・まず、離散数学とは？
離散数学は、計算機科学やオペレーションズ・
リサーチとの密接な関係で、20世紀に急激に発展
し、様々な分野に分かれています。「離散」の反
対は「連続」です。つまり、離散とは直感的に言
えば「とびとび」になっているものです。
グラフの節点や枝に重さや長さなどの数値が割
り当てられているものを離散数学の用語でネット
ワークと呼びます。それでは、以下のネットワー
ク問題を解いてみましょう。
おむすびの具を手に入れる
最短距離を考えよう！
図１：入口から出口への最短路は？
図１のように11種の食材があり、各々が道でつ
ながっています。食材から食材へは、それらの道
を使って移動しますが、それぞれの道を通抜ける
には、その脇に書いてある時（分）だけかかりま
す。食材をGETする時間は無視できる（つまり0
分）とします。
・「すべての可能性の有る路を調べる」という
「しらみつぶし法」で解いてみると？
同じ節点を二度通らない最短時が存在するこ
とが分かるので可能性のある路の数は有限個に
なり、理論上は計算可能ですし、節点数が少な
いときには実用上も有効です。しかし、節点数
がちょっとでも多くなるとこの方法は使い物に
なりません。仮に節点毎に選択可能な分岐は平
均３個だったとしても、調べなければいけない
ｎ
−１
路の数は約3
個になりますがこれは、指数
関数であるためｎの増加とともに急激に増大し
ます。
例えば、n=10のときは、2万弱程度ですが、
10
n=20だと約1.16×10 、n=100だと約
47
1.72×10 という具合に、天文学的な数値に
なってしまい、これはいくら計算機の能力が発
達しても明らかに計算不可能です。よって、効
率的な計算方法（アルゴリズム）が不可欠です。
例えば、入り口から昆布を経由し、高菜を
GETすると
5＋6=11
と分かります。
あなたは、入り口にいて出口まで行くと最短
で何分で行くことが出来るでしょうか？その時
の経路も求めてみましょう。
【続・離散数学から見たおむすび】のコラムに
続きます！
本記事の担当：Nagare Arisa（奈良女子大学）

Download Report