ベルマンフォード法をやっと理解した。

ベルマン・フォード法についてやっと理解したのでメモします。

今回はコードは書かずに具体例を用いて、その最短経路を求める手順を述べながら説明していこうと思います。

僕の理解力がないのがいけないのか、他のドキュメントは大事なことが抜けていることが多い。抜け目なく、理解できるように書いたので冗長になっているかと思いますが、ご許しを。それだけ難しいものだってことで笑


ベルマンフォード法

グラフ理論とかで登場する、グラフの2点間の最短経路を求めるアルゴリズムの一つ。ダイクストラ方とよく比較される。

ついでにダイクストラ法について知りたい方はこちら。


上の図で考えます。

手順

  1. 出発点をa,目的地をfとします。さらに全ての点までの距離を到達可能不明という意味で「∞」と仮定します。
  2. aから一回の移動(一辺の移動)でいけるところ(bとc)へ移動します。
  3. とりあえずbとcの重み(距離)を更新します。(b=5, c=4)
  4. bとcから1辺(1回の移動)でいけるところへ進む(b→c,d      c→d,e,f)
  5. c,d,e,fの重みを更新

ここがベルマンフォード法で気をつけなければいけないところです。というよりここだけ気をつければベルマンフォード法は攻略したも同然です。

  • 更新の際、b→c,d とc→d,e,fは別のものとして考えます。つまり、b→cと重みを更新し、そのcを用いてd,e,fを更新してはいけない
  • b→c で更新したcをCbとするならば、a→Cで更新したCaとは「別物」であるということが重要。
  • あくまで更新作業をする際(更新計算を行う際)は「同じ手順で進んだもののみである」
  • 手順5の場合、c→e(Ec)、b→c (Cb)、c→f(Fc)、b→d(Db)が更新されることになる

そうすると{e = 5, c=3, f = 8, d = 6}となる。1回目の移動(手順3)で重みがすでに存在する場合、両者を比較し小さい方で更新する。

ここまでの重みの更新情報を図に示します。黄緑が一回目の更新での重み。青が二回目(手順5)で更新した重みです。

 

6. 手順5で更新したc,d,e,fから一辺でいけるところへ移動。

fは最終地点なのでこれ以上移動できません。dとeはfへ移動できます。cは先ほど同様d,e,fへ移動します。

7.手順6で移動した所の更新作業をします。

更新作業をした図は以下です。手順7での重み更新を赤文字と赤矢印で書いています。更新した重みはピンクで囲っています。

8.dとeから一辺でいけるfへ移動します。

9.手順7で更新した重みを用いて更新作業をします。

9でやってみるとわかりますが、すでに存在する7の方が小さくなるので、手順9では重みは更新されず、今回の問題(a→f)での最短距離は『7』で決定します。

決定した最短経路を示します。

このように全ての辺に注目し、重みが更新されなくなるまで繰り返す方法が「ベルマンフォード法」です。

ダイクストラ法より計算量が多いとも言えるような少ないとも言えるような微妙な部分ですが、辺の重みが「負」でも計算できるので汎用性という意味では、こちらの方が良さそうです。

 

今回はコーディングについては一切触れなかったので、次は理解したことをコードに落とし込んでいこうと思います。



スポンサードリンク

記事が役に立ったらシェア!

ダイクストラ法についてまとめる



スポンサードリンク

アルゴリズムクイックリファレンスで2点間の最短ルートを求める「ダイクストラ法」について勉強したのでまとめます。

参考ドキュメントはこちらです。ウルトラ参考になりました。

 

応用的には飛行機の最短経路、電車の最短ルートの検索、カーナビとかの経路探索にも使われているアルゴリズムだろう。日常的におせわになっているアルゴリズムと言っても過言ではない。

ダイクストラ法(単一始点の最短経路アルゴリズム)

今回解く問題は以下の問題です。参考サイトに一つノードを加えました。

開始点(スタート)は1、終了点(ゴール)は6。上の図のような重み(距離)が与えられているときの1→6の最短経路を解きます。

ダイクストラ法の解説

