第4回 - 乱数の発生、ランダムな迷路の生成

0. 前回の復習
   • 演習 4-1. リストの参照について・復習
1. 乱数とは
   • 演習 4-2. 疑似乱数の生成
   • 実際の乱数生成
   • サイコロを振るプログラム
2. リストについて・さらに補足
   • 演習 4-3. 要素の削除にかかる計算量
3. 迷路生成プログラム
   • プログラムの構造
   • 迷路生成アルゴリズム
   • 演習 4-4. 関数 shuffle() の完成
4. ブレイクアウトルーム練習
   • 演習 4-5. サイコロの合計値の統計をとる
5. 本日の課題
   • 小課題4. モンテカルロ法で円周率を求める (1月20日締切)
   • 中課題2. 迷路の生成 (1月27日締切)

雑談

アルゴリズムを舞踊で表現する

• フラメンコによる二分探索
• ルーマニアの民族舞踊で挿入法
• トランシルヴァニア・ザクソンの民族舞踊でマージソート
• おまけ・ソートする女の子

アホなソート法

1. いんちきソート (bogosort)
   1. a = [5,9,4,0,7,3,1,8,6,2]
   2. aのすべての順列を試す。
   3. もしその順列が昇順になっていたらそこで終了。
   当然、 O(n²) < O(n!) であるので、 これはマージソートや挿入法よりもはるかに効率が悪い。
2. スターリンソート
   1. a = [5,9,4,0,7,3,1,8,6,2]
   2. aの要素を最初から見ていく。
   3. もし昇順でない要素があれば、その要素を粛清する。
   4. すべての昇順でない要素を粛清した時点で終了。

ソーティング・ゲーム

• 東工大の学生が以前に開発した、ソートを手動でやってみるゲームがある。

0. 前回の復習

• 逐次探索と二分探索の違いについて学習した。
• 挿入法とマージソートについて学習した。

1. 乱数とは

乱数 (random number) とは、決められた範囲 (たとえば 0〜1) の間で一様に分布する、 ランダムな (予測できない) 数のことである。 こんにち、乱数はゲームやシミュレーションなどで使われているが、 実際には、真の乱数はコンピュータプログラムでは 絶対に生成できない。なぜなら、 プログラムというのは常に決まった動作をするからである。

“四則演算のみを使って乱数を生成しようとする者は、言うまでもなく背徳的なのだ。”
(Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.)

-- John von Neumann

多くの場合、コンピュータ上で実際に生成しているのは 「一見、乱数っぽく見える」数である。これを疑似乱数という。 たとえば、以下のプログラムを使うと疑似乱数を発生させることができる:

# 乱数の「シード」(種)
seed = 1
# 10個の疑似乱数を表示する。
for i in range(10):
    # seed の値を更新する。
    seed = ((seed * 1103515245) + 12345) % 134217727
    print(seed / 134217727)

このプログラムは区間 [0, 1) の 疑似乱数 (0 〜 0.99999...) を発生させるが、実際にやっていることは 変数 seed に適当な計算をほどこしているだけで、 seed の値がわかれば、以後の結果は完全に予測可能である。 しかしこの関数はカオス的なふるまいを示すため、 人間が見ると「乱数っぽい値」に見える。

• 有名な疑似乱数発生アルゴリズム

1.1. 実際の乱数生成

上のプログラムでは seed の値を定数にしているため、 実行するたびに同じ疑似乱数が発生する。乱数は シーザー暗号などの 鍵を生成するのに使われているため、この値が予測可能になってしまうのは 大きな問題である。(実際にこれで暗号が破られ、 秘密の情報が漏洩してしまう事故がある。) そのため、通常は疑似乱数のシードとして、 なんらかの外部から入力した値を使う。ここでは簡単な例として、 現在の時刻を使ってみる:

# 乱数の「シード」(種) として、現在時刻 (の秒数) を設定する。
import time
seed = time.time()
def rand():
    # 関数の外にある変数seedを変更できるようにする。
    global seed
    # seed の値を更新する。
    seed = ((seed * 1103515245) + 12345) % 134217727
    return seed / 134217727

この関数 rand() は現在時刻をシードとして使い、 呼び出すたびに疑似乱数を生成する。 ここで使っている global という文は、 関数の外で定義されている変数を関数の中から参照・変更するためのものである。

1.2. サイコロを振るプログラム

関数 rand() の値を n倍すると、 [0,1) の範囲を n倍するから [0,n) の範囲になる。 したがって 0〜(n-1) までの疑似乱数を生成できることになる:

x = int(rand()*6)+1
print(x)                      # 1から6のどれかの数。

