2011-01-18

点線で楕円を描く

math

[追記] この記事には誤りが含まれています。訂正した記事はこちらです。

今日は 1 つネタをもらったので, ガチな数学をやろうと思います.

お題は「点線で楕円を描く」です.

円の場合は, 等角度ごとに区切って点線を書いていけば良いので簡単です.
たいていの場合, 三角関数は標準ライブラリにあるのであまり苦労しません.

しかし楕円の場合となると, 円がつぶれた形をしているので一筋縄ではいきません.

話の流れを追いつつ, どう解決していったか見ていきましょう.

発端

募集：PIL で点線の楕円を描画するのが得意な人。つーか、arc (円弧描画)関数だけで点線が書ける人。
http://twitter.com/#!/tk0miya/status/26986376482267136

楕円の場合は角度あたりの弧の長さが均等にならないよね。つまり点線を描画するにはどうすればいいんだ? 平面幾何なんてさっぱり分からないんだから、こんなん解決できないよ！
http://twitter.com/#!/tk0miya/status/26987619082571776

@tk0miya 楕円の弧長の話ですよね? その計算は楕円積分と言って, 数学で有名な積分計算です. 円もそうですが初等関数にならないので, きっちり計算する以上に楽な方法はありません. 計算式書きましょうか?
http://twitter.com/#!/cocoatomo/status/26991426927599616

実は, この楕円の弧長を求めるという問題は数学でも大きな問題でした.
いったいこれはどんな性質を持っているのか? 三角関数のようなものなのか?

数学のはなし

これを研究していた人たちにヤコビやワイエルシュトラスがいます.
彼らは
$\begin{align*}\begin{cases}x = a \cos \varphi \\ y = b \sin \varphi\end{cases}\end{align*}$
という楕円の周を $(a, 0)$ から左回りにたどったときの長さを求める積分
$\begin{align*}E(k,\quad \varphi) = \int_0^{\varphi} \sqrt{1 - k^2 \sin^2 \varphi} d \varphi \\ (k^2 = \frac{a^2 - b^2}{a^2}) \end{align*}$
の逆関数に着目し, その性質を調べ数学的な業績を挙げました.

