PSM

python する man

Python3でグラフの実装

pythonでのグラフとその探索の実装の仕方が分からず,悲しい思いをしたのでまとめました.

グラフの入力

ノードとエッジに関する情報は,競技プログラミングでよくあるように以下の形式で与えられるとします.
ノード(頂点)数はNで,a_i番目のノードとb_i番目のノードをi番目のエッジが結んでいることを表しています.

N
a1 b1
・
・
・
aN bN

今回使う数値例はこちら.
ノード数7,エッジ数6のグラフを考えてみます.

7
3 6
1 2
3 1
7 4
5 7
1 4

図にするとこんな感じです.
f:id:muromura:20170716021330p:plain


このグラフの入力は,例えば以下のように書いて受け取ることができます.

n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))

さて,このようにして情報を受け取ったとすると,いま,情報を以下の形式で持っています.

n=7  #ノード数
p = [[3,6], [1,2], [3, 1], [7,4], [5,7], [1,4]] #エッジ

つぎに,このグラフをプログラミングでどう表現するのか見てみます.

グラフの表現

グラフの実装の仕方は隣接リストと隣接行列の2通りあります.
どちらも一長一短あり,隣接リストはメモリの消費量
が少ない,隣接行列は直観的に分かりやすいなどの特徴があります.

そんな隣接リストの実装は以下となります.

#隣接リスト
l = [[] for i in range(n)]
for pi in p:  #0-originedに注意
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
print(l)

pythonは0-originな言語なので,このような書き方をすれば当然,隣接リストの先頭要素は[]となってしまいます.
しかし,今回はそれで大丈夫です.
違和感はありますが,無理に詰めるより頂点iについての情報がそのままi番目に格納されてくれていた方が,なにかと考えやすくてコードを書く時に便利です.

重みありの場合は以下のように情報が与えられます.

n=7  #ノード数
p = [[3,6,1], [1,2,2], [3, 1,3], [7,4,4], [5,7,5], [1,4,6]]

ここで,各要素の3番目が重みを表しています.
図にするとこんな感じ.赤い数字が重みを表しています.
f:id:muromura:20170817181213p:plain


重みありの場合は,[繋がっている頂点, 重み]としたリストを各頂点に突っ込んで行きます.

lw = [[] for i in range(n+1)]
for path in p:
    lw[path[0]].append((path[1],path[2]))
    lw[path[1]].append((path[0],path[2]))
print(lw)

隣接行列についても重みありと重みなしでメモしておきます.
こちらは[i-1, j-1]要素をノードiとノードjの接続情報の格納場所とし,重みなしのときは「繋がっている/いない」で「0/1」の2値を,重みありのときは重みを代入するだけなので簡単です.

#重みなし
m =[ [0]*n for i in range(n)]
for path in p:
    m[path[0]-1][path[1]-1] = 1
print(m) 

#重みあり
mw =[ [0]*n for i in range(n)]
for path in p:
    mw[path[0]-1][path[1]-1] = path[2]
print(mw) 

ウソつき問題とGW法

たまに見るウソつき問題にGW法という名前の万能の解法があることを知ったので,納得できるまで考えてみました.

はじめに

ウソつき問題とは以下のようなタイプの問題です.
誰しも小学生の頃にクイズ本やテレビのクイズ番組などで見たことがあると思います.

A~Dの4人が以下のようにそれぞれ証言している.
ただし,各人は必ずしも本当のことを言っているとは限らない.
A「Dはウソつきだ」
B「Cはウソつきだ」
C「AかDのどちらかはウソつきだ」
D「AかCのどちらかはウソつきだ」

このとき,以下の選択肢の中で,確実に正しいものはどれか.
1 Aはウソつきでない
2 Bはウソつきでない
3 Cはウソつきだ
4 Dはウソつきでない
5 ウソつきは2人いる

GW法の概要

正式名称はGrands Wagons法というらしいです.
さて,この作戦はたったの2ステップで表せます.
1.特定の発言によって登場人物をウソつき/正直者にグループ分けする
2.その他の発言によって正解を見つける

GW法

上の例であげた問題を考えてみます.

0.前提
まず,4人の人間がいます.
f:id:muromura:20170714143025p:plain
誰かはわかりませんが,ウソつきがいるようです.
f:id:muromura:20170714143040p:plain
ここでは正直者を白い人間,ウソつきを黒い人間で表してみます.
(あくまで例,上の問題でBとDがウソつきだというわけではないので注意)