ここでは一般的な説明ではなく、上記の解法の説明をします。いきなり一般論を述べるより具体的な問題から入った方が後のアルゴリズムも理解しやすいかと思います。

  1. スタート地点を1番とする(当然)
  2. 地点1から地点(2と3)に移動できるので、地点2と3の重みを更新します。(まだ地点2と地点3への最短経路は決定していません)
  3. 番号の小さい方(ここでは2)に移動します。(これが初めての移動なので、地点2への最短経路は1→2で決定です)
  4. 地点2から移動できる地点(3,4,6)があるので、重みを更新します。
  5. 3,4,6のうち最小番号の3に移動します。
  6. すでに3には1→3の重み80が存在しますが、今辿ってきた経路1→2→3が70なのでこちらの方が近いということになります。なので3の重みを70で更新します。とりあえずここまでの状態を図に示します。決定項目(最短経路)が青で未決定(現状では決定できない)事項が黄緑です。
  7. 最初の図に戻ります。地点3から移動できるのは4と5なので、重みを更新します。そうすると今回の経路(1→2→3→4)での重みは70+10=80ですが、すでにある経路(1→2→4)の方が重みが小さいのでこちらが最短経路ということになります。なので今回は重みは更新しません。
  8. そして3から移動できる最小番号(地点4)に行きます。
  9. 地点4から移動できるのは5と6です。今回の経路(1→2→3→4)の重みで更新すると、地点5での重みは4→5が30なので95、地点6での重みは4→6が10なので75となります。現時点での仮の経路は以下です。
  10. この時点で最小経路は(1→2→4 →6)となるのが自明なのですが、練習のため最後までやりましょう。地点4からいける最小番号は5なので、地点5に移動。
  11. 地点5はこれが初めての重みなので95で更新する。地点5から移動できる地点は地点6のみ。今回の経路(1→2→4→5)で重みを更新すると5→6が15なので95+15で110となる。すでにある経路(1→2→4→6)の重みが75なので今回は更新されずに最短経路が1→2→4→6で決定する。

このような解き方がダイクストラ法です。別名「貪欲法」と言います。残っている値(この場合は接点の数)が最小のものを選ぶという意味で貪欲です。なおダイクストラ法は重みが非負数の場合のみ使えます。非負数の場合はベルマン-フォード法を用います。これについては別途説明します。

コードを書いてみる

全体をいくつかの部分に分けて説明します。


隣接行列を定義します。隣接行列についてはこちらを参考にしてください。ここでは2重リストを用いて隣接行列の成分を表しています。

接点数をlen()関数で定義しています。未探索の接点をlist(range(node_num))で定義。これで未探索接点の初期条件(0,1,2,3,4,5)を設定します。

[math.inf]は正の無限大を表すので全ての接点の初期距離を∞(到着可能か不明)とする。

移動前の接点を[-1]*node_numで定義します。

接点0までの距離は開始点なので0とする。


次に最小のインデックス番号を取得する部分の関数です。

接点番号の初期値は0なのでstart = 0

indexに未探索ノード(ある地点から移動できる点)がある場合、index (接点)はそのまま。移動できる点がなくなった場合(接点1の場合2も3も計算した場合)、もうないのでelseとなり次の接点番号2へ移る。


ここはダイクストラ法の根本部分です。

while文は未探索接点がなくなるまで繰り返します(len(unserched_nodes) !=0)

最初の接点間の重みは無限大(math.inf)と定義する。ここから、上記で説明した1番にたどり着く(プログラミングは前提条件与えるのにやっとですね笑)

for文は未探索ノードにおけるループです。posible_min_distance=distance[node_index]の部分で最短距離が小さければ更新します。

そして先ほど説明したget_target_min_index関数で接点から次の接点へ移動する際の最小番号を更新する。(移動できる場合は更新せずにそのまま)

そして、この点は探索終了なので未探索接点(unserched_node)から削除する(remove(target_min_index))

経路の重み計算にはその時の接点番号を用いる(ターゲットから伸びる接点)のでtarget_edgeとして定義する。

そしてif文内で過去に更新した重み(距離)よりも小さければ(重みが少なければ)それをdistance[index]として更新する。

最後に一つ前の接点に到達する接点のリストを更新する。


正直ここが全然わかりません。

previous_nodeとprevious_nodesの違いがいまいち。二行目のnode_num-1もなんの意味が。

node_numは接点数のはず。接点数は一定で6-1で5のはず。そしたらelse文とか意味ないじゃんて思ってしまう。

難しい。

実行結果