その逆関数を $\varphi(k,\quad u)$ とするとその微分は以下のように求まります. (みなさん高校でやりましたね!?)
$\begin{align*}\frac{d \varphi}{du}(k,\quad u) &= \frac{1}{E'(k,\quad \varphi)} \\ &= \frac{1}{\sqrt{1 - k^2 \sin^2 \varphi}} \\ (u = E(k,\quad \varphi)) \end{align*}$

これを微分の形から差分の形に直して
$\begin{align*} \Delta \varphi &= \frac{\Delta u}{\sqrt{1 - k^2 \sin^2 \varphi}}\end{align*}$
これをさらに総和の形に直すと
$\begin{align*}\varphi_0 &= 0 \\ \varphi_n &= \varphi_{n-1} + \Delta \varphi_{n-1} \\ &= \varphi_{n-1} + \frac{\Delta u}{\sqrt{1 - k^2 \sin^2 \varphi_{n-1}}} \\ (\varphi_n \approx \varphi(n * \Delta u) \) \end{align*}$
となる.

なので, $\varphi (k,\quad u)$ の値を求めるときは $n$ を十分大きく (つまり $\Delta u = u/n$ 十分小さく) とれば $\varphi$ の値が差分の総和を計算することで求まり, $x = a \cos \varphi,\quad y = b \sin \varphi$ という計算で座標の値に戻せる.

誤差評価を行ってないので収束あたりがまだあやしいけれど, 一応目処は立った.
これからは誤差が出てしまったときの対処が残っているかな.

あとがき

こんなんでどうでしょう, tk0miya さん.

2011-01-17

グラフのはなし・その11

math ComputerScience order graph Python

さて前回 mro のトポロジカルソートを使った実装までできたのですが, mro の失敗が検知できない不十分なアルゴリズムで実装してしまいました.

今回はその不十分なところを修正するために, 今まで 2 つ (「未探索」と「探索済」) しかなかったノードの状態を 3 つ (「未探索」と「探索中」と「探索済」) に増やします.

ソースコード

改良したソースコードはこんなふうになります.

変わっている部分は PyClass オブジェクトの checked フィールドが color フィールドに変わり, その取る値が「真偽値」から 'WHITE', 'GRAY', 'BLACK' の 3 色になったところです.

それに合わせて, 探索の状態に応じて色を変えるようにし, 探索済をチェックするコードも色で判定するように変えました.
まずは実行してみてください.

# -*- coding: utf-8 -*-
class PyClass(object):
    def __init__(self, name=''):
        self.name = name
        self.color = 'WHITE'  # 最初はみんな白
        self.parents = []

    def __str__(self):
        return self.name

    def __repr__(self):
        return str(self)

# クラスの準備
D = PyClass('D')
C1 = PyClass('C1')
C2 = PyClass('C2')
B1 = PyClass('B1')
B2 = PyClass('B2')
A = PyClass('A')

# 矢印の準備
D.parents = [C2, C1]
C1.parents = [B2, B1]
C2.parents = [B2, B1]
B1.parents = [A]
B2.parents = [A]

# 探索完了の記録用リスト
searched = []

# クラスの継承関係を探索する
def dfs(klass):
    print('-> {0.name}'.format(klass))
    if klass.color == 'BLACK' or klass.color == 'GRAY': # 色のチェック
        print(u'{0.name} はチェック済み. 色: {0.color}'.format(klass))
        print('<- {0.name}'.format(klass))
        return

    klass.color = 'GRAY' # 探索中の色に塗る
    for parent in klass.parents:
        dfs(parent) # さらに継承関係を探索する

    print(u'{0.name} を黒に塗って引き返す'.format(klass)) # 祖先クラスの探索が終わった引き返す
    klass.color = 'BLACK' # 探索完了の色に塗る
    global searched
    searched.append(klass) # 探索が完了したら記録
    print('{1} を追加: {0}'.format(searched, klass))
    print('<- {0.name}'.format(klass))


if __name__ == '__main__':
    dfs(D)
    searched.reverse()
    print(searched)

きっとこんな結果になったはずです.

-> D
-> C2
-> B2
-> A
A を黒に塗って引き返す
A を追加: [A]
<- A
B2 を黒に塗って引き返す
B2 を追加: [A, B2]
<- B2
-> B1
-> A
A はチェック済み. 色: BLACK
<- A
B1 を黒に塗って引き返す
B1 を追加: [A, B2, B1]
<- B1
C2 を黒に塗って引き返す
C2 を追加: [A, B2, B1, C2]
<- C2
-> C1
-> B2
B2 はチェック済み. 色: BLACK
<- B2
-> B1
B1 はチェック済み. 色: BLACK
<- B1
C1 を黒に塗って引き返す
C1 を追加: [A, B2, B1, C2, C1]
<- C1
D を黒に塗って引き返す
D を追加: [A, B2, B1, C2, C1, D]
<- D
[D, C1, C2, B1, B2, A]

引き返すときに色を黒く塗っているのが分かりますね.

またごちゃごちゃするので出力はしていませんが, あるクラスの探索を始めるときにはそのクラスを灰色に塗っています.

あとがき

今日のところはここまでにします.

次回はこの色付けがどのように役立つのか, やや理論寄りな話をしたいと思います.
理論と言ってもできるだけ分かりやすく書くつもりなので, 紙とペン, 鉛筆を用意しておいてください.

それでは.

2011-01-16

グラフのはなし・その10

math ComputerScience order graph Python

さて今回は C3 アルゴリズムをトポロジカルソートで書けることを示してみましょう.

戦略

さて C3 アルゴリズムの肝は何だったかと言うと, それぞれの親クラスにとっての祖先クラスの順序と, 親クラスどうしの順序が食い違わないように, 祖先クラスを並べることでした. その操作を $merge$ 関数で行っていたのですね.

トポロジカルソートでもこれを真似してみましょう.
注意する点としては, このブログで出したトポロジカルソートのアルゴリズムでは, リストに点を追加していって最後に引っ繰り返していることです.

なので, あるクラスの親クラスリストでは順序を逆に並べます.

実装して実行してみる

こんな例を使いましょう. この継承関係は食い違いは起こしていませんね? 確認してみてください.

クラス: 親クラス
B1: A
B2: A
C1: B1, B2
C2: B1, B2
D: C1, C2

このような継承関係を Python スクリプトで書くとこうなります.

# クラスの準備
D = PyClass('D')
C1 = PyClass('C1')
C2 = PyClass('C2')
B1 = PyClass('B1')
B2 = PyClass('B2')
A = PyClass('A')

# 矢印の準備
D.parents = [C2, C1]
C1.parents = [B2, B1]
C2.parents = [B2, B1]
B1.parents = [A]
B2.parents = [A]

優先度とは逆に親クラスが並べてあるのが分かりますね.

さて先祖クラスの順序を求める以下の Python スクリプトを動かしてみましょう.
コメントや文字列が少し変更されてますが, スクリプトの中身はほとんど昨日使っていたものと同じです.
(Python2.7 で動くことを確認しています. Python2.6 や Python3.1 でも動くはずです.)

# -*- coding: utf-8 -*-
class PyClass(object):
    def __init__(self, name=''):
        self.name = name
        self.checked = False
        self.parents = []

    def __str__(self):
        return self.name

    def __repr__(self):
        return str(self)

# クラスの準備
D = PyClass('D')
C1 = PyClass('C1')
C2 = PyClass('C2')
B1 = PyClass('B1')
B2 = PyClass('B2')
A = PyClass('A')

# 矢印の準備
D.parents = [C2, C1]
C1.parents = [B2, B1]
C2.parents = [B2, B1]
B1.parents = [A]
B2.parents = [A]

# 探索完了の記録用リスト
searched = []

# クラスの継承関係を探索する
def dfs(klass):
    print('-> {0.name}'.format(klass))
    if klass.checked:
        print(u'{0.name} はチェック済み'.format(klass))
        print('<- {0.name}'.format(klass))
        return

    klass.checked = True
    for parent in klass.parents:
        dfs(parent) # さらに継承関係を探索する
    else:
        print(u'{0.name} から引き返す'.format(klass)) # 祖先クラスの探索が終わった引き返す

    global searched
    searched.append(klass) # 探索が完了したら記録
    print('{1} を追加: {0}'.format(searched, klass))
    print('<- {0.name}'.format(klass))


if __name__ == '__main__':
    dfs(D)
    searched.reverse()
    print(searched)

さて, みなさんの環境で動かすことはできたでしょうか?
スクリプトの動きについてはコメントや出力メッセージでなんとなく分かるように作ってあります. (分かりづらければコメントくださいな.)

ちゃんと動けばこんな出力になっているはずです.

-> D
-> C2
-> B2
-> A
A から引き返す
A を追加: [A]
<- A
B2 から引き返す
B2 を追加: [A, B2]
<- B2
-> B1
-> A
A はチェック済み
<- A
B1 から引き返す
B1 を追加: [A, B2, B1]
<- B1
C2 から引き返す
C2 を追加: [A, B2, B1, C2]
<- C2
-> C1
-> B2
B2 はチェック済み
<- B2
-> B1
B1 はチェック済み
<- B1
C1 から引き返す
C1 を追加: [A, B2, B1, C2, C1]
<- C1
D から引き返す
D を追加: [A, B2, B1, C2, C1, D]
<- D
[D, C1, C2, B1, B2, A]

探索が完了すると無事に正しい先祖クラスの順序になっていますね.

問題点

さてこのスクリプトには 1 つ問題があります. それは何でしょうか?

そうです. 継承関係の食い違いがあっても実行できて, 何らかの結果が出てきてしまうことです.
これはどこに問題があったのでしょうか?

PyClass というクラスのオブジェクトには checked というフィールドがあり, ここの値に「あるクラスが既に探索されたか?」という情報 (真偽値) を保存しておき二重探索を防いでいました.

しかし実は, 継承関係の食い違いを見付け出すためには真と偽の 2 つの値では不足していて, 「未探索」「探索中」「探索済」の 3 種類の値が無いといけないのです.

深さ優先探索のアルゴリズムから修正しないといけないので, また明日以降に今のスクリプトを改造していきましょう.

あとがき

なんだか最初の順序のはなしからだいぶ離れてしまったように感じますか?
これでも当初の目論見どおりなのです.

ここ最近, グラフやグラフアルゴリズムの勉強をしていたのですが, そこでふと「グラフアルゴリズムって, 点の整列を行っている」ことに気付いたのです.

「もしかして,『順序』という視点でグラフの話ができないか? それに最愛の言語 Python の mro (method resolution order, メソッド解決順序) もグラフアルゴリズムだ. そして Hadoop の MapReduce のジョブフローもグラフと見れ, その上のアルゴリズムは重要になるだろう. よし単純な順序の話を切り口に, 主にグラフの話しをしよう.」

こう思ってこの連載はスタートしました.
1ヶ月ネタが続くか不安でしたが, なんとか折り返し地点まで来れました.
これも毎日読んでいてくださるみなさまのおかげです.

後半も気を引き締めて, 回を落とさないように頑張ります.
よろしくです.

追伸

グラフアルゴリズムを解説するときは, グラフィカルな表示も欲しいですよね.
自分も欲しいです.

そう思ったので現在鋭意製作中です.
今は PyOpenGL で作っています.

完成をお楽しみに.

2011-01-15

グラフのはなし・その9

math ComputerScience order graph Python

今日は Perl や Python のクラスの多重継承で使われているアルゴリズム C3 を紹介します.

多重継承でメソッドを呼び出した場合, 複数の親クラスを持つので今呼び出しているメソッドがどの親に属しているのかを調べなければなりません.
そしてその順序も決めておき, 必ず決まったメソッドが呼ばれるようにしなくてはなりません.

それを実現する C3 アルゴリズムとはどんなものなのでしょうか?

C3 アルゴリズム概要

このページを参考にして解説を行います.
http://www.python.org/download/releases/2.3/mro/

数式で書いてしまえば,

$\mathrm{mro}(C) = [C] + \mathrm{merge}(\mathrm{mro}(P_1),\quad \mathrm{mro}(P_2),\quad \dots,\quad \mathrm{mro}(P_n),\quad [P_1,\quad P_2,\dots,\quad P_n])$

([P1, P2,..., Pn] は C の親クラス)

となります.
[C] は C 1 つからなるリストで, その後ろの "+" はリストの結合です.

右辺で再度 mro 関数が呼び出されていますが, 親クラスを持たないクラス C に対して $\mathrm{mro}(C) = C$ と定義されるので, この計算はどこかで止まります.

merge 関数では引数に入ってきたリストの順序を崩さずに, 新たなリストを作っているので, まさにトポロジカルソートが行われています.

C3 アルゴリズムの動き

具体的な merge 関数の動きを見ていきましょう.

まず, 先頭の引数 $\mathrm{mro}(P_1)$ (実体はリスト) から先頭の元 $P$ を取ってきます.
$P$ が他の引数 $\mathrm{mro}(P_2),\quad\mathrm{mro}(P_3),\dots,\quad\mathrm{mro}(P_n),\quad[P_1,\quad P_2,\dots,\quad P_n]$ のそれぞれの先頭にあるか, それとも含まれないか, をチェックします.
そのチェックが通った場合は $P$ を括り出します. (例はまた後で)
もしそのチェックに通らなければ, $\mathrm{mro}(P_2)$ に対して同じチェックを行います.
全ての引数でチェックが通らなければ $\mathrm{mro}$ 失敗です.

例

言葉だけの説明では分かりづらいので, 具体例を扱っていきましょう. (何度も言ってますが, 具体例を考えるのはすごく重要です.)

クラス: 親クラス
C: B

単純な継承です. すごく簡単だし, わざわざ計算しなくてもすぐに分かりますが, 練習として解いてみましょう.

$\begin{align*}\mathrm{mro}(C) &= [C] + \mathrm{merge}(\mathrm{mro}(B),\quad [B]) \\ &= [C] + \mathrm{merge}([B],\quad [B]) \\ &= [C] + [B] \\ &= [C,\quad B]\end{align*}$

確かに望んだ結果が出てきましたね.

では次はもう少し出てくるクラスを増やしましょう.

クラス: 親クラス
C: B1, B2

単純な多重継承です.

$\begin{align*}\mathrm{mro}(C) &= [C] + \mathrm{merge}(\mathrm{mro}(B_1),\quad \mathrm{mro}(B_2) [B_1,\quad B_2]) \\ &= [C] + \mathrm{merge}([B_1],\quad [B_2],\quad [B_1,\quad B_2]) \\ &= [C] + [B_1] + \mathrm{merge}([],\quad [B_2],\quad [B_2]) \\ &= [C] + [B_1] + [B_2] \\ &= [C] + [B_1,\quad B_2] \\ &= [C,\quad B_1,\quad B_2]\end{align*}$

こんな継承関係を考えてみましょう. これは有名なダイヤモンド継承ですね.

クラス: 親クラス
C: B1, B2
B1: A
B2: A

$\begin{align*}\mathrm{mro}(C) &= [C] + \mathrm{merge}(\mathrm{mro}(B_1),\quad\mathrm{mro}(B_2),\quad[B_1,\quad B_2]) \\ &= [C] + \mathrm{merge}([B_1,\quad A],\quad [B_2,\quad A] ,\quad[B_1,\quad B_2])\\ &= [C] + [B_1] + \mathrm{merge}([A],\quad [B_2,\quad A],\quad [B_2] ) \\ &= [C] + [B_1] + [B_2] + \mathrm{merge}([A],\quad [A],\quad []) \\ &= [C] + [B_1] + [B_2] + [A] \\ &= [C,\quad B_1,\quad B_2,\quad A] \end{align}$

今度はこんな計算になり, 上手く多重継承の先祖クラスの順序を扱えていますね.

4 段目で $A$ ではなく $B_2$ が括り出されているのは, $\mathrm{merge}$ 関数の第 2 引数に $[B_2,\quad A]$ というリストがあり, この順序を守るためです.

では最後に mro に失敗する例を考えてみましょう.

クラス: 親クラス
B1: A
B2: A
C1: B1, B2
C2: B2, B1
D: C1, C2

この継承関係では $C_1$ の親クラスの順序と $C_2$ の親クラスの順序が食い違っているので, きちんと先祖クラスの順序が付けられません.

実際に Python でクラス D を作ろうとすると, 以下のようにエラーが出て作ることができません.

>>> A = object
>>> class B1(A): pass
... 
>>> class B2(A): pass
... 
>>> class C1(B1, B2): pass
... 
>>> class C2(B2, B1): pass
... 
>>> class D(C1, C2): pass
... 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: Error when calling the metaclass bases
    Cannot create a consistent method resolution
order (MRO) for bases B2, B1

さて $\mathrm{mro}$ で計算してみましょう.

$\begin{align*}\mathrm{mro}(D) &= [D] + \mathrm{merge}(\mathrm{mro}(C_1),\quad \mathrm{mro}(C_2),\quad [C_1,\quad C_2]) \\ &= [D] + \mathrm{merge}([C_1,\quad B_1,\quad B_2,\quad A],\quad [C_2,\quad B_2,\quad B_1,\quad A],\quad [C_1,\quad C_2]) \\ &= [D] + [C_1,\quad C_2] + \mathrm{merge}([B_1,\quad B_2,\quad A],\quad [B_2,\quad B_1,\quad A],\quad [])\end{align*}$

とここまできて困ってしまいました. B1 と B2 の順序をどちらを先としてもうまく $\mathrm{merge}$ できません.
なので $\mathrm{mro}$ の計算は失敗し, ここで終了です.

あとがき

今日はトポロジカルソートが使われている一例として, Python の mro を扱いました.
昨日のトポロジカルソートとのつながりが話せていないので, 次回は Python の mro を実装し, 今までのトポロジカルソートと比べてみます.

2011-01-14

グラフのはなし・その8

math ComputerScience order graph Python

さて今日は目標の1つであったトポロジカルソートのプログラムを見てみましょう.
基本的な構造は昨日の深さ優先探索 (DFS) と同じです.

今日トポロジカルソートを行う DAG (輪っか無しの矢印グラフ) はこれです.

0 -> 1 -> 3
 |     `-> 4
 |         V
  `-> 2 -> 5
       `-> 6

昨日のグラフとだいたい同じですが,「4 → 5」の矢印が増えたところが違いますね. ここは後でポイントになりますので, 覚えておいてください.

トポロジカルソートを行う Python スクリプト

# -*- coding: utf-8 -*-                                                                                                                                         
class Node(object):
    def __init__(self, value=0):
        self.value = value
        self.checked = False
        self.children = []

    def __str__(self):
        return 'node{0}'.format(self.value)

    def __repr__(self):
        return str(self)

# 点の準備                                                                                                                                                      
node0 = Node(0)
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)

# 矢印の準備                                                                                                                                                    
node0.children = [node1, node2]
node1.children = [node3, node4]
node2.children = [node5, node6]
node4.children = [node5]

# 探索完了の記録用リスト
searched = []

# 分かれ道にきたらこの手順を踏む
def dfs(node):
    print('-> {0.value}'.format(node))
    if node.checked:
	print(u'チェック済み')
	print('<- {0.value}'.format(node))
	return

    node.checked = True
    for child in node.children:
	dfs(child) # さらに分かれ道にきたら同じ手順を繰り返す
    else:
        print(u'引き返す')

    global searched
    searched.append(node) # 探索が完了したら記録
    print(searched)
    print('<- {0.value}'.format(node))


if __name__ == '__main__':
    dfs(node0)
    searched.reverse()
    print(searched)

昨日のソースコードと違っているところはどこでしょうか?

searched というリストが増えた.
dfs というメソッドの終わりの方に searched に node を追加する操作が増えた.

この 2 点だけです.

実行結果は以下のようになりました. 最後の行がトポロジカルソートを行った結果です.
昨日の結果と比べて違っているところはどこでしょうか??

-> 0
-> 1
-> 3
引き返す
[node3]
<- 3
-> 4
-> 5
引き返す
[node3, node5]
<- 5
引き返す
[node3, node5, node4]
<- 4
引き返す
[node3, node5, node4, node1]
<- 1
-> 2
-> 5
チェック済み
<- 5
-> 6
引き返す
[node3, node5, node4, node1, node6]
<- 6
引き返す
[node3, node5, node4, node1, node6, node2]
<- 2
引き返す
[node3, node5, node4, node1, node6, node2, node0]
<- 0
[node0, node2, node6, node1, node4, node5, node3]

もちろんアルゴリズムは変更していないので, 昨日のグラフと今日のグラフの違うところが影響しているわけですね.

今日のグラフは「4 → 5」の矢印が増えているので, 4 の場所まできたときにさらに 5 の場所まで探索できます. それが出力の↓この部分に出ています.

-> 4
-> 5
引き返す
[node3, node5]
<- 5

考察

さて, 昨日のソースコードには無かった処理「searched.append(node) # 探索が完了したら記録」の部分について考えてみましょう.

当然この部分がトポロジカルソートの肝なのですが,「探索が完了」するとはどういうことでしょうか?
深さ優先探索とは,「探索していないところがあったらどんどん先に進んで, 行き止まりに到達したら引き返す」というものでしたね.
つまりここで言っている「探索が完了」というのは,「ここから行けるところはもう全て探索したよ」という意味なのです.

なので, searched (探索完了) という名前のリスト中のある点 A を見たとき, その点 A から到達できる点は, 必ずそれより前の方にあることになります.
ここがポイントなのですが分かりましたか?
自分でグラフを書いて, 上の処理を 1 つ 1 つ追っていってみてください.

こういうときに重要なのは具体例に対して自分の手を動かすこと.
頭だけで考えただけだと大抵はあやふやな理解しかできていません.
はっきり言いましょう. 手を動かさないで理解した気になっているのは勘違いです!! 手を動かして実験してみてください.

最後に reverse では結果が左右逆になっていて見づらいので, 引っくり返しているのです.

あとがき

昨日の深さ優先探索だったスクリプトが突然トポロジカルソートのスクリプトに変わって驚いたでしょうか?
実は, 私も深さ優先探索とトポロジカルソートのこの関係を知って驚きました.
しかし, よくよく考えて頭で味わってみると, なるほどよくできている関係でトポロジカルソートの性質をすっきり言い切っているなぁ, と感心しました.

こういう 1 つの概念やイメージが頭の中にスッと入ってくる瞬間が楽しくて私は数学をやっています.
みなさんもこの連載でそのような瞬間が味わえると望外の幸せです.

それでは.

2011-01-13

グラフのはなし・その7

math ComputerScience order graph Python

ちょっと今日は趣向を変えて, プログラムで語ってみます.

昨日まで理論の話だったので, 少し頭を切り替えて Python で深さ優先探索を書いてみます.

ソースコード

こんなふうなグラフを 0 からスタートして深さ優先探索してみましょう. このグラフは DAG になっていますね? なのでこれは半順序を表してるものと見れます.

0 -> 1 -> 3
 |     `-> 4
  `-> 2 -> 5
       `-> 6

これを Python で書くと次のようになります.

# -*- coding: utf-8 -*-                                                                                                                                         
class Node(object):
    def __init__(self, value=0):
        self.value = value
        self.checked = False
        self.children = []

# 点の準備                                                                                                                                                      
node0 = Node(0)
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)