1.グループ分け
あるタイプの証言に注目し,ルールに沿って登場人物をグループ分けします.
注目する証言のタイプは,『〜は正直者/ウソつきだ』のように特定の人物がウソつきかどうか直接的に言及しているものです.
そのとき,以下のルールに沿ってグループ分けすることができます.

・A「Bはウソつき」 なら AとBは違うグループ
・A「Bは正直」 なら AとBは同じグループ

Aがウソつきかどうかも分からないのに,本当にグループ分け出来ているの?と思ったので詳しく見てみます.

Aが「Bはウソつき」と言っている
f:id:muromura:20170714142334p:plain
f:id:muromura:20170714142755p:plain

Aが「Bは正直者」と言っている
f:id:muromura:20170714142827p:plain
f:id:muromura:20170714143202p:plain

どの場合も,AとBが同じグループに属するかどうかについて,正しく判断できていることがわかりました.

上の問題では,他者に直接言及しているのはAとBです.
ルールを適用すると,AとDは違うグループである,BとCは違うグループである,の2つがわかります.
ここでAとBがそれぞれウソつきかどうかを考えると,以下の4パターンのグループ分けが考えられます.
f:id:muromura:20170714143551p:plain
f:id:muromura:20170714143612p:plain
f:id:muromura:20170714143603p:plain
f:id:muromura:20170714143607p:plain




2.正解を見つける
つぎに,残るCとDの発言に注目して正解を見つけたいと思います.

Cの発言に注目すると,「AかDのどちらかはウソつき」と言っており,Aの発言からこれは明らかに正しいです.
よってCは正直者となります.
グループ分けの中でCが正直者となっているのは①と④で,ひとまずこれらが候補となります.

つぎにDの発言に注目します.
Cが確実に正直者であることはわかっているので,Dがウソつきかどうかを考えてみます.
①の場合はAはウソつき,CとDが正直者で,Dの発言内容と合致します.
④の場合はAとCが正直者,Dがウソつきとなりますが,これもDの発言内容が嘘ということとなり合致します.

以上より①と④はどちらもあり得るので1つに絞れません.
f:id:muromura:20170714143551p:plain
f:id:muromura:20170714143607p:plain
ここから確実に言えるのは,「Bがウソつき」「Cは正直者」「正直者とウソつきは2人ずつ」くらいです.
選択肢をみると,5の「ウソつきは2人いる」が正しいことがわかりました.


まとめ

以上がGW法によるウソつき問題の解法になります.
ルールにより機械的に分類作業をすすめ,あとは組み合わせを考えるだけなので,慣れるとかなり高速で解くことができそうです.



余談

A「Aはウソつきだ」

のような,自分について言及するような証言は,ウソつき問題では一般的に含まれません.
これはウソつきのパラドックスだとかエピメニデスのパラドックスとか言われる,自己言及のパラドックスというものの一種になるため回答者に誤解を与えるからだと思われます.
[wiki:自己言及のパラドックス]

Pythonでの再帰関数とメモ化

python3での再帰関数とメモ化についてまとめました.

はじめに

再帰関数とは.
定義の中に,自分自身を呼び出す(再帰)ようにして定義される関数のことです.
今回例にあげる再帰関数は,引数nが定数で明らかにn回以下のの繰り返しで書き換えることが可能なものばかりですが,再帰を用いて定義することにより簡単に記述することができます.

再帰関数はシンプルに実装すると,同じ計算を何回もすることが多いので,計算量の無駄が多くなります.
無駄を減らすためにいくつかの方策があるようなので,調べてまとめてみました.


例1:階乗

階乗とは,
 n! = n * (n-1) * \cdots *2 * 1
の計算のことです.階段のように一段ずつ変化する数をかけていくのでこう呼ばれています.
これを素直に実装すると,

 #階乗
def easyFact(n):
    if ( n==0 ): 
        return 1
    else: 
        return n*easyFact(n-1)

#結果
print([easyFact(i) for i in range(10)])

となります.


結果は

[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

例2:ユークリッドの互除法を用いた最大公約数

#最大公約数
def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

#結果
print(gcd(456,276))

結果は

12

本題:フィボナッチ数列

本題のフィボナッチ数列です.
フィボナッチ数列は,
1 1 2 3 5 8 13......
と,前2つの数を足していくことでつくられる数列です.少し前にダヴィンチ・コードなどで取り上げられて一躍有名になりました.


単純

#単純な再帰
def simFib(n):
    if ( n<=1 ):
        return 1
    else:
        return simFib(n-2) + simFib(n-1)

フィボナッチ数列のルールとして,初項は1,第2項は(0+1)で1が予め決まっています.
第3項以降は上であげた漸化式 a_{n+2} = a_{n+1}+a_nに沿って計算していきます.
この例ではnを更新するたびにわざわざ初項から計算しなおすことになり,実行速度が大変遅くなります.


末尾再帰

高速化には以下のような方針があります.

def endFib(n, a1 = 1, a2 = 0):
    if (n < 1): 
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)