上で手計算で解いた時と同じ結果になります。しかし自分で0から書いたコードではないので、どこで何が起きているのか不明です。まさにブラックボックスの状態ですね。

以上、一応ダイクストラ法のアルゴリズムについて勉強してみましたがやはりコードに落としこむことができないm(_ _)m

今回はオライリーの「アルゴリズムクイックリファレンス」とgoogle先生を頼りに勉強しました。

正直この本は初心者には嫌われてますが、これを理解するための入門書チラ見しながらとかgoogle先生に聞きながらなら、かろうじて読めるかなと行ったところ。論文読んでるような感じです。時間はかかるけど、しっかり理解しながら読めば気付いた時にはそこらへんの入門書程度なら余裕だなって感じの知識はつきます。

たまには難しめの本から入りたいという変わり者にはおすすめです。



スポンサードリンク

 

 

 

 

記事が役に立ったらシェア!

Rで学ぶグラフ理論(第4回)



スポンサードリンク

前回の続きでグラフ構造の評価方法について述べていきます。

相互性

有向グラフにおいて、頂点間の関係のうち有向辺がお互いに向いているものの割合です。言い換えると両思いの割合です。

以下の図に示すように、頂点には4パターンの関係が考えられます。

そして上の図で言えば、相互性は次のように定義されます。

\begin{eqnarray}
\mathrm{reciprocity} = \frac{a}{a+c+d}
\end{eqnarray}

しかし上記の定義は一部である。上の定義式の分子にbを加えた場合の定義も存在する。

両者の区別は、分析の目的に応じて異なる。企業間の株式のネットワークにおいてはaとbは全く別の状態であるが、集団における贈与のネットワークにおいて、互酬性の規範がどの程度守られているかを知りたいときには、aとbは同等のものとして扱うべきである。

なぜなら、互酬性の規範に反するのは、贈与が一方向に行われている場合(図のcとd)であり、お互いに無関係(b)の場合は、規範に反していない。一応その場合の定義を以下に示す。
\begin{eqnarray}
\mathrm{reciprocity} = \frac{a+b}{a+b+c+d}
\end{eqnarray}

階層的構造

出-木構造の必要十分条件として以下の4つが定義されている。

連結性、階層性、効率性、最小上界性である。これらに違反している程度からある有向グラフが階層的構造を持っているかどうかを評価する。

連結性

辺の方向を無視した時グラフ全体で相互に到達可能な頂点の組みがどれくらいあるかによって連結性を定義できる。辺の方向を無視しても相互に到達不可能な頂点の組の数をVとすると、全ての頂点間の組みの数に対するその比率を1から引くことで求める。

\begin{eqnarray}
\mathrm{connectedness} &=& 1 – \frac{V}{\frac{n(n-1)}{2}}
&=& 1 – \frac{2V}{n(n-1)}
\end{eqnarray}

階層性

上の図のように、上から下へ一方向ではなく、相互に到達可能な関係があるとすれば、それは上下関係とは呼べず、階層性に違反していることになる。

よって、双方向に到達可能な頂点の組みの数V、少なくとも一方から他方へ到達可能な頂点の組数でをMaxVとすると以下の式で表現できる。

\begin{eqnarray}
\mathrm{hierarchy} &=& 1 – \frac{V}{\mathrm{Max}V}
&=& 1 – \frac{2V}{n(n-1)}
\end{eqnarray}

上の図の場合、双方向に到達可能な組みがないので、階層性は0になる。


スポンサードリンク

弱連結

上のグラフでいうと頂点1,2,3,のような関係。

離散数学的な定義

  • • 任意の頂点u, v間が、弧ではつながっている

図で示すと

みたいな感じである。

効率性

出-木構造は上位の頂点から下位の頂点へと必ず一つの経路を通って到達できるという意味で効率的である。しかしそのような経路が複数ある場合それは無駄であるため、そのような効率がどの程度実現しているかを表す指標が効率性である。

今、n個の頂点とm個の有向辺からなる弱連結の有向グラフを考える。もしこの有向グラフが出-木構造なら有向辺の数は、m = n -1 となる。

よって出-木構造でない実際の有向グラフに含まれる冗長な有向辺の数はm-(n-1)となる。

mの理論的な最大値はn(n-1)となるから、冗長な有向辺の数の理論的最大値はn(n-1)-(n-1)である。