# 矢印の準備                                                                                                                                                    
node0.children = [node1, node2]
node1.children = [node3, node4]
node2.children = [node5, node6]


# 分かれ道にきたらこの手順を踏む                                                                                                                                
def dfs(node):
    print('-> {0.value}'.format(node))
    if node.checked:
	print(u'チェック済み')
        print('<- {0.value}'.format(node))
        return

    node.checked = True
    for child in node.children:
        dfs(child) # さらに分かれ道にきたら同じ手順を繰り返す                                                                                                   
    else:
        print(u'引き返す')
    print('<- {0.value}'.format(node))


if __name__ == '__main__':
    dfs(node0)

Python2.7 で動くことを確認しています.

出力はこんな感じになりました.

-> 0
-> 1
-> 3
引き返す
<- 3
-> 4
引き返す
<- 4
引き返す
<- 1
-> 2
-> 5
引き返す
<- 5
-> 6
引き返す
<- 6
引き返す
<- 2
引き返す
<- 0

このプログラムではグラフの様子は固定になっていますが,「点の準備」と「矢印の準備」と書かれている部分を修正して, 色々試してみてください.

どうでしたか? 深さ優先探索の様子が分かったでしょうか?

あとがき

「やっつけな雰囲気が漂うが大丈夫か?」「大丈夫だ, 問題ない」