x = 3.14
print(x)       # 3.14
print(int(x))  # 3

なお、rand() の乱数はほぼ 一様分布を示すので、以下のプログラムを実行すると ほぼすべての数が同じ頻度になるはずである:

# サイコロを1000回振って、出た目の統計をとるプログラム
a = [0] * 6
for i in range(1000):
    x = int(rand()*6)
    a[x] = a[x] + 1
print(a)

2. リストについて・さらに補足

Python では、print() や str() などの関数は 自分で定義しなくても最初から使える。このような関数を組み込み関数という。 いっぽう、リスト a をコピーする場合、 copy(a) ではなく a.copy() のようにする。 この .copy() の部分は メソッド と呼ばれる。 本当は copy() のような組み込み関数にしてもよかったはずだが、 おそらく組み込み関数の数を増やしすぎると名前がカブってしまう (誰か他の人が copy() という関数を作りたくても作れない) ためであると思われる。

以下では、リストの操作をするためのいくつかのメソッドを紹介する。

リストをコピーして新しいものを作成する:

b = a.copy()

n要素のリストをコピーするのにかかる計算量は O(n) である。

リストの末尾に要素を追加する (破壊的):

a.append(値)

例:

x = ["dog", "cat"]
x.append("cow")
print(x)   # ["dog", "cat", "cow"]

ひとつの要素を追加するのにかかる計算量は O(1) である。 ちなみに、同じ処理は + 記号を使ってもできる:

x = x + [ "cow" ]

リストの途中に要素を挿入する (破壊的):

a.insert(位置, 値)

例:

x = ["dog", "cat", "cow"]
#   0      1      2
x.insert(1, "penguin")
print(x)   # ["dog", "penguin", "cat", "cow"]

n要素のリストに新たに要素を挿入する場合、後続の要素をずらす必要があるため 最悪で O(n) の計算量がかかる。

リストの要素を削除する (破壊的):

del a[位置]

例:

x = ["dog", "penguin", "cat", "cow"]
del x[2]
print(x)   # ["dog", "penguin", "cow"]

3. 迷路生成プログラム

以下のような迷路を自動生成するプログラム genmaze.py を作成したい。

$ python genmaze.py 15 15
###############
#     #       #
# ##### #######
#         #   #
# ##### ### ###
#     #       #
# # ####### # #
# #       # # #
# # # ### # # #
# # #   # # # #
# # # ##### # #
# # #     # # #
### ##### # # #
#       # # # #
###############

3.1. プログラムの構造

まずプログラム全体の構造を以下のように考える。 関数 genmaze(w, h) は、 w × h マスの迷路データを生成し、 返すものとする。迷路は 2次元のリスト (リストのリスト) として表現する。 迷路の 1マスは、0 または 1 の数によって表す。 ここでは 1 が壁のある部分、 0 が壁のない部分 (通路) とする。

# genmaze: w×h の迷路を生成する。
def genmaze(w, h):
    m = []
    for i in range(h):
        m.append([1]*w)
    # ... 迷路生成アルゴリズム ...
    return m

さらに 0 と 1 でできた迷路を実際に表示する関数 showmaze() を用意する:

# showmaze: 与えらえた迷路を表示する。
def showmaze(m):
    for y in range(len(m)):
        # 空の文字列を用意し、1文字ずつ足していく。
        s = ""
        for x in range(len(m[y])):
            # 座標 (x,y) に壁があるかどうかを判定する。
            if m[y][x] == 1:
                s = s + "#"
            else:
                s = s + " "
        print(s)
    return

あとはコマンド引数を使ってこれを呼び出す部分を書けばよい:

import sys
...
width = int(sys.argv[1])
height = int(sys.argv[2])
m = genmaze(width, height)
showmaze(m)

3.2. 迷路生成アルゴリズム

実際には、 迷路を生成するアルゴリズムはいくつもある。 ここでは、Primの方法を使う。 いわゆる「根っこ伸ばし方式」:

1. 迷路のすべての部分を「土」とする。
2. 迷路の中の適当な位置に「種」をおき、そこから根を伸ばす。
3. 根はあらゆる方向に、同時に、伸びられるだけ伸びる。
4. 迷路の中が根っこで一杯になったら (伸びる場所がなくなったら) 完了し、 根っこのあった部分を通路とする。

この方法がなぜいいのかというと、

• 根が迷路中のすべての位置をカバーしている。
• すべての部分がつながっている。 つまり、あらゆる地点から、任意の地点に行く経路が存在する。
• 根はループしない。別の根にぶつかったら、もうそれ以上伸びない。