直前の2つの値をa1,a2に記憶しておけば計算量が減るという考え方です.

繰り返し

def repFib(n):
    a1, a2 = 1, 0
    while n > 0:
        a1, a2 = a1 + a2, a1
        n -= 1
    return a1

末尾再帰は繰り返しに書き換えることができます.

行列

import numpy as np
def matFib(n):
    m = np.matrix('1 1 ; 1 0') ** n
    return m.item(0)

あくまでフィボナッチ数列に限った話ですが,この数列は行列をn乗した行列の要素として表現できます.
よって計算量はO(n)となります.

メモ化

本命です.
実はmemoFib()の動作はsimFib()と全く同じですが,メモ化関数memoize()を定義し,デコレータ表記を用いてメモ化しています.

def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def memFib(n):
    if ( n<=1 ):
        return 1
    else:
        return memFib(n-2) + memFib(n-1)

メモ化を用いることによって一度計算した値を記憶し,次にその値が欲しいときは,計算抜きにメモから呼び出せるようになります.
何回も同じ計算を実行するときなどに非常に早く計算できます.


実行時間の比較

お待ちかね,速度比較です.
フィボナッチ数列の第n項をFib(n)として,Fib(1)からFib(30)までを計算する時間の和を測りました.
いちいち書くのが煩雑だったので,計測過程を関数化しています.

import time
#計測用関数
def tc(func, n):
    s = time.time()
    a = [func(i) for i in range(n)]
    e = time.time() - s
    return  '{0:8.6f}'.format(e)+'秒'

#比較
print("単純__:", tc(simFib, 30))
print("末尾再帰:", tc(endFib, 30))
print("繰り返し:", tc(repFib, 30))
print("行列__:", tc(matFib, 30))
print("メモ化_:", tc(memFib, 30))


結果です.

単純__: 0.754400秒
末尾再帰: 0.000116秒
繰り返し: 0.000050秒
行列__: 0.002787秒
メモ化_: 0.000014

単純に書いた場合が圧倒的に遅いのに対し,他の場合ではかなりの高速化が行われています.
特に今回は
Fib(1)を計算⇨,Fib(2)を計算 ⇨……Fib(30)を計算
というように30回分いちいちフィボナッチ数列を計算しているので,メモ化によって大きな恩恵を受けていることがわかります.

Python3で最小木問題とプリム法

最小木問題を解くアルゴリズムのうち,プリム法をPython3で実装したのでメモ.
プリム法の実装の理解だけでなく,matplotlibを使ったので良い練習になりました.

wikipedia:プリム法

import matplotlib.pyplot as plt
import random
import numpy as np
import math
import sys

#最小木問題をプリム法で解く

#点群をランダム発生
p = [[random.uniform(0,100), random.uniform(0,100)] for i in range(100)]

#空のリストを用意
e = []  #部分最小木
av = []  #部分最小木に含まれる頂点
pv = list(p)  #その他の頂点

#始点は任意
av.append(p[0])
pv.remove(p[0])

while 1:
    #比較のための初期値として十分大きい数を用意
    shortestlen = sys.float_info.max
    #部分最小木に追加する辺を為す2点の初期化
    kav = None  #部分最小木に含まれる頂点からの候補
    kpv = None  #その他の頂点からの候補
    for v1 in av:
        for v2 in pv:
            #重みの計算(ここでは距離)
            dist = math.sqrt(  (v1[0]-v2[0])**2 + ( v1[1]-v2[1] )**2 )
            if shortestlen > dist:
                shortestlen = dist
                #候補の更新
                kav = v1
                kpv = v2
    if shortestlen > 0:
        #部分最小木に追加
        e.append([kav , kpv])
    #確定した頂点を移す
    av.append(kpv)
    pv.remove(kpv)
    #全頂点に対する判定を終えたら終了
    if len(pv) == 0:
        break


# 最小木の描画
for l in e:
    l = np.array(l).T
    plt.plot(l[0], l[1], 'k-', lw=2)
plt.show()


結果は
f:id:muromura:20170701180710p:plain
となりました.