すみません, やっつけはやっつけです.

ただ昨日は言葉で説明しただけなので, 厳密な形で説明しなくてはいけませんでした. そこで Python という比較的ソースが読みやすい言語で書いてみました.

また, プログラムが分かる人にはこっちの方が理解が早いんじゃないかと思って, ちょっと寄り道してやってみました.

それでは, お休みなさい.

2011-01-12

グラフのはなし・その6

math ComputerScience order graph

さて, 今日からは探索やソートの話をしていきます.

探索やソートについては以前も触れましたが, ここで簡単におさらいをしておきます.

ソート (sort) とは

ソートは日本語に訳すと「並びかえ」になります. 文字通りなんらかの順序でものを並べかえる作業のことです.
人間が並びかえることもありますが, ソートと専門用語っぽく言ったときはコンピュータ (計算機) が並びかえる作業を指します.

探索 (search) とは

探索とは文字通り何かを探すことです. これもソートと同様コンピュータが何かを探す作業のことを指します.

人間とコンピュータ

人間がソートや探索をする場合には, 全体を見てなんとなく並びかえたり, だいたいここらへんにあるだろうと当たりを付けたりします. 人間 (生物) の脳が素晴しいのはこういった曖昧な処理や直感的な決定, 判断が行えることです.

それに比べコンピュータは (良く言われることですが) はっきり決めないと動いてくれません. なんせ中の仕組み (CPU やメモリ) がすごくシンプルなため, そのような処理はコンピュータにとっては高度で難しいことなのです.