「根っこのある部分」は、 迷路中の位置 (座標) のリストとして表現する。 各座標は 2要素のリスト [x, y] で表現する。

root = [[3,4], [3,5], [4,5], ...]

実際には「同時に伸びる」というのはプログラムで実現するのは難しいので、 「根のあるランダムな部分が毎回少しずつ伸びていく」ことにする。 ループを設定し、1ターンごとに、根の中のランダムな部分が 四方に1マス分だけ伸びることにする。これを、すべての部分についてくりかえす。 全体のアルゴリズムは以下のようになる:

root = [スタート座標]
while 0 < len(root):
    root 中の座標ひとつを取り出す。
    for 隣接する座標のうち、まだ伸びていない場所に対して:
        その場所に新しく根を伸ばし、root に入れる。

スタート座標は、迷路の中であればどこでもよく、 (1,1) のような固定された値でもよい。 どちらにせよ、結果はランダムになるはずだからである。

3.2.1. リストから要素を取り出す

リスト root には len(root) 個の要素がある。 この中からひとつをランダムに取り出す。まず乱数をひとつ取得する。

i = int(rand()*len(root))

p = root[i]
x = p[0]
y = p[1]

del root[i]

3.2.2. 隣接する座標を選ぶ

次に、その座標 [x,y] から 上下左右の隣の位置に根が伸びることができるかどうか判定する。 ここでも、伸びる方向はランダムでなければならない。 ここでは以下のどれかの選択肢をランダムな順序で試すことを考える:

1. 上方向 [0, -1] に伸びることができるか?
2. 下方向 [0, 1] に伸びることができるか?
3. 左方向 [-1, 0] に伸びることができるか?
4. 右方向 [1, 0] に伸びることができるか?

これを実現するために、上下左右をあらわすベクトルを 4種類用意し、それをシャッフルしてから順番に試すことにする (座標と方向ベクトルは、どちらも同じ 2要素のリストで表せる)。 リストの要素をシャッフルするには、リストの中から ランダムな位置の要素を2つ選び、それらを入れ替える。 これをだいたいリストの要素数ぶんだけ繰り返せば、 結果として得られるリストはほぼシャッフルされているといえる。

def shuffle(a):
    # リストの要素数ぶんだけ繰り返す。
    n = len(a)
    for k in range(n):
        # i, j: a中のランダムな位置
        i = ????
        j = ????
        # a[i] と a[j]を入れ替える。
        ????????
    return a

dirs = [[0,-1], [0,+1], [-1,0], [+1,0]]
shuffle(dirs)
print(dirs)

3.2.3. 伸ばせるかどうかチェックする

shuffle()関数を使って、 ランダムな順で試す 4通りのベクトルを得られたとする。 ここからひとつずつベクトルの x成分と y成分を取り出し、 その方向に根を伸ばせるかどうかチェックする。

for i in range(4):
    v = dirs[i]
    vx = v[0]
    vy = v[1]
    # [vx,vy] の方向に伸ばせるかどうかチェックする。
    ...

根っこが伸ばせるかどうかを判定するには、 以下の2つのマスが壁である (まだ根が伸びていない) かどうかを 判定すればよい:

• 点 [x,y] に対して、隣の位置 = [x+vx, y+vy]
• 点 [x,y] に対して、2マス隣の位置 = [x+2*vx, y+2*vy]

迷路の情報は変数 m に入っている。 これは行、列ごとのリストであるので、ある座標 [nx, ny] に壁が存在するかどうかは m[ny][nx] の値をチェックすればよい。

if m[ny][nx] == 1:
    # ...壁があるときの処理...
else:
    # ...壁がないときの処理...

もし根が伸ばせるときは、その新しい座標を リスト root に追加し、処理を続行する。 いずれ迷路の中で根がいっぱいになると、 それ以上伸ばせなくなり、root 内の 要素は減っていくはずである。

root.append([nx, ny])

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

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

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

ほぼ雑談・コンピュータサイエンスと直接関係ない統計の話

統計学では、ある分布 (どんな分布でもよい) をもつ複数の 確率変数を足し合わせると、多くの変数を足せば足すほど、 それらの合計値の分布は正規分布に近くなることが知られている (中心極限定理)。

自然界の量 (身長、平均寿命、テストの成績など) にこれほど 正規分布を示すものが多いのは、これらの量が多くの 異なるファクターの和によって表されるためであると推測される。

なお、「トム・ソーヤーの冒険」などで知られる 米国の作家マーク・トウェインは次のような言葉を残している:

まず嘘があり、次に恥知らずな嘘がある。最悪なのが、統計だ。
(Lies, damned lies and statistics.)

-- Mark Twain

5. 本日の課題