Algorithms with Python

はじめに

今回は「集合 (set)」を表すデータ型を作ってみましょう。集合はいくつかの要素を集めたものです。一般に、集合は重複した要素を含まず、要素の順番に意味はありません。なお、要素の重複を許す集合は「多重集合 (multi set)」と呼ばれます。たとえば、集合 {1, 3, 5, 7} は {7, 5, 3, 1} や {5, 3, 1, 7} と表すこともできます。このように、要素は適当に並べてもかまわないのですが、ある規則で要素を整列させておく場合もあります。

Python の場合、集合を表すデータ型 set が用意されていますが、私達でも簡単にプログラムすることができます。今回はアルゴリズムのお勉強ということで、あえて「連結リスト (linked list)」を使って集合 (Set) を実装してみましょう。

最初に定義するメソッドを表に示します。

簡単な例を示しましょう。a = Set([1, 2, 3, 4, 5]), b = Set([4, 5, 6, 7]), c = Set([6, 7]) とします。

a.issubset(b) => False
c.issubset(b) => True

a.union(b) => Set([1, 2, 3, 4, 5, 6, 7])
a.union(c) => Set([1, 2, 3, 4, 5, 6, 7])

a.intersection(b) => Set([4, 5])
a.intersection(c) => Set([])

a.difference(b) => Set([1, 2, 3])
a.difference(c) => Set([1, 2, 3, 4, 5])

●プログラムの作成

それではプログラムを作りましょう。最初にクラスを定義します。

リスト : クラスの定義

class Set:
    class Cell:
        def __init__(self, x, next = None):
            self.item = x
            self.next = next
    
    def __init__(self, data = None):
        self.top = Set.Cell(None)   # Header Cell
        if data:
            for x in data:
                if not self.member(x):
                    self.top.next = Set.Cell(x, self.top.next)

クラス名は Set としました。連結リストを表す Cell は Set の中で定義します。インスタンス変数 item に要素を、next に次のセルへの参照を格納します。終端は None で表します。今回の連結リストはヘッダセルを使います。Set のインスタンス変数 top にヘッダセルを格納し、その後ろのセルに集合の要素を格納します。

Set のメソッド __init__() は、引数 data にデータがある場合、それを連結リストに格納します。このとき、重複した要素がないかメソッド member() を使ってチェックします。要素はヘッダセルの後ろに追加していきます。

member() は次のようになります。

リスト : 集合に要素が含まれているか

    def member(self, x):
        cp = self.top.next
        while cp:
            if cp.item == x: return True
            cp = cp.next
        return False

最初に、ヘッダセルの後ろのセルを取り出して変数 cp にセットします。あとは、セルをたどって x と等しい要素 (cp.item) を探します。見つけた場合は True を返します。なければ False を返します。探索は基本的な操作なので難しいところはないでしょう。

member() を使うと、データを挿入するメソッド insert() は簡単です。次のリストを見てください。

リスト : データの挿入

    def insert(self, x):
        if not self.member(x):
            self.top.next = Set.Cell(x, self.top.next)

データ x が自分自身 (self) に含まれているか member() を呼び出してチェックします。含まれていなければ、ヘッダセルの後ろにデータを挿入します。これも簡単ですね。

メソッド issubset() と isequal() も簡単です。プログラムは次のようになります。

リスト : 集合の同値と包含関係の判定

    # 部分集合の判定
    def issubset(self, x):
        cp = self.top.next
        while cp:
            if not x.member(cp.item): return False
            cp = cp.next
        return True

    # 同値の判定
    def isequal(self, x):
        return self.issubset(x) and x.issubset(self)

集合 self の要素が集合 x にすべて含まれている場合、issubset() は True をかえします。異なる要素があれば部分集合ではないので False を返します。self の連結リストを順番にたどって cp.item が x に含まれているか member() を呼び出してチェックするだけです。

集合の同値関係 a = b は、a が b の部分集合で、かつ b が a の部分集合のときに成立します。したがって、isequal() は self.issubset(x) and x.issubset(self) をチェックするだけです。

●union

次は 2 つの集合の和を求めるメソッド union() を作ります。プログラムは次のようになります。