深さ優先探索 (DFS)

さて, 何の話から始めようかと考えましたが, トポロジカルソートの話をするには深さ優先探索が必要なのでこれから話していきます.

迷路を進む

まず「深さ優先」って何? となると思いますが, これは探索の戦略を表しています. 巨大な迷路を進むことを考えてみましょう. イメージはこんな感じ. 迷路のゴールが探索のゴールとします

何も道具を使わないのは厳しいので, ヘンゼルとグレーテルを見習ってたくさん小石を地面に置く目印に使っていいことにしましょう.

さて, ではこの小石をどう使いましょうか?

ヘンゼルのように歩きながら小石を道に落としていきましょうか?

でもそれでどうやってゴールを探し出せば良いのでしょうか?

闇雲に歩きながら目印を落としても, 一度辿ったところは分かるのですが次にどこを探せば良いのか分からないですね.

おっと言い忘れましたが, この迷路は立体迷路なので右の壁づたいに進むとスタートに戻る可能性があります. 頭の良い人はこの方法を思い付いたかもしれませんが, それは平面の迷路でしか使えない手段です.

さっきちょっと書いた「次にどこを探せば良いのか」というのがヒントです.

さて思い付きましたか? (あ, 引っ張りすぎ??)

答えはこうです.

ゴールの探し方