これらを用いて、効率性は次のように定義できる。ただしVは冗長な有向辺の数、MaxVは冗長な有向辺の理論的最大値である。

\begin{eqnarray}
\mathrm efficiensy &=& 1 – \frac{V}{\mathrm{Max}V}\\
&=& 1 – \frac{m-(n-1)}{n(n-1)-(n-1)}\\
&=& 1 – \frac{m-(n-1)}{(n-1)^2}
\end{eqnarray}

弱連結でない場合(すいませんがここからよく理解できていません)

文章も砕けた感じになります。

私が参考にしている本では

「この場合は、いくつかの連結成分に分かれている場合がある。この場合、それぞれの連結成分が出- 木構造となっているのがもっとも効率的である。」と書いてあります。

????

まず言葉の定義から

連結成分

以下の図を考えます。

連結成分とは同値関係におけるグラフGの部分グラフである。

{1,2,3},{4},{5,6,7}は連結成分を誘導するという。

でこの連結成分が、上の{1,2,3}のように閉ループを構成するのではなく、

こんな感じになってれば、良いと言っています。

要は、全体で」見たと時に弱連結でなくとも、部分グラフ単体で見た時に、出-木構造になっている時に、もっとも効率が良いということだろう。

弱連結でない時の定義

直感的に十分理解できる。別れている部分グラフのごとに先ほどの定義式を使うだけである。そしてシグマを取れば良い。

有向グラフがN個の連結成分に別れている時、i番目の連結成分に含まれる頂点の数をniとすると、効率性は以下のように定義できる。
\begin{eqnarray}
\mathrm{efficiensy} &=& 1 – \frac{m-\sum^{N}_{i=1}(n_{i}-1)}{\sum^{N}_{i=1}n_{i}(n_{i}-1)-(n_{i}-1)}\\
&=& 1 – \frac{m-\sum_{i=1}^{N}(n_{i}-1)}{\sum_{i=1}^{N}(n_{i}-1)^2}
\end{eqnarray}

実際に計算してみる

階層構造の4つの指標について実際に計算してみることにする。

計算する有向グラフを以下に示す。

計算の簡便化のために以下のような表を作成する。条件に当てはまるものが1、当てはまらないものが0である。

頂点のペア 一方向に到達可能 双方向に到達可能 最小上界をもつ
1-2 0 0 0
1-3 1 0 1
1-4 1 0 1
1-5 0 0 0
2-3 0 0 0
2-4 1 0 1
2-5 1 1 1
3-4 1 0 1
3-5 0 0 0
4-5 1 0 1

連結性

この有向グラフは弱連結であるので、全ての頂点間で到達可能であるため連結性は1である。

階層性

有向辺を辿って少なくとも一方向に到達可能なペアに対する双方向に到達可能なペアの比率を1から引いて求めるられる。一方向に到達可能なペアは6つ、両方向に到達可能なペアは1つなので

\begin{eqnarray}
1-\frac{1}{6} = 0.833333
\end{eqnarray}

効率性

効率性は「階層性のうち冗長な経路の数の多さ」を評価しているので、上の表は関係ない。頂点の数と有向辺の数に依存するので、
\begin{eqnarray}
1-\frac{6-(5-1)}{(5-1)^2} = 0.875
\end{eqnarray}

最小上界性

上の表より最小上界を持たないペアの数は4ペア。最小上界性を求める式を用いて計算すると
\begin{eqnarray}
1-\frac{2 \times 4}{(5-1) \times (5-2)} = 0.33333
\end{eqnarray}

となる。


以上でネットワーク構造の評価法の相互性と階層構造について述べてきた。

次は、前回と前々回にやったColemanの高校生の友人ネットワークのデータを用いて、これまで述べてきた指標について計算し、その結果とそこから導かれる背景について論じていこうと思う。



スポンサードリンク

記事が役に立ったらシェア!

Rで学ぶグラフ理論(第3回)



スポンサードリンク

前回の続きをしていこうと思います。グラフ理論というより厳密にはネットワーク分析ですね笑。まあそういう細かいことはほっておいて笑。

用いるデータは前回と変わりません。

ネットワーク構造の諸批評

前回説明した密度以外にどんなものがあるか述べていきます。

推移性

