続・離散数学から見たおむすび 先に【離散数学から見たおむすび】の コラムをご覧ください！ ・最短路アルゴリズムのエース（ダイクストラ 法）で解いてみると？ ダイクストラ法とは？ 始点から、残りのすべての節点までの最短路と その長さを、同時に求めてくれます。基本的な考 え方は、始点に近い節点から順に距離を確定して いくものです。 まず、入口に隣接している3節点、昆布・高菜・ 鮭について、入口から（他の節点を経由せずに） 直接くる場合の距離を、仮の距離として、 dist’(鮭)＝6 dist’(昆布)＝5 dist’(高菜)＝12 とします。これは、その枝の長さそのものなので、 dist’(鮭)＝6 dist’(昆布)＝5 dist’(高菜)＝12 これは、あくまで「他の節点を経由せずに入口 から直接来る路の距離」ですので、最短路である 保証はありません。しかし、そのまま最短路に なっているものが1つ存在します。それは、3つの うち最小の路をもつ dist’(昆布)＝5 です。理由は、もしそれが最短で無いとしたら、 もっと短い路があるはずだからです。 この時点でdist’(昆布)＝5で、その最短路は ＜入口、昆布＞が確定 昆布の距離が確定したので、昆布経由でたど り着く路の距離も考えることができます。つま り、昆布に隣接している節点、高菜、タラコ、 ツナについて上記の路の計算をし、仮の距離と すると、 dist’(高菜)＝11 （すでに12という値が入っていたが、小さい方 を選ぶ） dist’(タラコ)＝12 dist’(ツナ)＝20 仮の最短路長は、 dist’(高菜)＝11 dist’(タラコ)＝12 dist’(ツナ)＝20 dist’(鮭)＝6 が得られます。先程と同様に考え、このうちの 一つは、最短路長になります。 一番短いdist’(鮭)＝6で、その最短路は ＜入口、鮭＞が確定 図２：入口と鮭までの距離が確定 ここまでの結果を図示すると図2のようになります。 ｛5｝のように中括弧で括ってあるものは、確定、 (11)のように小括弧で括ってあるものは、現在の距 離を表しています。 ここまでこればお分かりでしょうか。つまり、 入口から出口までの最短路は ＜入口、鮭、高菜、天むす、明太子、出口＞ です。また、長さは18ということになります。 図３：すべての節点の距離が確定 図3の太線で表された枝からなるグラフの形を 木(tree)と言います。この木は入口からすべて の節点への最短路を同時に表しています。ダイ クストラ法は、一つの始点（入口）から残りの すべての節点までの最短路を同時に表す最短路 木を求めることができます。 ネットワークでモデル化される問題には重要 なものが多いです。今回は、その代表として、 鉄道などの経路システムやカーナビに使われて いる、とても身近な問題を紹介しました。 本記事の担当：Nagare Arisa（奈良女子大学）
© Copyright 2024 ExpyDoc