リスト : 集合の和を求める

    def union(self, x):
        def _union(cp):
            if cp is None: return x.top.next
            elif x.member(cp.item):
                return _union(cp.next)
            else:
                return Set.Cell(cp.item, _union(cp.next))

        s = Set()
        s.top.next = _union(self.top.next)
        return s

union() は集合 self と x の和を計算します。実際の処理は内部関数 _union() で行います。_union() の引数 cp は self の連結リストです。cp.item が x に含まれていなければ、その要素を x の連結リスト x.top.next に追加します。この処理を再帰呼び出しで行っています。

_union() の引数 cp が None の場合は、x の連結リストをそのまま返します。union は第 2 引数の連結リストを共有することに注意してください。次に、cp.item が x に含まれている場合は _union() を再帰呼び出しして、その返り値をそのまま返します。そうでない場合は、cp.item を新しいセルに格納して返します。これで cp.item を集合に含めることができます。

あとは、Set() で新しい集合 s を生成し、s.top.next に _union の返り値をセットするだけです。これで集合の和を求めることができます。

●intersection

次は 2 つの集合の積を求めるメソッド intersection() を作ります。

リスト : 集合の積を求める

    def intersection(self, x):
        def _intersection(cp):
            if cp is None: return None
            elif x.member(cp.item):
                return Set.Cell(cp.item, _intersection(cp.next))
            else:
                return _intersection(cp.next)

        s = Set()
        s.top.next = _intersection(self.top.next)
        return s

intersection() は集合 self と x の積を計算します。実際の処理は内部関数 _intersection() で行います。_intersection() の引数 cp は self の連結リストです。cp.item が x に含まれている場合は、その要素を新しい集合 (連結リスト) に追加します。この処理を再帰呼び出しで行っています。

_intersection() の引数 cp が None の場合は、空リスト None を返します。次に、cp.item が x に含まれている場合は cp.item を新しいセルに格納して返します。これで cp.item が集合に含まれます。そうでなければ、_intersection() の返り値をそのまま返します。

あとは、新しい集合を Set() で生成して、s.top.next に _intersection() の返り値をセットするだけです。これで集合の積を求めることができます。

●difference

次は集合の差を求めるメソッド difference() を作ります。

リスト : 集合の差を求める

    def difference(self, x):
        def _difference(cp):
            if cp is None: return None
            elif x.member(cp.item):
                return _difference(cp.next)
            else:
                return Set.Cell(cp.item, _difference(cp.next))

        s = Set()
        s.top.next = _difference(self.top.next)
        return s

difference() は集合 self と x の差を計算します。実際の処理は内部関数 _difference() で行います。_difference() の引数 cp は self の連結リストです。cp.item が x に含まれていない場合、その要素を新しい集合 (連結リスト) に追加します。この処理を再帰呼び出しで行っています。

_difference() の引数 cp が None の場合は、空リスト None を返します。次に、cp.item が x に含まれている場合は _difference() の返り値をそのまま返します。そうでなければ、cp.item を新しいセルに格納して返します。これで cp.item が集合に含まれます。

あとは、新しい集合を Set() で生成して、s.top.next に _difference() の返り値をセットするだけです。これで集合の差を求めることができます。

●要素の削除

最後に要素を削除するメソッド remove() を作ります。次のリストを見てください。

リスト : 要素の削除

    def remove(self, x):
        def _remove(cp):
            if cp is None: return None
            elif cp.item == x: return cp.next
            else: return Set.Cell(cp.item, _remove(cp.next))

        self.top.next = _remove(self.top.next)

union() で連結リストを共有しているので、remove() は新しいリストを生成して返します。実際の処理は内部関数 _remove() で行います。_remove() の引数 cp は self の連結リストです。cp が None の場合は空リスト None を返します。これは削除する要素 x が見つからない場合です。

次に cp.item が x と等しい場合は、それ以降の要素を調べる必要はないので cp.next を返します。ここで、要素 cp.item が削除されます。そうでなければ、cp.item を新しいセルに格納して返します。あとは、self.top.next の値を _remove() の返り値に書き換えるだけです。

あとはとくに難しいところはないでしょう。詳細は プログラムリスト１ をお読みください。また、要素の個数が多くなると連結リストでは処理が遅くなってしまいます。そのような場合はハッシュ法を使うと良いでしょう。ご参考までに、Python の辞書 (dictionary) を使った実装を プログラムリスト２ に示します。よろしければお読みください。