わかりやすくいうと無向グラフの場合、グラフ全体のうち閉ループになっている割合です。

私が参考にしている本では「自分の友達の友達は自分の友達である割合」と言っています。人的ネットワークでいうと三角関係の割合というところでしょうか。

下のような隣接行列で表されるグラフであれば、3-2-1とか、1-4-5-の関係の割合です。

具体的な計算方法

  1. 隣接行列Aを2乗する。→理由は不明だが、算出された各成分は長さ2の経路の数に等しくなる。
  2. 1で求めた行列A2の成分の和を求める。→長さ2の経路の数
  3. 2で求めたもののうち、両端の頂点に直接関係のあるものは、A2とAの成分積の成分の総和となる

よって推移性は以下の式で定義される。
\begin{eqnarray}
R = \frac{\sum A_{ij}}{\sum A2_{ij}}
\end{eqnarray}

Rでの計算方法

12から14行目はグラフ表示する部分ですので、推移性を求める場合はいらないです。

計算すると

となります。


スポンサードリンク

密度との比較

ここで前回のデータ(高校生の友人関係のネットワークデータ)を用いて、推移性を求めてみようと思います。

gtrans()は推移性を求める関数です。

1957年秋に比べ、1958年春の方が推移性は下がっています。友人関係の密度(繋がり)は増加しても、三角関係というか(共通の知り合い)は増えないみたいです。

友達の紹介を通じて得られる友人よりも、個人個人で新たに繋がりを増やす人の方が多いということでしょうか。

ネットワーク分析で事象の背景が見えてくるのは本当に面白いですね。



スポンサードリンク

 

 

 

記事が役に立ったらシェア!

Rを用いてグラフ理論を学んでみる。



スポンサードリンク

グラフ理論をRを使って勉強してみよう思います。

今回は簡単なグラフを可視化するところから。

その前に環境構築(mac)

Rは簡単にインストールできます。ここではRとRの統合開発環境のRーstudio(swift でいうxcode,androidアプリでいうandroid-studio)のインストール方法について述べて行きます。

homebrewはあらじかじめインストールしておいてください。

次に下記のコマンドを実行し、インストール

かなり時間かかります。辛抱強く待ちましょう。

次にR-studioです

次にインストールコマンド。

インストールが終了するとターミナルに以下が表示されると思います。

以下のコマンドを実行するかlaunchpad等から直接起動しましょう。

以上で準備は終わりです。

グラフ理論の細かいことはほっといて…

とりあえずR-studioで遊びましょう。起動すると以下のような画面になると思います。

左側がコンソールでここにコマンド打ち込んで行きます。スクリプトを作成し、それを読み込ませることもできるみたいですが、それはまた今度で。

R-studioでグラフ理論を学ぼう!(超基本)

グラフを作成するために以下のコマンドを実行しライブラリを読み込みます。

グラフ理論ではグラフをGで定義し、ここでは以下のように定義します。

erdos.renyi.game()の意味は現時点では不明だが、呪文だと思って使うことにします。

()内の数字は、10がグラフ理論における隣接行列の行の数(正方行列)。9/10が一列または一行における成分が「1」の数となる最大値。

これはランダム生成なので、必ずしも列、行内に1が9個出現する訳ではありません。

最後は有向グラフという意味。無向グラフの場合はいりません。

次にxとして隣接行列の作成

そうすると以下のような隣接行列が作成されます。

次にエッジリストです。

隣接行列に比べ、コンパクトになるので、大規模かつ疎なグラフに対して用いられます

以下のコマンドを実行。

実行するとわかりますが、グラフが密であるため、成分が多くなり、かなり行数が多くなります。

今回はスペース省略のため割愛させていただきます。

ついに可視化!

layout.()関数はグラフを描画するためのコマンドで、色々な種類のグラフを作成するために多くの関数が用意されています。

今回は円で表示したいのでcircleにする。

R-studioの右下の欄に以下が表示されれば、おっけーです。

ついでにlayout.circleをlayout.sphereにしてみる。

まだ勉強不足なため、両者の違いが理解できない笑

以上で、R-studioでのグラフ理論の遊びを終わりにします。

隣接行列やエッジリストの説明など今回は省きましたが、R-studioを使って遊びながら書いて行きます。



スポンサードリンク

記事が役に立ったらシェア!