ナップサック問題（メモ化）

前回と同じナップサック問題を より効率的に解く方法 を考えます。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

メモ化

前回は、再帰関数 を使ってナップサック問題を解きましたが、再帰関数が 同じ引数で何度もコールされる ことがありました。

このままでは非効率なので、メモ化 という方法で効率的に処理を行ってみます。

メモ化 では、最初の計算時の結果を記憶しておくことで、同じ引数での二度目以降の計算を省略 します。

ソースコード

メモ化 のために、9行目、13～14行目、23行目を追加しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# メモ化用変数
memo = {}

# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
def rec(i, j):
    if (i, j) in memo:      # メモに結果があったら
        return memo[i, j]   # その結果を返す

    if i == len(items):     # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    memo[i, j] = res        # 結果をメモ化
    return res

print(rec(0, capacity))

[実行結果]

7

解（価値の総和の最大値）は前回同様 7 となりました。

今回の入力例では、同じ引数で再帰関数がコールされる回数 が少ないので大幅な効率化はしていませんが、この改良により 解ける問題のサイズを大幅に増やす ことができたことになります。

functools

functools というPythonの標準モジュールを使うと デコレータ を設定するだけで 簡単にメモ化 することができます。（8行目、11行目）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
import functools

# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
@functools.lru_cache(maxsize=None)
def rec(i, j):
    if i == len(items):  # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    return res

print(rec(0, capacity))

[実行結果]

7

ナップサック問題（再帰関数）

ナップサック問題

次のような問題を考えます。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックに入れる品物の 重さの総和 は capacity を超えてはいけません。

選んだ品物の 価値の総和 として考えられる最大値を求めて下さい。

解法・ソースコード

それぞれの品物を入れるか入れないかで分類しながら、再帰関数を使って探索を行ってみます。

再帰関数の第１引数には 品物のインデックス を渡し、第２引数には あとどのくらいの許容量があるか（どのくらいの重さを許容できるか） を渡し、返す値は 価値 となります。

再帰関数内の条件分としては次の３つになります。

  • 品物がない場合
    価値が増えないので 0 を返す。
  • 許容の重さを超える場合
    今回の品物は選択せずに、次の品物のチェックのため品物のインデックスを増やし関数をコールします。（再帰呼び出し）
    その関数の結果を返値（価値）とします。
  • 許容の重さを超えない場合
    今回の品物を 入れない場合 と 入れる場合 の両方で、次の品物のチェックのため品物のインデックスを増やし関数をコールします。（再帰呼び出し）
    ２つのパターンで価値の大きいほうを返値（価値）とします。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
def rec(i, j):
    if i == len(items):  # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    return res

print(rec(0, capacity))

[実行結果]

7

解（価値の総和の最大値）は 7 となりました。

１番目、２番目、４番目の品物を選んだ場合、価値の総和が7、重さの総和が5 となり 重さの許容範囲内で価値が最大 となっていることを確認できます。

再帰関数

再帰関数

次のような問題を考えます。

[問題]

整数 k に対して、レベル k の AB文字列 を次のように定義します。

・レベル 0 の AB 文字列は "B" です。

・レベル k の AB 文字列は "A" + (レベル k - 1 の AB 文字列) + "B" + (レベル k - 1 の AB 文字列) + "A" です。

　例 : レベル 2 の ABC 文字列は "A" + "ABBBA" + "B" + "ABBBA" + "A" = "AABBBABABBBAA" となります。

レベル k の AB 文字列の x 文字目 までに "B" が何個あるかを求めてください。

[条件]

・レベル k は、1以上 50以下の整数

・x（何文字目） は、1以上 レベル kのAB文字列の長さ以下の整数

解法・ソースコード

まず レベル k のAB文字列の長さは ２の k 乗 以上になり k ≦ 50 という条件を考慮すると、単純に文字列を生成する方法では処理が終わりません。

そこで 再帰関数 を使った解法を考えてみます。

問題をよく読むと、レベル k の AB文字列は レベル k - 1 の AB文字列によって定義されていることがわかります。

つまり、AB文字列は １つ前のAB文字列 によって再帰的に定義されています。

レベル k の AB文字列の長さを len_s[k]、レベル k の AB文字列に含まれる文字列”B”の個数を cnt_b[k]とします。