●実行例

それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。

# 簡単なテスト
if __name__ == '__main__':
    a = Set([1,2,3,4,5])
    b = Set([4,5,6,7,8])
    print(a)
    print(b)
    c = a.union(b)
    print(c)
    d = a.intersection(b)
    print(d)
    e = a.difference(b)
    print(e)
    print(a.issubset(c))
    print(c.issubset(a))
    print(a.isequal(a))
    a.insert(1)
    print(a)
    a.insert(10)
    print(a)
    b.remove(5)
    print(b)
    print(c)

実行結果を示します。

Set([5, 4, 3, 2, 1)]
Set([8, 7, 6, 5, 4)]
Set([3, 2, 1, 8, 7, 6, 5, 4)]
Set([5, 4)]
Set([3, 2, 1)]
True
False
True
Set([5, 4, 3, 2, 1)]
Set([10, 5, 4, 3, 2, 1)]
Set([8, 7, 6, 4)]
Set([3, 2, 1, 8, 7, 6, 5, 4)]

●追記 : 直積集合

平面や空間などの座標において、各成分がすべて整数であるような点を「格子点 (lattice point)」といいます。二次元の座標 (x, y) で x と y の範囲が有限であれば、格子点は「直積集合 (direct product)」で求めることができます。直積は「デカルト積 (Cartesian product)」と呼ばれることもあります。

最近では、多くの処理系で集合演算をサポートしています。その中には、直積集合を求める関数 (product など) が用意されている処理系もあります。Python の標準ライブラリ itertools には product() が用意されていますが、内包表記が使える処理系の場合、直積集合は私達でも簡単にプログラムすることができます。

リスト : 直積集合 (Python)

def product(xs, ys):
    return [(x, y) for x in xs for y in ys]