歩きながら小石を落としていくことはするのですが, 一本道を歩いているときはもったいないので小石は落としません. 分かれ道に来たときに初めて小石を使います.

まず道がいくつかに分かれているところに来たら, 一番右の分かれ道に小石を 1 つ置いてその先へ進んでいきます. 分かれ道にくるたびに同じことをします.

するとゴールへ辿り着くか, どこかで行き止まりになるか, 小石が置かれた分かれ道に出るか, になりますね. ゴールならそこを出て迷路はクリアです.

行き止まりなら, 来た道を引き返して直前に小石を置いたところまで戻ります. その小石から行き止まりまでは一本道だったので, もうその道は探索しなくて良いですね? ここがポイントです.「もうその道は探索しなくて良い」ということが言えることが重要です.

小石が置かれていた分かれ道に出たなら, その分かれ道にはすでに一度来たことがあるはずです. 引き返す前に「もうこの分かれ道は辿ったよ」という印を置いて, 元来た道を帰りましょう.

さて分かれ道に戻って何をしましょう. 戻ってきた道が一番右の分かれ道だったので, その 1 つ左の道を同じく小石を置いて進みましょう. こんなふうに,

分かれ道に来たら右端の分かれ道に小石を置いて進む.
行き止まりか小石が置かれている分かれ道に出たら引き返して小石を置いたところまで戻る.
小石を置いた道の 1 つ左の道を進む.