このとき、レベル k の AB文字列を表す文字列の先頭から x文字目 に含まれる 文字列”B”の数 は次のように考えることができます。

  • x=1のとき
    0個
  • x=2 ～ len_s[k-1]+1のとき
    ひとつ前の文字列レベルの先頭から、x-1文字列の中に含まれる文字列”B”の個数
  • x=len_s[k-1]+2のとき
    ひとつ前の文字列レベルの文字列”B”の個数+1
  • x=len_s[k-1]+3 ～ 2 * len_s[k-1]+2のとき
    ひとつ前の文字列レベルの先頭から、x-len_s[k-1]-2文字の中に含まれる文字列”B”の個数 + cnt_b[k-1] + 1個
  • x=2*len_s[k-1]+3のとき
    cnt_b[k-1] * 2 + 1個

以上により、レベル k の AB文字列 を レベル k-1 の AB文字列 に関する問題へと帰着することができました。

また、レベル k の AB文字列の長さ(len_s) と 文字列”B”の個数(cnt_b) は以下のように定義できます。

  • レベル k の AB文字列の長さ
    len_s[k] = len_s[k-1] * 2 + 3 　　(len_s[0] = 1)
  • 文字列”B”の個数
    cnt_b[k] = cnt_b[k-1] * 2 + 1 　　(cnt_b[0] = 1)

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#---------- 入力例 1 ---------
k = 2   # 文字列レベル k 
x = 7   # 何文字目までの "B" をカウントするか
#---------- 入力例 2 ---------

# 再帰関数
def rec(k, x, len_s, cnt_b):
    if k == 0:      # 終了条件
        return 1
    # xに応じて処理分け
    if x == 1:
        return 0
    elif x <= len_s[k - 1] + 1:
        return rec(k - 1, x - 1, len_s, cnt_b)
    elif x == len_s[k - 1] + 2:
        return cnt_b[k - 1] + 1
    elif x <= len_s[k - 1] * 2 + 2:
        return rec(k - 1, x - len_s[k - 1] - 2, len_s, cnt_b) + cnt_b[k - 1] + 1
    else:
        return cnt_b[k - 1] * 2 + 1

len_s = [1] * (k + 1)   # レベルごとの文字列の長さ
cnt_b = [1] * (k + 1)   # レベルごとの文字列"B"の数
for i in range(1, k + 1):
    len_s[i] = len_s[i - 1] * 2 + 3   # ひとつ前のレベル文字列を２倍し３を足したものが文字列数
    cnt_b[i] = cnt_b[i - 1] * 2 + 1   # ひとつ前のレベル文字列を２倍し１を足したものが文字列"B"の数

# 再帰的に求める
print(rec(k, x, len_s, cnt_b))

[実行結果]

4

文字列レベル2の文字列は “AABBBABABBBAA” であり、この文字列の先頭から7文字の中に 文字列”B” が 4個 含まれます。

パリティ②

パリティ

操作に関する問題は、決まったパターンを持たず 柔軟な思考 を必要とするものが多くあります。

しかしながら、次のように問題を解くための指針となる考え方があります。

  • 操作をわかりやすく言い換える。
  • 操作によって作れるものを特徴付ける。

[問題]

Ｎ個の整数が一列に並んでいます。

この整数列に対して次の操作を好きなだけ行うことができます。

「隣り合う２つの整数を選んで、両方の整数に－1を掛ける」

操作終了後のＮ個の整数の 総和 として考えられる最大値を求めて下さい。

解法・ソースコード

今回の操作を分類すると、次のいずれかになります。

  • 数列の「プラス」「プラス」が連続している箇所を「マイナス」「マイナス」にする。
  • 数列の「プラス」「マイナス」が連続している箇所を「マイナス」「プラス」にする。
  • 数列の「マイナス」「プラス」が連続している箇所を「プラス」「マイナス」にする。
  • 数列の「マイナス」「マイナス」が連続している箇所を「プラス」「プラス」にする。

上記により「マイナス」の個数は「２つ増える」か「変わらない」か「２つ減る」 かのいずれかであることが分かります。

つまり「マイナス」の個数の パリティ（偶数／奇数） は 操作の前後で不変 です。