>>> product([1, 2, 3], [4, 5, 6])
[(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]

三次元の座標は product() を 2 回使えばできるはずです。結果は次のようになりました。

>>> product(product([1, 2], [3, 4]), [5, 6])
[((1, 3), 5), ((1, 3), 6), ((1, 4), 5), ((1, 4), 6), ((2, 3), 5), ((2, 3), 6), ((2, 4), 5), ((2, 4), 6)]

>>> product([1, 2], product([3, 4], [5, 6]))
[(1, (3, 5)), (1, (3, 6)), (1, (4, 5)), (1, (4, 6)), (2, (3, 5)), (2, (3, 6)), (2, (4, 5)), (2, (4, 6))]

集合 A, B の直積集合を A * B で表すと、一般に A * B = B * A は成り立ちません。また、(A * B) * C の要素は ((a, b), c) に、A * (B * C) の要素は (a, (b, c)) に、A * B * C の要素は (a, b, c) になるので、厳密に言えばこれらは異なる集合になります。

実際には、((a, b), c) や (a, (b, c)) を (a, b, c) と同一視して、複数の集合の直積を 2 つの集合の直積の繰り返しで定義してもよいようです。詳しくは 参考 URL 1 をお読みください。

これを Python でプログラムすると次のようになります。

リスト : 直積集合 (その２)

def product(*args):
    if len(args) == 0: return [()]
    ys = [(x,) for x in args[0]]
    for i in range(1, len(args)):
        ys = [(*y, x) for y in ys for x in args[i]]
    return ys

最初に、先頭のリスト args[0] の要素をタプルに包み、それを格納したリストに変換します。あとは順番に、タプル y の後ろにリストの要素 x を追加していくだけです。Python の場合、リストやタプルの前に * を付けると、要素が展開されることに注意してください。

それでは実際に試してみましょう。

>>> product([1, 2, 3], [4, 5, 6])
[(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]
>>> product([1, 2], [3, 4], [5, 6])
[(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]
>>> product([1, 2], [3, 4], [5, 6], [7, 8])
[(1, 3, 5, 7), (1, 3, 5, 8), (1, 3, 6, 7), (1, 3, 6, 8), (1, 4, 5, 7), (1, 4, 5, 8), (1, 4, 6, 7),
 (1, 4, 6, 8), (2, 3, 5, 7), (2, 3, 5, 8), (2, 3, 6, 7), (2, 3, 6, 8), (2, 4, 5, 7), (2, 4, 5, 8),
 (2, 4, 6, 7), (2, 4, 6, 8)]

正常に動作していますね。最後に itertools の product() を簡単に説明します。

product(p, q, .., repeat = n)

repeat は繰り返しを指定します。たとえば、product(p, repeat = 2) は product(p, p) と同じです。

>>> for x in product([1,2]): print(x)
...
(1,)
(2,)
>>> for x in product([1,2], repeat = 2): print(x)
...
(1, 1)
(1, 2)
(2, 1)
(2, 2)
>>> for x in product([1,2], repeat = 3): print(x)
...
(1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 2, 2)
(2, 1, 1)
(2, 1, 2)
(2, 2, 1)
(2, 2, 2)

product(p, q, repeat = 2) は x = product(p, q); product(x, x) と同じです。

>>> for x in product([1,2], [3,4]): print(x)
...
(1, 3)
(1, 4)
(2, 3)
(2, 4)
>>> for x in product([1,2], [3,4], repeat = 2): print(x)
...
(1, 3, 1, 3)
(1, 3, 1, 4)
(1, 3, 2, 3)
(1, 3, 2, 4)
(1, 4, 1, 3)
(1, 4, 1, 4)
(1, 4, 2, 3)
(1, 4, 2, 4)
(2, 3, 1, 3)
(2, 3, 1, 4)
(2, 3, 2, 3)
(2, 3, 2, 4)
(2, 4, 1, 3)
(2, 4, 1, 4)
(2, 4, 2, 3)
(2, 4, 2, 4)

もちろん、product(p, q, r) のように 2 個以上の引数を指定することもできます。

>>> for x in product([1,2], [3,4], [5,6]): print(x)
...
(1, 3, 5)
(1, 3, 6)
(1, 4, 5)
(1, 4, 6)
(2, 3, 5)
(2, 3, 6)
(2, 4, 5)
(2, 4, 6)

●参考 URL

1. 直積集合 - Wikepedia

●グラフ

次は「グラフ (graph)」というデータ構造を取り上げます。一般にグラフというと、 円グラフや折れ線グラフといった図表を思い出す人が多いと思います。数学の「グラフ理論」では、いくつかの点とそれを結ぶ線でできた図形を「グラフ」といいます。次の図を見てください。

      図 1 : グラフの例

上図に示すように、グラフは点とそれを接続する線から構成されています。点のことを「頂点 (vertex)」や「節点 (node)」と呼び、線のことを「辺 (edge)」や「弧 (arc)」と呼びます。また、グラフには 2 種類あって、辺に向きの無いグラフを「無向グラフ」といい、辺に向きがあるグラフを「有向グラフ」といいます。有向グラフは一方通行の道と考えればいいでしょう。 次の図を見てください。

          図 2 : 有向グラフと無向グラフ

たとえば、上図の (1) では A 地点から B 地点へ行くことができますが、一方通行のため B 地点から A 地点に戻ることはできません。これが有効グラフです。(2) の無効グラフでは、A 地点から B 地点へ行くことができるし、逆に B 地点から A 地点に戻ることもできます。

データ間のさまざまな関係を表す場合、グラフはとても役に立ちます。たとえば、下図のように経路をグラフで表すことができます。

      図 3 : 経路図

上図ではアルファベットで頂点を表しています。この例では経路をグラフで表していますが、このほかにもいろいろな問題をグラフで表現することができます。

●隣接行列と隣接リスト

グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。上の経路図を隣接行列で表すと次のようになります。

   │A B C D E F G
 ─┼─────── 
  A│0 1 1 0 0 0 0
  B│1 0 1 1 0 0 0
  C│1 1 0 0 1 0 0
  D│0 1 0 0 1 1 0
  E│0 0 1 1 0 0 1
  F│0 0 0 1 0 0 0
  G│0 0 0 0 1 0 0

  図 4 : 隣接行列

A に接続している頂点は B と C なので、A 行の B と C に 1 をセットし、接続していない頂点には 0 をセットします。経路が一方通行ではない無向グラフの場合は、A 列の B と C にも 1 がセットされます。これを Python でプログラムすると、次のようになります。

リスト : 隣接行列

adjacent = ((0, 1, 1, 0, 0, 0, 0),   # A 
            (1, 0, 1, 1, 0, 0, 0),   # B
            (1, 1, 0, 0, 1, 0, 0),   # C
            (0, 1, 0, 0, 1, 1, 0),   # D
            (0, 0, 1, 1, 0, 0, 1),   # E
            (0, 0, 0, 1, 0, 0, 0),   # F
            (0, 0, 0, 0, 1, 0, 0))   # G

頂点 A から G を数値 0 から 6 に対応させるところがポイントです。隣接行列は 2 次元配列 (Python ではリストのリスト) で表します。このプログラムではタプルを使いました。内容は上図の隣接行列と同じです。

隣接行列の欠点は、辺の数が少ない場合でも N 行 N 列の行列が必要になることです。つまり、ほとんどの要素が 0 になってしまい、メモリを浪費してしまうのです。この欠点を補う方法に隣接リストがあります。これはつながっている頂点を格納する方法です。

 A => (B, C)
 B => (A, C, D) 
 C => (A, B, E)
 D => (B, E, F)
 E => (C, D, G)
 F => (D)
 G => (E)

 図 5 : 隣接リスト

これを Python でプログラムすると次のようになります。

リスト : 隣接リスト

adjacent = ((1, 2),    # A 
            (0, 2, 3), # B
            (0, 1, 4), # C
            (1, 4, 5), # D
            (2, 3, 6), # E
            (3,),      # F
            (1,))      # G

隣接行列と同様に、頂点 A から G を数値 0 から 6 に対応させます。Python の場合、要素が一つしかないタプルは、要素の後ろにカンマが必要になります。ご注意ください。

ところで、隣接リストにも欠点があります。たとえば、E と G が接続しているか調べるには、データを順番に調べていくしか方法がありません。このため、接続の判定に時間がかかることがあるのです。まあ、頂点に接続されている辺の数が少なければ、処理速度が極端に遅くなることはないでしょう。

●経路の探索

それでは簡単な例題として、地図上の A 地点から B 地点までの道順を求めるプログラムを作ってみましょう。「探索」にはいろいろな種類があります。たとえば、8 クイーン のようなパズルの解法も、あらゆる可能性の中から正解に行き着く手順を探すことですから、探索の一つと考えることができます。そして、探索でよく用いられる最も基本的な方法が「バックトラック (backtracking)」なのです。もちろん、経路の探索もバックトラックで解くことができます。

●バックトラックによる探索

経路図を再掲します。今回は隣接リストでグラフを表し、A から G までの経路を求めることにします。

      図 3 : 経路図

バックトラックを再帰呼び出しで実現する場合、経路を「進む」ことを再帰呼び出しに対応させるのがポイントです。たとえば、経路を探索する関数を search() としましょう。search() は引数として現在地点の頂点を受け取ることにします。最初は search(A) と呼び出します。A から B へ進むには search(B) と呼び出します。これで B へ進むことができます。

それでは、A に戻るにはどうしたらいいのでしょう。search(B) は search(A) から呼び出されたので、search(B) の実行を終了すれば、呼び出し元である search(A) に戻ることができます。つまり、関数の実行を終了すれば、一つ手前の地点にバックトラックできるのです。このように再帰呼び出しを使うと、進むことと戻ることを関数呼び出しで簡単に実現することができます。

それでは具体的に説明します。経路はリスト path に頂点を格納して表すことにします。経路の探索を行う関数 search() は、次のように定義します。

def search(goal, path):

search() の第 1 引数がゴール、第 2 引数が経路を表すリストです。リストの最後尾の要素が現在地点の頂点になります。search() は現在地点に隣接している頂点を一つ選び、経路を進めていきます。A から Gまでの経路を求めるには、次のように呼び出します。

  # A から G までの経路を求める
  search(6, [0])

search() は出発点 A をリストにセットし、A に接続されている頂点を選びます。隣接リストから順番に選ぶことにすると、次の頂点は B となります。B へ進むためには、次のように search() を再帰呼び出しします。

  # B へ進む時の再帰呼び出し
  search(6, [0, 1]);

この関数の実行を終了すると、呼び出し元の関数である頂点 A の処理に戻ります。プログラムは次のようになります。

リスト : 経路の探索

def search(goal, path):
    n = path[-1]
    if n == goal:
        print(path)
    else:
        for x in adjacent[n]:
            if x not in path:
                path.append(x)
                search(goal, path)
                path.pop()

search() を見てください。最初に path の最後尾の要素を取り出して変数 n にセットします。これが現在地点になります。そして、n がゴール地点 goal かチェックします。これが再帰呼び出しの停止条件になります。ゴールに到達したら print() で経路 path を表示します。

ここで探索を終了することもできますが、バックトラックすることで全ての経路を見つけることができます。パズルを解く場合、解の総数を求めることが多いので、全ての解をもれなく探索する必要があります。バックトラックを使えば、このような要求も満たすことができます。

ゴールしていない場合は、隣接リストから次の頂点を選びます。隣接リストから順番に頂点を取り出して、変数 x にセットします。このとき、経路に含まれている頂点を選んではいけません。そうしないと、同じ道をぐるぐると回る巡回経路が発生し、ゴールまでたどり着くことができなくなります。not in 演算子で path 内に頂点 x がないことを確認します。それから、append() で path に x を追加して search() を再帰呼び出しします。再帰呼び出しのあと、pop() で x を削除することをお忘れなく。

実行結果は次のようになります。

>>> search(6, [0])
[0, 1, 2, 4, 6]
[0, 1, 3, 4, 6]
[0, 2, 1, 3, 4, 6]
[0, 2, 4, 6]

4 通りの経路を見つけることができました。バックトラックによる探索は経路を先へ先へ進めるので、「縦形探索」とか「深さ優先探索 (depth first search)」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。最短経路を求めるのに適したアルゴリズムが「幅優先探索 (breadth first search)」です。

●幅優先探索

バックトラックによる探索は「深さ優先探索」や「縦形探索」とも呼ばれるように、一つの経路を先へ先へと進めていきます。このため最初に見つかる経路が最短経路であるとは限りません。幅優先探索は全ての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、同じ経路図を使って幅優先探索を具体的に説明しましょう。

幅優先探索の様子を下図に示します。

                  図 6 : 幅優先探索

まず、出発点 A から一つ進んだ経路 (2 節点) を全て求めます。この場合は、[A, B] と [A, C] の 2 つあり、これを全て記憶しておきます。次に、これらの経路から一つ進めた経路 (3 節点) を全て求めます。経路 [A, B] は [A, B, C] と [A, B, D] へ進めることができますね。ほかの経路 [A, C] も同様に進めて、全ての経路を記憶します。あとはこの作業をゴールに達するまで繰り返せばいいのです。

上図では、4 節点の経路 [A, C, E, G] でゴールに達していることがわかります。このように幅優先探索では、最初に見つかった経路が最短距離 (または最小手数) となるのです。この性質は、全ての経路を平行に進めていく探索順序から考えれば当然のことといえるでしょう。このことからバックトラックの縦形探索に対して、幅優先探索は「横形探索」と呼ばれます。このあとも探索を繰り返せば、すべての経路を求めることができます。

完成までの最小手数を求めるパズルを解く場合、幅優先探索を使ってみるといいでしょう。ただし、探索を進めるにしたがって、記憶しておかなければならないデータの総数が爆発的に増加する、つまりメモリを大量消費することに注意してください。

上図の場合ではメモリを大量消費することはありませんが、問題によってはマシンに搭載されているメモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがって、幅優先探索を使う場合は、メモリの消費量を抑える工夫も必要になります。

●経路の管理

経路の管理はキューを使うと簡単です。幅優先探索でのキューの動作を下図に示します。

          図 7 : 幅優先探索とキューの動作

最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [A] を一つ進めて、経路 [A, B] [A, C] を作り、それをキューに追加します。(3) では、経路 [A, B] を取り出して、一つ進めた経路 [A, B, C] と [A, B, D] をキューに追加します。

あとはキューに経路がある間、処理を繰り返せばいいわけです。キューは先入れ先出し (FIFO) の性質を持つデータ構造です。距離の短い経路から順番に処理されるため、幅優先探索として機能するわけです。

●プログラムの作成

それではプログラムを作りましょう。経路図は深さ優先探索と同じく隣接リスト (1) で表します。今回は簡単な例題ということで、キューはリストで表すことにします。キューにデータを追加する操作 (enqueue) は append() で、キューからデータを取り出す操作 (dequeue) は pop(0) で代用します。プログラムは次のようになります。

リスト : 幅優先探索

def bf_search(start, goal):
    q = [[start]]
    while len(q) > 0:
        # dequeu
        path = q.pop(0)
        n = path[-1]
        if n == goal:
            print(path)
        else:
            for x in adjacent[n]:
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    # enqueue
                    q.append(new_path)

最初にキュー q を初期化します。これはスタート地点の経路 [start] を追加するだけです。あとは、キューにデータがある間、経路を取り出して処理を行います。まず、pop(0) で先頭の経路を取り出して変数 path にセットします。次に、変数 n に現在地点をセットします。もし、n が goal と等しい場合は、print() で経路 path を表示します。

そうでなければ、経路を一つ進めます。この処理は深さ優先探索とほぼ同じです。ただし、新しい経路 new_path が必要になるので、path[:] で経路をコピーしていることに注意してください。それから、append() で new_path に x を追加して、それを q に追加します。これで全ての経路を求めることができます。

それでは、実際に実行してみましょう。

>>> bf_search(0, 6)
[0, 2, 4, 6]
[0, 1, 2, 4, 6]
[0, 1, 3, 4, 6]
[0, 2, 1, 3, 4, 6]

結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。当然ですが、経路の総数は 4 通りとなります。

●反復深化

幅優先探索は最短手数を求めるのに適したアルゴリズムですが、生成する局面数が多くなると大量のメモリを必要とします。このため、メモリが不足するときは、幅優先探索を使うことができません。深さ優先探索の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らないという問題点があります。

それでは、大量のメモリを使わずに最短手数を求める方法はないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。

たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように制限値を 1 手ずつ増やしていくわけです。このアルゴリズムを「反復深化 (iterative deeping)」といいます。

反復深化は最短手数を求めることができるアルゴリズムですが、幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。ただし、同じ探索を何度も繰り返すため実行時間が増大するという欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。

●反復深化のプログラム

それでは、同じ経路図を使って反復深化を具体的に説明しましょう。反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う関数を作り、上限値を１手ずつ増やしてその関数を呼び出せばいいのです。プログラムは次のようになります。

リスト : 反復深化

def id_search(limit, goal, path):
    n = len(path)
    m = path[-1]
    if n == limit:
        if m == goal: print(path)
    else:
        for x in adjacent[m]:
            if x not in path:
                path.append(x)
                id_search(limit, goal, path)
                path.pop()

# 実行
def test_ids(start, goal):
    for x in range(1, 8):
        print(x, 'moves')
        id_search(x, goal, [start])

関数 id_search() の引数 limit が上限値を表します。id_search() は limit まで深さ優先探索を行います。変数 n が経路の長さを表し、これが上限値 limit に達したら探索を打ち切ります。このとき、ゴールに到達したかチェックします。あとは、limit の値を増やしながら id_search() を呼び出せばいいわけです。それでは実行結果を示しましょう。

>>> test_ids(0, 6)
1 moves
2 moves
3 moves
4 moves
[0, 2, 4, 6]
5 moves
[0, 1, 2, 4, 6]
[0, 1, 3, 4, 6]
6 moves
[0, 2, 1, 3, 4, 6]
7 moves

結果を見ればおわかりのように、最初に見つかる解が最短手数になります。このプログラムでは全ての経路を求めましたが、最短手数を求めるだけでよい場合は、解が見つかった時点で探索を終了すればいいでしょう。

●プログラムリスト１

#
# set1.py : Set (linked list version)
#
#          Copyright (C) 2006-2022 Makoto Hiroi
#
class Set:
    class Cell:
        def __init__(self, x, next = None):
            self.item = x
            self.next = next
    
    def __init__(self, data = None):
        self.top = Set.Cell(None)   # Header Cell
        if data:
            for x in data:
                if not self.member(x):
                    self.top.next = Set.Cell(x, self.top.next)

    def member(self, x):
        cp = self.top.next
        while cp:
            if cp.item == x: return True
            cp = cp.next
        return False

    def issubset(self, x):
        cp = self.top.next
        while cp:
            if not x.member(cp.item): return False
            cp = cp.next
        return True

    def isequal(self, x):
        return self.issubset(x) and x.issubset(self)
    
    def insert(self, x):
        if not self.member(x):
            self.top.next = Set.Cell(x, self.top.next)

    def remove(self, x):
        def _remove(cp):
            if cp is None: return None
            elif cp.item == x: return cp.next
            else: return Set.Cell(cp.item, _remove(cp.next))

        self.top.next = _remove(self.top.next)

    def union(self, x):
        def _union(cp):
            if cp is None: return x.top.next
            elif x.member(cp.item):
                return _union(cp.next)
            else:
                return Set.Cell(cp.item, _union(cp.next))

        s = Set()
        s.top.next = _union(self.top.next)
        return s

    def intersection(self, x):
        def _intersection(cp):
            if cp is None: return None
            elif x.member(cp.item):
                return Set.Cell(cp.item, _intersection(cp.next))
            else:
                return _intersection(cp.next)

        s = Set()
        s.top.next = _intersection(self.top.next)
        return s

    def difference(self, x):
        def _difference(cp):
            if cp is None: return None
            elif x.member(cp.item):
                return _difference(cp.next)
            else:
                return Set.Cell(cp.item, _difference(cp.next))

        s = Set()
        s.top.next = _difference(self.top.next)
        return s

    def traverse(self):
        cp = self.top.next
        while cp:
            yield cp.item
            cp = cp.next
    
    def __len__(self):
        n = 0
        cp = self.top.next
        while cp:
            n += 1
            cp = cp.next
        return n
    
    def __str__(self):
        cp = self.top.next
        if cp is None: return 'Set([])'
        buff = 'Set(['
        while cp.next:
            buff += '{}, '.format(cp.item)
            cp = cp.next
        buff += '{})]'.format(cp.item)
        return buff

# test
if __name__ == '__main__':
    a = Set([1,2,3,4,5])
    b = Set([4,5,6,7,8])
    print(a)
    print(b)
    c = a.union(b)
    print(c)
    d = a.intersection(b)
    print(d)
    e = a.difference(b)
    print(e)
    print(a.issubset(c))
    print(c.issubset(a))
    print(a.isequal(a))
    a.insert(1)
    print(a)
    a.insert(10)
    print(a)
    b.remove(5)
    print(b)
    print(c)

●プログラムリスト２

#
# set2.py : Set (dictionary version)
#
#          Copyright (C) 2006-2022 Makoto Hiroi
#
class Set:
    def __init__(self, data = None):
        self.buff = {}
        if data:
            for x in data:
                if x not in self.buff: self.buff[x] = True

    def member(self, x): return x in self.buff

    def issubset(self, x):
        if len(self.buff) > len(x.buff): return False
        for y in self.buff:
            if not x.member(y): return False
        return True

    def isequal(self, x):
        return self.buff == x.buff

    def insert(self, x):
        if not self.member(x): self.buff[x] = True

    def remove(self, x):
        if x in self.buff: del self.buff[x]

    def union(self, x):
        s = Set(self.buff)
        for y in x.buff: s.insert(y)
        return s

    def intersection(self, x):
        s = Set()
        for y in self.buff:
            if y in x.buff: s.buff[y] = True
        return s

    def difference(self, x):
        s = Set()
        for y in self.buff:
            if y not in x.buff: s.buff[y] = True
        return s

    def traverse(self):
        for x in self.buff.keys():
            yield x

    def __len__(self): return len(self.buff)

    def __str__(self):
        return 'Set({})'.format(list(self.buff.keys()))

# test
if __name__ == '__main__':
    a = Set([1,2,3,4,5])
    b = Set([4,5,6,7,8])
    print(a)
    print(b)
    c = a.union(b)
    print(c)
    d = a.intersection(b)
    print(d)
    e = a.difference(b)
    print(e)
    print(a.issubset(c))
    print(c.issubset(a))
    print(a.isequal(a))
    a.insert(1)
    print(a)
    a.insert(10)
    print(a)
    b.remove(5)
    print(b)
    print(c)
    print(len(c))
    for x in c.traverse(): print(x)