以下, 道を選んで, 進んで, 戻って, また道を選ぶの繰り返しになります.

この方法でゴールが見付かる保証はちゃんとあります. (当然ちゃんとゴールがあれば, ですが...) しかも同じ道を 2 回探索しないで済む保証もあります.

なぜかと言うと, 分かれ道に来たときに全ての分岐を 1 回だけ探索しています. そして一度探索した道には小石を置いて 2 回以上探索しないようにしています. なのでこの方法でゴールが探し出せることになります.

あとがき

昨日は疲れで休んでしまいました. すみません.
この連載が更新されなかったときは仕事が忙しいんだな, と思ってくださいm(_ _)m

さて, 今日は探索戦略の 1 つ深さ優先探索のお話をしました. どう感じたでしょうか? いちいち事細かにやるのは煩わしいと思ったでしょうか? 本当にこれでゴールに辿り着けるのか不思議に思ったでしょうか? なるほどこういう方法もあったのか, と感心されたでしょうか?

それぞれ思うことはあるでしょうが, この方法はコンピュータだからできる, もしくはコンピュータだからせざるを得ない方法です. コンピュータは「今いるところが分かれ道かどうか」と「道を 1 つ進む」と「道を 1 つ戻る」の 3 つしかできません. その 3 つしかない方法を組み合わせてなんとか迷路を解くためには, こういった方法になります.

まずは,「コンピュータはできることを減らしたかわりに, 高速で作業ができるようになった」ということを感覚として持っておいてください. 今後も繰り返し言っていくと思います.

それでは.