実装は次のように行います。

  • 数列の中のマイナスの数値が 偶数個 ある場合
    マイナスの数値を全てなくして（絶対値をとって）、総和を算出する。
  • 数列の中のマイナスの数値が 奇数個 ある場合
    マイナスの数値を全てなくして（絶対値をとって）、総和を算出する。
    その総和から、絶対値が最小 である数値を ２回差し引く。
    （総和にはすでに最小の数値が含まれているため ２回差し引く 必要があります。）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#---------- 入力例 1 ---------
lst = [-10, 5, -4]
#---------- 入力例 2 ---------
# lst = [1, 2, -3, 10, 100]
#-----------------------------
# マイナスの個数
cnt_minus = sum(x < 0 for x in lst)

# Ｎ個の整数の絶対値の総和
total = sum(map(abs, lst))
# Ｎ個の整数の絶対値の最小値
abs_minus = min(map(abs, lst))

# マイナスの個数が[偶数の場合]は、[絶対値の総和]を出力。
# マイナスの個数が[奇数の場合]は、[絶対値の総和] － [絶対値の最小値×２]を出力。
print(total if abs_minus % 2 == 0 else total - abs_minus * 2)

[実行結果 (入力例 1)]

19

マイナスの数値の個数が 偶数 なので、すべての整数の 絶対値の総和 が解となります。

[実行結果 (入力例 2)]

114

マイナスの数値の個数が 奇数 なので、すべての整数の 絶対値の総和 から 絶対値の最小値×２ を引いた値が解となります。

パリティ①

パリティ

パリティ とは、偶数と奇数に関する性質 のことです。

パリティ に注目すると問題が簡単に解けることがあります。

[問題]

２次元平面上で旅をしようとしています。

時刻 0 に地点 (0, 0) を出発し、時刻 t に地点 (x, y) を訪れる予定です。

時刻 t に地点 (x, y) にいるときには、時刻 t + 1 には

地点 (x + 1, y)、(x - 1, y)、(x, y + 1)、(x, y - 1) のうちいずれかに

移動することができます。

その場にとどまることはできません。

入力は、時刻と地点(t, x, y)が複数与えられます。

入力の旅行プランが実行可能であれば "Yes"、不可能であれば "No" を出力してください。

解法・ソースコード

まず、不可能な場合を考えてみます。

例えば、時刻が１ のときは、１つしか移動できない ので地点(5,6)のような移動はできません。

次に時間は足りているのに移動できない状況は考えられるでしょうか。

例えば、時刻が３ のときには 地点(1, 1) への移動はできません。

これをよく考えてみる、パリティ（奇数か偶数か） によって移動できる地点とできない地点が 交互 になっていることに気づくことができます。

つまり、時刻のパリティ と 移動数のパリティ が同じであれば移動でき、パリティ が異なれば移動できないことになります。

以上を踏まえて、コードを書くと次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#---------- 入力例 1 ---------
plan = [(3, 1, 2),   # 時刻 t、地点 (x, y)
        (6, 1, 1)]   # 時刻 t、地点 (x, y)
#---------- 入力例 2 ---------
#plan = [(3, 1, 2),   # 時刻 t、地点 (x, y)
#        (6, 2, 1)]   # 時刻 t、地点 (x, y)
#---------- 入力例 3 ---------
#plan = [(3, 1, 2),   # 時刻 t、地点 (x, y)
#        (2, 1, 1)]   # 時刻 t、地点 (x, y)
#-----------------------------
# 前回の時刻と座標
pt, px, py = 0, 0, 0    # 初期状態

for t, x, y in plan:
    # 前回状態との差分
    dt, dx, dy = t - pt, abs(x - px), abs(y - py)
    # 時間が足りない場合は移動不可
    if dt < dx + dy:
        print('No (時間が足りない)')
        break
    # パリティが合わないときは移動不可
    if dt % 2 !=  (dx + dy) % 2:
        print('No (パリティが合わない)')
        break
    # 前回状態を更新
    pt, px, py = t, x, y
else:
    print('Yes (移動可能)')

[実行結果 (入力例 1)]

Yes (移動可能)

入力例 1 では、時間が足りておりパリティもあっている ので移動が可能です。

[実行結果 (入力例 2)]

