「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。今月(2022年10月)からは多忙につき、日々の投稿数を減らします。

MENU

Pythonで学ぶアルゴリズム(12/18)

 アルゴリズムを学ぶのにPythonの学習も兼ねて

を参照していく。

6. グラフ構造

 ヒトのつながりを表現する手段であるグラフ理論に基づくグラフ構造が利用し得る。

6.5 最短距離を求める

6.5.4 すべての頂点間の最短距離

 すべての頂点間の最短距離が欲しい場合、ダイクストラ法をすべての頂点に適用する方法では計算量が多くなる場合がある。実際、頂点の数をn,\ 辺の数をmとすれば、計算量は\mathcal{O}(n(n+m)\log n)になる。グラフに辺が密にあれば更に\mathcal{O}(n^3\log n)になってしまう。
 \mathrm{Floyd-Warshall}法を用いれば計算量\mathcal{O}(n^3)で計算が可能になる。ただし辺の密度が低ければダイクストラ法の方が速い。\mathrm{Floyd-Warshall}法は動的計画法の一種である。

6.5.5 動的計画法

 頂点uからvへの道と、その途中にある頂点a,bが現在の最短経路だったとする。もし途中のa,bを結ぶより短い道があるならば、そちらがuからvへの最短経路の一部として選ばれるはずである。このように税体が最適化されているときに局所も最適化されていることを最適化の原理という。この性質を利用したアルゴリズムを設計する方法を動的計画法という。


6.5.6 Floyd-Warshall法

 まずn^2個あるすべての頂点ペアについて初期状態を設定する。ある頂点ペアが1つの辺で結ばれているならばそれは2点間の最短距離になる。もし隣接していなければ距離を無限大とする。自分へのループは無いと仮定する。この状態である1つの頂点xを考える。隣接していない頂点ペアu,vxを介してつながっていればそれは最短距離になる。これを帰納的に考え、k-1番目まで来たとする。d^{k-1}(u,v)k-1番目までの頂点だけを考慮に入れているときのu,vの最短距離だとする。k番目の頂点を考慮したとき、d^{k}(u,v)



\begin{aligned}
d^k(u,v)=\min\left\{d^{k-1}(u,v),d^{k-1}(u,k)+d^{k-1}(k,v)\right\}
\end{aligned}


で求めることができる。これはk番目の頂点が考慮すべき対象に加わった時に、そこを通るべきか否かを判定している。新たに加えたk番目の頂点を通った方が近いならば最短距離を更新する。

6.5.7 Floyd-Warshall法のサンプル
########################
### Floyd-Warshall法 ###
########################

import math
import random

# グラフの生成
def generate_graph(n, m):
    """ n個の頂点とm個の辺の持つグラフを作成する """
    graph_data = [[0] * n for i in range(n)]
    edge_set = set()
    
    while len(edge_set) < m:
        i, j = random.sample(range(n), 2)
        if i > j:i, j = j, i
        edge_set.add((i,j))
        graph_data[i][j] = graph_data[j][i] = 1
    return graph_data, edge_set

# テストデータを生成
random.seed(6)
node_num = 16
edge_num = 20
my_graph, edge_set = generate_graph(node_num, edge_num)


def all_pairs_shortest_paths(W):
    # 頂点の数
    n = len(W)
    
    # 結果を格納する行列を準備する
    res = [[0] * n for i in range(n)]
    
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i,n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = math.inf
            res[i][j] = res[j][i] = val
    
    # 動的計画法で前兆転換の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

all_pairs_shortest_paths(my_graph)

プライバシーポリシー お問い合わせ