第6回 - 辞書の使い方、最短経路アルゴリズムを使った迷路の解法

2022年1月24日

Python のハッシュテーブル (辞書)
- 演習 6-1. Python辞書の不都合な真実
最短経路探索アルゴリズム
迷路探索への応用
ブレイクアウトルーム練習
- 演習 6-5. Pythonの辞書を使った郵便番号検索
本日の課題
- 小課題6. 最短経路の探索 (1月31日締切)
- 中課題3. 迷路の最短経路を求める (2月7日締切)

学修アンケートへの回答をお願いいたします。

雑談 - Pythonでゲームを作るには

Python には、Pygame という拡張機能を追加することでPC上のゲームを作成することができる。

まず、以下のようにして pygame を自分のPCにインストールする:

C:\Users\euske>pip install pygame
Collecting pygame
  Downloading pygame-2.1.2-cp39-cp39-win_amd64.whl (8.4 MB)
     |████████████████████████████████| 8.4 MB 6.4 MB/s
Installing collected packages: pygame
Successfully installed pygame-2.1.2

実際に使ってみるには、以下のようにする:

C:\Users\euske>python  # まず python を開始する
Python 3.9.9 (...) [MSC v.1929 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import pygame      # pygame モジュールを使用
pygame 2.1.2 (SDL 2.0.18, Python 3.9.9)
Hello from the pygame community. https://www.pygame.org/contribute.html
>>> pygame.init()      # 各種機能を初期化
(5, 0)
>>> disp = pygame.display.set_mode((600,400)) # 画面を600×400のサイズで作成
>>> disp.fill((0,0,255))  # 画面を青色で塗る (実際の画面はまだ変化しない)
<rect(0, 0, 600, 400)>
>>> pygame.display.flip() # 画面を実際に更新
>>> pygame.event.get()  # イベント列を取得

ここで出てくるイベント (event) とは、 Python プログラムへの「入力」である。コマンド・プロンプトから実行するプログラムと違い、 GUI (グラフィカルユーザインターフェイス) プログラムでは、一口に「入力」といっても多様な種類 (キーボードからの入力、マウスからの入力、ウィンドウの操作等) があるため、これらをひとつにまとめて「イベント」と呼んでいる。

以上をふまえて、四角形が動くだけのゲーム(?) をプログラムすると、以下のようになる:

game.py

# pygameを初期化。
import pygame
pygame.init()
# ウィンドウを開く。
window = pygame.display.set_mode((600,400))
# 初期位置を (0,0) に設定。
x = 0
y = 0
# 初期状態を設定。
state = 0
# 有限状態機械。
while True:
    # たまっているイベントをひとつずつ処理する。
    for e in pygame.event.get():
        if e.type == pygame.QUIT:
            # ウィンドウの「閉じる」ボタンが押されたら終了状態に遷移。
            state = 1
        elif e.type == pygame.KEYDOWN:
            # キーが押されたら、押されたキーに応じた各種処理。
            if e.key == pygame.K_LEFT:
                x = x - 1
            elif e.key == pygame.K_RIGHT:
                x = x + 1
            elif e.key == pygame.K_UP:
                y = y - 1
            elif e.key == pygame.K_DOWN:
                y = y + 1
    # ウィンドウを青で塗る。
    window.fill((0,0,255))
    # 自分の位置(x,y) に緑で 10x10 の大きさの四角形を描画。
    window.fill((0,255,0), (x,y,10,10))
    # 画面を更新。
    pygame.display.flip()
    # 終了状態になったら終了。
    if state == 1:
        break

1. Python 内蔵のハッシュテーブル (辞書)

Python には、実はハッシュテーブル (Python の用語では辞書 (dictionary) という) を簡単に使う機能がすでに備わっている。

# d という辞書を新たに作成する。
d = {}
# キー "abc" に対応するバリュー "def" を代入する。
d["abc"] = "def"
# キー "12345" に対応するバリュー "wxyz" を代入する。
d["12345"] = "wxyz"
print(d["abc"])    # def
print(d["12345"])  # wxyz

ここで使われている辞書 (ハッシュテーブル) d は、ひとつのデータ型である。リストなどと同様に、まるごとひとつの変数に入れることができる。ここでも d[ ] の中に入る値をキー (key) と呼び、それに対応する値をバリュー (value) と呼ぶ。

なお、リストと同じく、辞書もメモリ使用量が大きくなる可能性があるので、不動産の法則が成り立っている。 (したがって変数 d に入っているのは、辞書そのものではなく辞書への参照である。)

構文

d = {}            # 空の辞書を変数 d に入れる。
d["abc"] = "def"  # キー "abc" に対応するバリュー "def" を d に格納する。
v = d["abc"]      # キー "abc" に対応するバリューを得る。
d["abc"] = "xyz"  # バリューを書き換える。

キーはいくつでも追加することができ、バリューはあとから書き換えることもできる。

文字のかわりに数値を使う

キーやバリューとして文字列のかわりに数値を使うこともできる。 (一見するとリストのように見えるが、リストではない。)

p = {}
p[123] = 456      # キー 123 に対応するバリュー 456 を p に格納する。
print(p[123])     # キー 123 に対応するバリューを得る。

注意: ただし Python ではリスト型はキーとしては使えない。

辞書の直接定義

リストと同様、辞書の中身を直接プログラムに書くこともできる。

price = { "chocolate": 100, "cookie": 150 }
print(price["chocolate"])

存在しないキー

存在しないキーのバリューを参照しようとすると、エラーが発生する。

price = { "chocolate": 100, "cookie": 150 }
print(price["ramen"])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'ramen'

キーの存在確認

あるキーが辞書中に存在するかどうかを調べるには、文字列・リストと同じ in 演算子を使う。

price = { "chocolate": 100, "cookie": 150 }
if "ramen" in price:
    print("ラーメンいる")
else:
    print("ラーメンいない")

キーの一覧

ある辞書に含まれているキーの一覧を表示するには .keys() メソッドを使う。

price = { "chocolate": 100, "cookie": 150 }
for k in price.keys():
    print(k, price[k])

これは以下のように表示される。

chocolate 100
cookie 150

注意: 辞書のキーが表示される順序はランダムである。あとから代入されたキーが最初に出てくる場合がある。

キーの個数

リストと同じく、ある辞書に含まれているキー・バリュー対の個数を表示するには len() 関数を使う。

price = { "chocolate": 100, "cookie": 150 }
print(len(price))  # 2

キーの削除

辞書からキー・バリュー対を削除するには、リストのときと同じように del 文を使う。

d = { "X": 1, "Y": 2, "Z": 3 }
del d["Y"]
print(d)    # {'X': 1, 'Z': 3}

Pythonでは、リストを辞書のキーとして使うと「ある不都合」が起こるので、意図的にリストは辞書のキーにはできなくしてある。その不都合とは何か考えよ。

k = [1,2,3]
d = {}
d[k] = "abc"  # エラー
k.append(4)

2. 最短経路探索アルゴリズム

最短経路探索 (pathfinding) とは、迷路やら何やらの中から、最短経路を探し出すことである。以下のような用途に利用されている:

カーナビ、地図アプリ
乗り換え案内
ネットワーク経路制御
ゲームにおけるキャラクタの動き

2.1. 最短経路とは?

以下のような「ネットワーク」を考える (数学用語では、これをグラフ graph と呼ぶ)。これは、ノード (Node, 点) とエッジ (Edge, 線) で構成される。

各エッジには「距離」がついている。 A地点から始めて、もっとも少ない距離で Z地点にたどりつくには、どのエッジをたどればよいだろうか? これが最短経路探索である。

上の図で、 A地点から始めて、もっとも少ない距離で Z地点にたどりつく経路を答えよ。

アホな方法:

すべての可能な経路をかたっぱしから列挙する。
もっとも合計距離が短いものを選ぶ。
計算量 O(2ⁿ) 以上 (組み合わせ数の爆発)

2.2. Dijkstra (ダイクストラ) の方法

ある意味、迷路でやった「根っこ伸ばし方式」に似ている:

まず根っこがゴール (Z地点) から伸びると仮定する。最初のノードの総コストを「0」とする。それ以外のすべてのノードの総コストを「∞ (無限大)」とする。
(別にスタートから始めてもよいのだが、ゴールから始めると、あとあと便利)
根の終端は、現在のノードから出ているエッジをひとつずつたどって、隣のノードに伸びようとする。このとき、始点から到達した点までの総距離を新たな総コストとして計算する。
根は、最小のコストで到達できるときにのみそのノードに伸びることができるとする。伸びたときそのノードの総コストは更新される。
すべてのノードに根が伸びるまで 2., 3. をくり返す。

これを Python 風に書くと以下のようになる:

# 各ノードのコストを初期化する。
cost = {各ノードのコスト}
# ゴールから始める。
root = [ゴール]

while 0 < len(root):
    # rootから点をひとつ取り出す。
    p = root[0]
    del root[0]
    c0 = cost[p]
    for q in (pの隣のノード):
        # 隣に伸びたときのコストを計算。
        c1 = c0 + (p,q間の距離)
        # 従来のコストより小さいか?
        if c1 < cost[q]:
            # コストを更新、根を伸ばす。
            cost[q] = c1
            root.append(q)

上のプログラムは、根がすべての点に到達したときに終了する。このときスタート地点におけるコストは、スタートからゴールまでの最短距離になっているはずである。

2.3. Pythonによる実装

では実際に Python を使って実装してみる。簡単のため、グラフは以下のようなものにする。 (ここでは各ノード間のエッジは距離ではなく所要時間を表しているが、やることは同じである)

下準備

まず上のグラフを Python のリスト (のリスト) で表すことを考える。各エッジを [地点1, 地点2, コスト] のように表すと、以下のようになる:

route = [
    ["jiyugaoka",  "denenchofu", 2],
    ["jiyugaoka",  "shibuya",    12],
    ["denenchofu", "oookayama",  4],
    ["jiyugaoka",  "oookayama",  3],
    ["shibuya",    "meguro",     5],
    ["oookayama",  "meguro",     9],
]

さらに、与えられた 2点 a, b間の距離 (コスト) を返す関数 getcost() を定義する。ここでは route中に書かれているのが (a,b) および (b,a) のどちらでもよいように、2通りの検査をしている。

# 2点 a, b間の距離 (コスト) を返す。
def getcost(a, b):
    # すべてのエッジを探索する。
    for p in route:
        # p[0] に地点1, p[1] に地点2, p[2] にコストが入っている。
        if ((a ==      and b ==     ) or
            (a ==      and b ==     )):
            return     
    # 見つからない場合は -1 を返す。
    return -1

print(getcost("oookayama", "jiyugaoka"))  # 3
print(getcost("oookayama", "shibuya"))    # -1

また、あるノード x と接続されている隣のノード名の一覧をリストとして返す関数 neighbors() を定義する。ここでも x がエッジのどちら側であってもよいように、 2通りの検査をしている。

# ノード x の隣のノード名一覧を返す。
def neighbors(x):
    a = []
    # すべてのエッジを探索する。
    for p in route:
        # エッジのどちらかが x であれば、相手のノードを返す。
        if x ==     :
            a.append(    )
        elif x ==     :
            a.append(    )
    return a

print(neighbors("oookayama"))  # ['denenchofu', 'jiyugaoka', 'meguro']
print(neighbors("shibuya"))    # ['jiyugaoka, 'meguro']

次に、各ノードの総コストを無限大に初期化する。とはいっても Python では無限大は扱えないので、ここでは単に大きい数 (9999) を代入しておく。

cost = {}
for p in route:
    cost[p[0]] = 9999
    cost[p[1]] = 9999

実際のアルゴリズム

ここまでくれば、あとはダイクストラの方法をそのまま書くだけである:

# 各ノードから goal に到達する最短距離を求める。
def shortest(goal):
    # 各ノードのコスト初期化。
    cost = {}
    for p in route:
        cost[p[0]] = 9999
        cost[p[1]] = 9999
    cost[goal] = 0
    # ゴールから始める。
    root = [goal]

    while 0 < len(root):
        # rootから点をひとつ取り出す。
        p = root[0]
        del root[0]
        # c0: ノード p における総コスト。
        c0 = cost[p]
        print("node", p, "cost", c0)
        # p の隣のノードをすべて試す。
        for q in neighbors(p):
            # c1: p→q に伸びたときの総コスト。
            c1 = c0 + getcost(p, q)
            print("neighbor", q, "cost", c1)
            # 従来のコストより小さいか?
            if c1 < cost[q]:
                # コストを更新、根を伸ばす。
                cost[q] = c1
                root.append(q)
                print("update", q)
    # 各ノードにおける総コスト一覧を表示する。
    print(cost)
    return

上の関数 getcost() および neighbors() を完成させ、 "shibuya" に到達する最短距離を求めるプログラム shortest.py を書け。
ダイクストラの方法は、ノード間のコストが必ず 0 以上でないとうまくいかない。これを確かめるために、上の例で、たとえば「自由が丘 - 大岡山」のコストを -10 に設定し、プログラムがどう動作するか観察せよ。

2.4. 最短経路を発見する

上のプログラムでは、ゴールから各ノードまでの最短距離は計算できたが、実際の経路はわからなかった。ここで上のプログラムを以下のように変更すると、最短経路を発見できる。

根っこがあるノードに到達してその最小コストを更新するとき、 更新した根がどのノードから来たかを記録しておくようにする

このようにすると、すべての処理が終わったとき、スタートからゴールまで最小のコストとなるノードを順にだとることができるようになっている。

最初の状態。渋谷から開始する。渋谷における総コストは 0 である。(他のノードはすべて ∞)
根を自由が丘と目黒に伸ばし、最小コストを更新したところ。このとき、コストを更新した根がどこから来たかを記録する矢印を書いておく。
根がすべて伸びたところ。各ノードからの矢印は、渋谷へ向かう最短経路を示している。

(最初に根っこをゴールから伸ばしたのはこの理由である。スタートからゴールに向かって根を伸ばすようにすると、あとで順序を入れ変えねばならない。)

最短経路を求めるアルゴリズム

# 各ノードから goal に到達する最短経路を求める。
def shortest(goal):
    ...
    # ゴールから始める。
    root = [goal]
    # 各ノードにおける、更新元のノード名。
    origin = {}

    while 0 < len(root):
        # rootから点をひとつ取り出す。
        p = root[0]
        del root[0]
        # c0: ノード p における総コスト。
        c0 = cost[p]
        print("node", p, "cost", c0)
        # p の隣のノードをすべて試す。
        for q in neighbors(p):
            # c1: p→q に伸びたときの総コスト。
            c1 = c0 + getcost(p, q)
            print("neighbor", q, "cost", c1)
            # 従来のコストより小さいか?
            if c1 < cost[q]:
                # コストを更新、根を伸ばす。
                cost[q] = c1
                root.append(q)
                print("update", q)
                # 更新した根がどのノードから来たかを覚えておく。
                origin[q] = p
    # 各ノードにおける総コスト一覧を表示する。
    print(cost)
    # 各ノードからゴールへ向かう最短ノードを表示する。
    print(origin)

上のプログラムの変数 origin を使って、実際に oookayama から shibuya まで各ノードをたどって最短経路を表示する処理を追加せよ。
```
oookayama
meguro
shibuya
```
ヒント: while文を使って現在地が goal になるまで繰り返す。
変数 route の内容を変更し、もし oookayama - meguro のコストが 15 だったとすると、別の経路が選ばれることを確認せよ。

最短経路探索アルゴリズムはさまざまな用途に応用できる。「コスト」の概念を時間や金額などにすることで、最短時間経路や最低運賃経路なども計算できる。

3. 迷路探索への応用

中課題2. で生成したような迷路に対して最短経路探索を適用すると、スタートからゴールへ向かう最短経路を求めることができる。

#########
#S#     #
# # # # #
#   # # #
##### # #
#       #
# # #####
# #    G#
#########

まず、通路の各マスをすべて個別のノードとみなす。ここでは辞書で使うキーとして、名前のかわりに、"1,1" のように X,Y座標をカンマでつなげた文字列を使うことにする。
各マス間の距離は同じなので、 エッジのコストはすべて 1 とみなせる。つまり getcost() 関数は必要なくなる。 neighbors() 関数は書き直す必要があるが、これは与えられた座標から上下左右にある進めるマスの座標 (最大4個) を返せばよい。
```
def neighbors(p):
    x = p[0]
    y = p[1]
    a = []
    # (x,y) の上下左右のマスのうち、進めるものを返す。
    ...
    return a
```
右下の座標をゴールとして設定し、最短経路探索を実行する。たとえば 9×9 の迷路なら [7,7] の位置から始める。
```
goal = [7,7]
cost["7,7"] = 0
root = [goal]
```
処理が終わったら、スタート [1,1] から始めてゴールまでの各ノードをたどり、通った各マスに 2 を代入していく。

最後に 2 のあるマスを「.」で表示する。

#########
#.#...  #
#.#.#.# #
#...#.# #
#####.# #
#  ...  #
# #.#####
# #.....#
#########

なお中課題2. で生成した迷路はループが存在しなかったが、ダイクストラの方法はループが存在する迷路に対しても正しく動作する。

4. ブレイクアウトルーム演習

ブレイクアウトルーム演習の方法:

ブレイクアウトルーム中はカメラを使うこと。
まず自己紹介をする。名前・所属・趣味などを簡単に説明する。
最初の問題をやる担当者が PC の画面共有をおこない、課題のプログラムを考えながら書く。このとき周囲の人は手助けする。
終わったら、今日の演習でできなかったところを教えあう。
全部終わったら、適当に雑談する (← これが本当の目的)。

第5回の授業で出てきた郵便番号から住所を検索するプログラムを Pythonの辞書を使って書け。

postcode.py

import csv
with open("KEN_ALL_ROME.CSV", encoding="utf-8") as fp:
    table = list(csv.reader(fp))
# 郵便番号 → 住所に対応させるハッシュテーブル(辞書)を作成。
postcode = {}
for row in table:
    # row[0] に郵便番号、row[1]+row[2]+row[3] に住所が書かれている。
    key =             
    value =             
    postcode[key] = value
# 実際に検索する (キーに対するバリューを取得する)。
import sys
key = sys.argv[1]
value =             
print(value)

5. 本日の課題

締め切り: 1月31日 (1週間後)
提出するファイル: shortest.py

授業中にやった最短経路を求めるプログラム shortest.py を改良し、任意の2駅間の最短経路が求められるようにせよ。このプログラムはコマンド引数から始点・終点を入力するものとする。

$ python shortest.py shibuya oookayama
shibuya
meguro
oookayama

プログラムの構成

# shortest.py
import sys

# エッジの一覧。
route = [
    ["jiyugaoka",  "denenchofu", 2],
    ["jiyugaoka",  "shibuya",    12],
    ["denenchofu", "oookayama",  4],
    ["jiyugaoka",  "oookayama",  3],
    ["shibuya",    "meguro",     5],
    ["oookayama",  "meguro",     9],
]

# 2点 a, b間の距離 (コスト) を返す。
def getcost(a, b):
    ...

# ノード x の隣のノード名一覧を返す。
def neighbors(x):
    ...

# 最短経路探索を実行し、
# start から goal へノードをたどる。
def shortest(start, goal):
    ...

start = sys.argv[1]  # 始点
goal = sys.argv[2]   # 終点
shortest(start, goal)

締め切り: 2月7日 (2週間後)
提出するファイル: solvemaze.py

ダイクストラの方法を使って、与えられた迷路の解法を表示するプログラム solvemaze.py を作成せよ。ここでは迷路の生成部分は考えなくてよい。迷路はつねに固定で、以下のもの使うこと。スタート・ゴールも固定である。

# 壁があるマスは 1 で、通路は 0 で表す。
m = [
    [1,1,1,1,1,1,1,1,1],
    [1,0,1,0,0,0,0,0,1],
    [1,0,1,0,1,0,1,0,1],
    [1,0,0,0,1,0,1,0,1],
    [1,1,1,1,1,0,1,0,1],
    [1,0,0,0,0,0,0,0,1],
    [1,0,1,0,1,1,1,1,1],
    [1,0,1,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1],
]

# スタートとゴールをそれぞれ (1,1) および (7,7) に定める。
start = [1,1]
goal = [7,7]

このプログラムを実行すると、以下のように表示して終了するようにする。

$ python solvemaze.py
#########
#.#...  #
#.#.#.# #
#...#.# #
#####.# #
#  ...  #
# #.#####
# #.....#
#########

プログラム中の適切な場所にコメントを入れ、各部分がどのように動くかを説明すること。

プログラムの構成

基本的に小課題 6. のプログラムと構成は同じである。が、各エッジのコストは必ず 1 なので getcost() 関数は必要なく、 neighbors() 関数は書き直す必要がある。

# solvemaze.py

# 迷路とスタート・ゴールの定義。
m = [ ... ]
start = [1,1]
goal = [7,7]

# 与えられたマス (ノード) p から進めるマスの座標一覧を返す。
def neighbors(p):
    ...

# 最短経路探索を実行する。
def shortest(start, goal):
   ...

# 完成した解法を表示する。
for y in range(len(m)):
    s = ""
    for x in range(len(m[y])):
        if m[y][x] == 1:    # 壁
            s = s + "#"
        elif m[y][x] == 2:  # 最短経路
            s = s + "."
        else:               # その他 (通路)
            s = s + " "
    print(s)

ヒント

[x,y] のようなリストを辞書のキーとして使うために、 str(x)+","+str(y) などとして座標を文字列に変換する。
最初にすべてのノードの cost を 9999 にするのは面倒くさいので、「cost 中に登録されていない場所はすべて 9999 とみなす」という処理をしてもよい。これは、以下のような if 文で実現できる:
```
k = str(x)+","+str(y)
if k in cost:
    # (x,y) が存在する場合。
    c0 = cost[k]
else:
    # (x,y) が存在しない場合、コストは 9999 とみなす。
    c0 = 9999
```
処理中、origin にたどるノードを入れておきたいが、これまた [x,y] のようなリストは辞書のキーとして使えないので、文字列に変換する。ただし辞書のバリュー部分にはリストが入れられるので、たとえば
```
origin["3,5"] = [3, 6]
```
などとすれば、たどるべき座標が取り出せる。 (もちろん、これ以外のやり方をしてもよい)

学修アンケートへの回答をお願いいたします。

Yusuke Shinyama