No (パリティが合わない)

入力例 2 では、時間は足りていますが パリティ があっていないので移動できません。

[実行結果 (入力例 3)]

No (時間が足りない)

入力例 3 では、時間が足りていない ため移動できません。

ダイクストラ法＋ヒープキュー＋経路表示（最短経路問題）

ダイクストラ法＋ヒープキュー＋経路表示

前回記事では、ダイクストラ法 と ヒープキュー を使って最短経路問題の効率を上げて解きました。

今回は、さらに 最短経路 を表示します。

グラフは前回同様のものを使います。

[グラフ]

ソースコード

経路を表示するのはとても簡単です。

前回記事では ヒープキュー に コスト と 頂点名 を設定していましたが、さらに 経路 を設定するだけです。

heappush関数 の引数が３つになっています。（22行目、40行目）

（入力データの形式は前回記事と同様です）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#---------- 入力例 ----------
nodes = {                                   # ノード情報
    'Start':{'edge':{'B':4, 'C':3},         # 隣の頂点までのコスト（頂点名:コスト）
             'cost':0},                     # 頂点Startまでの最小コスト
    'B':    {'edge':{'C':1, 'D':1, 'E':5},  # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Bまでの最小コスト
    'C':    {'edge':{'F':2},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Cまでの最小コスト
    'D':    {'edge':{'E':3},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Dまでの最小コスト
    'E':    {'edge':{'Goal':2},             # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Eまでの最小コスト
    'F':    {'edge':{'E':1, 'Goal':4},      # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Fまでの最小コスト
    'Goal': {'edge':{},                     # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')}           # 頂点Goalまでの最小コスト
}
#----------------------------
import heapq

q = []
heapq.heappush(q, (0, 'Start', 'Start')) # スタート位置である頂点の(コスト,頂点名、経路)をヒープキューに追加

# ダイクストラ法（最もコストの小さい頂点を順番に確認していく方法）
while len(q):       # キューがある限り実行
    # 最もコストが小さい頂点名をヒープキューから取得
    d = heapq.heappop(q) # コスト,頂点名,経路が返ってくる
    min_node_name = d[1] # 頂点名
    path = d[2]          # 経路
    if min_node_name == 'Goal':         # ゴール位置の頂点だった場合
        print('解：最小コストは', nodes['Goal']['cost'])    # 最小コストを表示して終了
        print('経路：', path)
        break
    # 最もコストが小さい頂点からの辺を繰り返しチェックする
    for dst, cost in nodes[min_node_name]['edge'].items():
        # 次の頂点までのコストが更新対象であれば更新
        if nodes[dst]['cost'] > nodes[min_node_name]['cost'] + cost:
            nodes[dst]['cost'] = nodes[min_node_name]['cost'] + cost
            # コストを更新した頂点の(コスト,頂点名,経路)をヒープキューに追加
            heapq.heappush(q, (nodes[dst]['cost'], dst, path + ' → ' + dst))

[実行結果]

解：最小コストは 8

経路： Start -> C -> F -> E -> Goal

最小コストの場合の、経路を表示 することができました。

ダイクストラ法＋ヒープキュー（最短経路問題）

ダイクストラ法＋ヒープキュー

前回記事では、ダイクストラ法 を使って最短経路問題を解きました。

今回は、ヒープキュー を使って処理をより効率的にしていきます。

グラフは前回同様のものを使います。

[グラフ]

ソースコード

ヒープキュー は、格納されているデータの中から 一番小さなもの を効率よく取り出せるキューです。

ダイクストラ法 の処理の中で、一番小さなコストの頂点を探すときに ヒープキュー（heapq） を使います。

（入力データの形式は前回記事と同様です）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#---------- 入力例 ----------
nodes = {                                   # ノード情報
    'Start':{'edge':{'B':4, 'C':3},         # 隣の頂点までのコスト（頂点名:コスト）
             'cost':0},                     # 頂点Startまでの最小コスト
    'B':    {'edge':{'C':1, 'D':1, 'E':5},  # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Bまでの最小コスト
    'C':    {'edge':{'F':2},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Cまでの最小コスト
    'D':    {'edge':{'E':3},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Dまでの最小コスト
    'E':    {'edge':{'Goal':2},             # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Eまでの最小コスト
    'F':    {'edge':{'E':1, 'Goal':4},      # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Fまでの最小コスト
    'Goal': {'edge':{},                     # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')}           # 頂点Goalまでの最小コスト
}
#----------------------------
import heapq

q = []
heapq.heappush(q, (0, 'Start')) # スタート位置である頂点の(コスト,頂点名)をヒープキューに追加

# ダイクストラ法（最もコストの小さい頂点を順番に確認していく方法）
while len(q):       # キューがある限り実行
    # 最もコストが小さい頂点名をヒープキューから取得
    min_node_name = heapq.heappop(q)[1] # コストと頂点名が返ってくるので、頂点名だけ取得
    if min_node_name == 'Goal':         # ゴール位置の頂点だった場合
        print('解：最小コストは', nodes['Goal']['cost'])    # 最小コストを表示して終了
        break
    # 最もコストが小さい頂点からの辺を繰り返しチェックする
    for dst, cost in nodes[min_node_name]['edge'].items():
        # 次の頂点までのコストが更新対象であれば更新
        if nodes[dst]['cost'] > nodes[min_node_name]['cost'] + cost:
            nodes[dst]['cost'] = nodes[min_node_name]['cost'] + cost
            # コストを更新した頂点の(コスト,頂点名)をヒープキューに追加
            heapq.heappush(q, (nodes[dst]['cost'], dst))

[実行結果]

解：最小コストは 8

前回同様 頂点Start から 頂点Goal までの最小コストは 8 であることを導き出すことができました。

ヒープキュー を使うことにより、ソースコードがすっきりした感じがします。

また、最小コストの頂点取得の 検索効率があがった ので処理も高速化しているはずです。
（今回のグラフはシンプルすぎて効果を実感できないかもしれませんが・・・）

ダイクストラ法（最短経路問題）

ダイクストラ法

ダイクストラ法 は、最短経路問題 を解くアルゴリズムの１つです。

ダイクストラ法 には次のような特徴があります。

  • コストが最小になる頂点 を探しながら最短経路を求める。
  • マイナスの値 の場合は使えないが、ベルマンフォード法よりも高速に解を求めることができる。

次のようなグラフを考えてみます。

[グラフ]

ソースコード

ソースコードでは、グラフの情報を次の入力例のように定義してみます。

  • 頂点は名前（頂点名）をもち、それぞれの頂点は隣の頂点情報(edge)と自分のコスト(cost)情報を持っています。
  • 隣の頂点情報は、頂点名（辞書型データのキー）とそこに移動するためのコスト（辞書型データのバリュー）があり、複数存在することがあります。
  • 頂点自体がもっているコストは、そこに辿りつくためのコストであり、初期値としてはスタート地点が０、それ以外は無限大を設定しておきます。

ダイクストラ法 では、コストが最もコストが小さくなる頂点 を選択することを繰り返して探索する方法です。

一度チェックしたした頂点は チェック済み として、チェックしていない頂点 の中からコストが最も小さいものを順番に確認していきます。

最も小さいコストの頂点が複数ある場合は、そのうちどれか１つを選択してチェックしていきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#---------- 入力例 ----------
nodes = {                                   # ノード情報
    'Start':{'edge':{'B':4, 'C':3},         # 隣の頂点までのコスト（頂点名:コスト）
             'cost':0},                     # 頂点Startまでの最小コスト
    'B':    {'edge':{'C':1, 'D':1, 'E':5},  # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Bまでの最小コスト
    'C':    {'edge':{'F':2},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Cまでの最小コスト
    'D':    {'edge':{'E':3},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Dまでの最小コスト
    'E':    {'edge':{'Goal':2},             # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Eまでの最小コスト
    'F':    {'edge':{'E':1, 'Goal':4},      # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Fまでの最小コスト
    'Goal': {'edge':{},                     # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')}           # 頂点Goalまでの最小コスト
}
#----------------------------
# ダイクストラ法（最もコストの小さい頂点を順番に確認していく方法）
while len(nodes):       # 未チェックの頂点がある限り実行
    # 最もコストが小さい頂点を探す
    min_cost = min([node_info['cost'] for src, node_info in nodes.items()])
    for name, node_info in nodes.items():
        if node_info['cost'] == min_cost:
            min_node_name = name    # 最もコストが小さい頂点名を取得
            break

    # 最もコストが小さい頂点からの辺を繰り返しチェックする
    for dst, cost in node_info['edge'].items():
        # 次の頂点が未チェック かつ 次の頂点までのコストが更新対象であれば更新
        if dst in nodes and nodes[dst]['cost'] > nodes[min_node_name]['cost'] + cost:
            nodes[dst]['cost'] = nodes[min_node_name]['cost'] + cost

    if min_node_name == 'Goal': # チェックした頂点が'Goal'の場合
        print('解：最小コストは', nodes['Goal']['cost'])    # 最小コストを表示して終了
        break

    del nodes[min_node_name]    # チェックが終わった頂点は削除(チェック済みとする)

[実行結果]

解：最小コストは 8

頂点Start から 頂点Goal までの最小コストは 8 であることを導き出すことができました。

ベルマンフォード法（最短経路問題）

ベルマンフォード法

ベルマンフォード法 は、最短経路問題 を解くアルゴリズムの１つです。

ベルマンフォード法 には次のような特徴があります。

  • 頂点を結んだ 辺の重み（コスト）を更新しながら最短経路を求めます。
  • 辺の重み（コスト）が マイナス の場合でも解くことができます。

次のようなグラフを考えてみます。

[グラフ]

各頂点におけるスタート地点からのコストを求めるにあたり、設定した初期値から辺の重みを使って順に更新する作業を繰り返し、それ以上更新できなくなったら処理を終了します。

ソースコード

ソースコードでは、グラフの情報を次の入力例のように定義してみます。

  • 頂点は名前（頂点名）をもち、それぞれの頂点は隣の頂点情報(edge)と自分のコスト(cost)情報を持っています。
  • 隣の頂点情報は、頂点名（辞書型データのキー）とそこに移動するためのコスト（辞書型データのバリュー）があり、複数存在することがあります。
  • 頂点自体がもっているコストは、そこに辿りつくためのコストであり、初期値としてはスタート地点が０、それ以外は無限大を設定しておきます。

ベルマンフォード法 では、次のような手順で頂点のコスト情報を更新していきます。

  1. 辺を１つ選ぶ。
  2. 選んだ辺のコストを使って、両端の頂点のコストを更新する。
    （コストが小さい頂点に辺のコストを加算した値が、もう一方の頂点のコストよりも小さい場合、更新する）
  3. 全ての頂点に対して、コストが更新されなくなるまで上記の1～2を繰り返す。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#---------- 入力例 ----------
nodes = {                                   # ノード情報
    'Start':{'edge':{'B':4, 'C':3},         # 隣の頂点までのコスト（頂点名:コスト）
             'cost':0},                     # 頂点Startまでの最小コスト
    'B':    {'edge':{'C':1, 'D':1, 'E':5},  # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Bまでの最小コスト
    'C':    {'edge':{'F':2},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Cまでの最小コスト
    'D':    {'edge':{'E':3},                # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Dまでの最小コスト
    'E':    {'edge':{'Goal':2},             # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Eまでの最小コスト
    'F':    {'edge':{'E':1, 'Goal':4},      # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')},          # 頂点Fまでの最小コスト
    'Goal': {'edge':{},                     # 隣の頂点までのコスト（頂点名:コスト）
             'cost':float('inf')}           # 頂点Goalまでの最小コスト
}
#----------------------------
# ベルマンフォード法（辺の重みに注目する方法）
is_updated = True                           # 更新フラグを立てる
while is_updated:                           # 頂点が更新されなくなるまで実行
    is_updated = False                      # 更新フラグを落とす
    for src, node_info in nodes.items():    # 頂点をすべてチェック
        for dst, cost in node_info['edge'].items():             # その頂点からの辺をすべてチェック
            if nodes[src]['cost'] + cost < nodes[dst]['cost']:  # 頂点のコスト＋辺のコストが、次の頂点のコストより小さい場合
                nodes[dst]['cost'] = nodes[src]['cost'] + cost  # 次の頂点のコストを更新
                is_updated = True                               # 更新フラグをたてる
print('解：最小コストは', nodes['Goal']['cost'])

[実行結果]

解：最小コストは 8

頂点Start から 頂点Goal までの最小コストは 8 であることを導き出すことができました。

ベルマンフォード法の注意点

辺のコスト というのは 時間 や 料金、距離 などが対応すると考えられます。

これらはいずれもプラスの値ですが、もしマイナスの値であってもベルマンフォード法は有効です。

ただし、マイナスの値でループ しているような 経路（閉路） がある場合は、そのループを回り続けるといくらでもコストが小さくなってしまうため ベルマンフォード法 では解くことができません。

グラフ（辞書型編）

グラフ（辞書型編）

グラフ は、対象物の関係性 を表します。

グラフ を使うと、友人関係・鉄道路線・タスクの依存関係など、さまざまな関係性を表現できます。

関係性を グラフ で表すと、問題を抽象的に考えることができるというメリットがあります。

問題

次のような問題があります。

[問題]

頂点数がＮ個、辺数がＭ本であるような無向グラフ（辺の向きがないグラフ）があります。

頂点は隣接する頂点の情報（複数）を持っています。

それぞれの頂点は色の情報をもっており、色の情報は塗り替えることができます。

クエリ―は２種類あり下記のような操作を行います。

　クエリ―１：1 aという形式で情報が与えられ、頂点aに隣接する頂点 の色が 頂点aの色 に塗り変えられます。
　
　クエリ―２：2 a bという形式で情報が与えられ、頂点a の色が 色b に塗り替えられます。

[条件]

・頂点数Ｎは1以上200以下の整数

・変数ＭはＮ（Ｎ－１）／２以下の整数

・クエリ―数Ｑは1以上200以下の整数

解法・ソースコード

頂点と辺、色の情報を辞書型の変数で管理します。

辞書型のキーには 頂点のID を設定し、辞書型の値として 色情報と隣接する頂点 の情報を辞書型データとして設定します。

クエリ―ごとに各頂点の色情報を更新し、最後に各頂点の色情報を表示しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#---------- 入力例 ----------
# ノード情報
nodes = {
    1:{'color':5,       # 色情報（初期）
       'edge':[2]},     # 隣接ノード（１→２）
    2:{'color':10,      # 色情報（初期）
       'edge':[1,3]},   # 隣接ノード（２→１、２→３）
    3:{'color':15,      # 色情報（初期）
       'edge':[2]},     # 隣接ノード（３→２）
}
# クエリ―情報
querys = [(1, 2),
          (2, 1, 20),
          (1, 1)]
#----------------------------
# 各ノードの色情報を表示する
def show_color():
    for k,v in nodes.items():
        print('  node[{}]: color[{}]'.format(k, v['color']))

print('【初期のカラー情報】')
show_color()
print(' -------')

for query in querys:
    print('クエリ―', query)
    node = nodes[query[1]]          # ノードを選択
    if query[0] == 1:               # クエリ―がタイプ１の場合
        for e in node['edge']:      # 選択ノードに隣接する各ノードの色を更新
            nodes[e]['color'] = node['color']
    else:                           # クエリ―がタイプ２の場合
        node['color'] = query[2]    # 選択ノードの色を更新
    print(' (カラー情報)')
    show_color()
    print(' -------')

print('【解：カラー情報】')
show_color()

[実行結果]

【初期のカラー情報】
  node[1]: color[5]
  node[2]: color[10]
  node[3]: color[15]

クエリ― (1, 2)
(カラー情報)
node[1]: color[10]
node[2]: color[10]
node[3]: color[10]

クエリ― (2, 1, 20)
(カラー情報)
node[1]: color[20]
node[2]: color[10]
node[3]: color[10]

クエリ― (1, 1)
(カラー情報)
node[1]: color[20]
node[2]: color[20]
node[3]: color[10]

【解：カラー情報】
node[1]: color[20]
node[2]: color[20]
node[3]: color[10]

１番目のクエリ―により、頂点２に隣接する全ての頂点の色が10に塗り替えられます。

２番目のクエリ―により、頂点１の色が色20に塗り替えられます。

３番目のクエリ―により、頂点１に隣接する全ての色が20に塗り替えられます。

最終的には、頂点１の色が20、頂点２の色が20、頂点３の色が10になっていることが確認できます。