スキップしてメイン コンテンツに移動

ダイクストラ法

Introduction

今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this pageを見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。
このスライドはダイクストラ法を説明したスライドです。

Overview

  • アルゴリズム
  • 実装

アルゴリズム

このアルゴリズムは
  1. スタート始点のノードを決める。そして、それをAと名付ける。
  2. 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0
  3. Aの隣接ノードのリストをadj_listと名付ける。
  4.  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj.
  5. グラフnetworkからAを取り除く
  6. グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。
となっています。
このアルゴリズムを図を用いて説明します。

 このグラフを使って説明します。
 初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。

 Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。

次にAを取り除きます。
 次はBから始まります。Aと同じことをやります。


このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。


実装

このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。
しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点でのノードのdをヒープ構造で保存しておけば、ヒープ構造から取り出せば、最小のdを持つノードを簡単に取り出せます。


ダイクストラ法はPython 3で実装しました。
コードはgithubに乗せています。

100個のノードを作り、各ノードに0~30の間からランダムな数を選択しedgeを作ります。



結果は



このgifは各ノードの最短距離の更新を表したものです。



Labels:

コメント

コメントを投稿

このブログの人気の投稿

グラフ理論

Introduction sorry, this page is Japanese only. いよいよ私も三回生になり、グラフ理論の授業が始まりました。ということで、グラフ理論の基本的な定義を書いていこうと思います。 最後に説明する隣接行列については実装を行いましたので、以下の記事もよろしければご覧ください。 隣接行列の実装 グラフのイメージ グラフ理論のグラフとは高校数学で習う二次関数などとは違います。 例えば駅などを創造してください。各駅間に線路が通っていますね。このような、駅、線路の集まりのことをグラフといいます。次の絵で確認してもらえるとイメージしやすいかと思います。 このようなものをグラフといいます。グラフは二点間がどうつながっているかだけを保存し、実際の距離や位置関係は保存しません。 このような向きのない（各駅を行き来でき、一方通行ではない）グラフを無向グラフをいいます。反対に向きのある（一方通行しかできない）グラフを有向グラフといいます。 グラフの定義 グラフではある空でない集合E,Vを考えます。Eの要素をedge(辺）、Vの要素をvertex(頂点)といいます。 ここで以下のような写像を考えます。 $$g:E \rightarrow V \times V$$ この時(E,V,g)で定義される空でない空間のことをグラフといいます。 写像で捉えるグラフ 写像gというのは、Eの要素、つまり辺を対応する(始点、終点)というV×Vの集合の要素に送ります。gは写像ですので、写像の定義より、Eのどの要素の始点と終点が対応していることになります。つまり、辺がどこにもつながっていないということはあり得ません。反対にすべてのV×Vの要素がEの要素のどれかに対応しているのであればgは全射になります。 隣接行列 隣接行列とはどのvertexと、どのvertexがつながっているかを行列で表します。例を見るのが理解するのには早いと思うので、例を挙げて説明します。 上のグラフのイメージで出てきたグラフの例を考えましょう。隣接行列は以下のようになります。 $$　\[  adj = \left( \begin{array}{cccccc} 0 &
コメントを投稿
続きを読む

Entropy

Introduction sorry, this page is Japanese only.   今日はエントロピーについて書こうと思います。これは確率論や統計学で死ぬほど大事なKLダイバージェンスといものを理解するために必要な知識です。 この記事ではエントロピーについてしか書きませんが、今度KLダイバージェンスについても書こうと思います。 KLダイバージェンスの記事はこちら Entropy 直観的な話 ある事象、「例えば明日大学の講義にX分遅刻する」という事象を考えます。 この事象に対する確率がP(X)が与えられているとしましょう。P(1)は一分遅刻する確率です。この時確率分布P(X）が持つ情報量はどれだけのものかとうことを考えたいとします。 明日の講義はテストを受けるとします。そのテストを受けないと単位を落としてしまします。しかし、テスト前日はすごく寝不足としましょう。遅刻する確率が99パーセントとわかった時、ほとんどどうあがいても遅刻するのであれば単位を落とすのはほぼ確実といえます。 よって前日に徹夜で勉強するよりも、睡眠不足を解消するために寝る方がよっぽど効率的であることがわかります。しかし、遅刻をする確率が50パーセントとわかった時、前日にテスト勉強をすればよいのか、せずに睡眠をとればよいのかわかりません。このように、確率が偏っているほど何が起こるか予測しやすく、対策を立てやすいのです。遅刻する確率が99パーセントとわかる時は遅刻する確率が50パーセントとわかった時に比べて圧倒的に多いはずです。 確率P(X)に対してこの情報量のことをP(X)の 自己エントロピー といいます。 そして、自己エントロピーの期待値のことを 平均エントロピー といいます。 立式 性質 ではこの情報量を数式で表していきましょう。まず自己エントロピーには大事な性質が二つあります。それが 互いに独立な確率変数の自己エントロピーはそれぞれの情報量の和で表される。 自己エントロピーは減少関数である。 の二つです。 自己エントロピーの加法性 互いに独立な確率変数の情報慮はそれぞれの情報量の和でなければいけません。例えば「明日の講義がY分早く終わる」という事象を考えます。この確率変数Yはあなたが何分講義に遅刻しようが
コメントを投稿
続きを読む

二次元空間の直線

Introduction English ver 今日は、次の定理を証明します。 二次元空間の直線は次のように表せる \[\{x|<x,v> = 0\}\] ただし、vは直線に直行し、ゼロでないベクトルとします。 証明 \[\forall k \in \{x|<x,v> = 0\},\] \[<k,v> = 0\] k と vは二次元空間のベクトルなので、それぞれのベクトルは次のように表せます。 \[k = (k_1,k_2)\] \[v = (v_1,v_2)\] よって \(<k,v>=k_1v_1 + k_2v_2=0\) 方程式を\(k_2\)について解くと \[k_2 = -\frac{v_1}{v_2} k_1\] これはまさしく、傾き\(-\frac{v_1}{v_2}\)の直線です。 Q.E.D
コメントを投稿
続きを読む