適切なハッシュ関数による幅優先探索の効率化

1. 初めに

探索とは、遷移可能な状態を通って、始状態から終状態へ至る経路を見つけることです。この際、ループに陥らないように、一度探索した状態は再度探索しないようにする必要があります。状態のハッシュ値を定義しておくと、２つの状態が同じかどうかはそれらのハッシュ値を比較することでわかるので、すでに探索したかどうかの判定を効率的に行うことができます。また、探索する系に応じて適切なハッシュ関数を定義しておくと　さらに効率よく探索を行うことができます。

ここでは、例として嫉妬深い夫の川渡り問題を考えます。川渡り問題とは、川岸にいる一団を特定の条件を満たしながら対岸に渡すパズルです。嫉妬深い夫の川渡り問題はそのバリエーションの１つです。

このパズルは以下の条件を満たしながら川岸にいる３組の夫婦全てを反対の岸に渡す手順を示す問題です。

川には１艘のボートがあり、２人まで乗ることができる。また、全ての人はボートを漕ぐことができる。
全ての場所 (両岸、ボート上) において女性は自分の夫がいないところで他の男と一緒にいることを禁止されている。 (つまり、ある場所にいる人全てが女性か、その場所にいる全ての女性が自分の夫と一緒にいる必要がある。)

この問題を解く上で、３組の夫婦を入れ替えても渡る手順には影響がありません。（たとえば、夫婦 A,B,C がいたとして、A の妻と B の妻がいる状態は B の妻と C の妻がいる状態と同じだとみなせます。）従って、この問題を解く上で、川のそれぞれの場所 (両岸とボート) で、合計人数、男性(もしくは女性)の人数、組になっている夫婦の数が同じで、かつボートの位置が同じであれば川は同じ状態であるとみなすことができます。川の状態をこのように定義し、以前探索したのと同じ状態になる場合には探索を打ち切るようにすると探索の範囲を狭めることができ、効率的に解くことができます。

具体的には以下のようにして幅優先探索で問題を解いていきます。

探索した経路を川の状態のリストとして保持する。経路はキューに保持する。
キューから最初の要素を取り出し、制約を満たし、まだ探索していない次の状態を算出する。
次の状態が終了条件を満たせば、そこにいたるまでの経路を出力して終了する。
そうでない場合は、次の状態を経路の末尾に加えて新しい経路とし、それをキューに加える。

2. プログラムのソースコードと実行結果

2.1. ソースコード

川の状態はそれぞれの場所 (両岸及びボート) で、男女合計人数、女性の人数、夫婦の組の数及びボートの位置が等しいときは同じだとします。そのためには、川及びそれぞれの場所のハッシュ値がこれらの数だけで決まるようにします。

人、場所、川を表すクラスとして、 Person, Plase, River の３つのクラスを定義し、それぞれのハッシュ値を定義します。

Person のハッシュ値は (Couple No.) * 2 + (性別: 男 1, 女 0) で定義します。(line 29--30)
Plase のハッシュ値は、(ペアの数)*8**2 + (女性の数)*8 + (人数) で定義します。(line 80--81)
River のハッシュ値は (ボートの位置: 左岸 1, 右岸 0) * 512**3 + (ボートのハッシュ値) * 512**2 + (左岸のハッシュ値) * 512 + (右岸のハッシュ値) で定義します。(line 112--113)

set や frozenset の要素にはハッシュ値が定義されている必要があるので、 Person や River のハッシュ値も定義する必要があります。 Person は Plase (frozenset) の要素であり、また、一度通った状態を探索するのを避けるため、訪れた River の set を定義します。

Plase の和や差を簡単に定義できるように、Plase は froznset の派生クラスとして定義します。

夫婦の数やボートの定員を変えられるようにしています。コマンドラインから

python rivercross.py [n_couple] [boat_size]

とすると、夫婦の数が n_couple, ボートの定員が boat_size の川渡り問題になります。

コードを以下に示します。

[rivercross.py]

001:   #! python
002:   
003:   ''' River Crossing'''
004:   
005:   import sys, time
006:   from math import floor, log
007:   from copy import copy
008:   from functools import reduce
009:   from queue import Queue
010:   from itertools import combinations_with_replacement
011:   
012:   
013:   
014:   BOAT_SIZE = 2
015:   N_OF_COUPLE = 3
016:   N_SHIFT =3
017:   
018:   
019:   class Person:
020:       '''People crossing river:
021:       Couple No = {1,2,3}
022:       isBoy = True or False
023:       '''
024:       
025:       def __init__(self, couple_no, gender):
026:           self.no = couple_no
027:           self.isboy = gender=='boy'
028:   
029:       def __hash__(self):
030:           return self.no * 2 + self.isboy
031:   
032:       def is_girl(self):
033:           return not self.isboy
034:   
035:       def is_paired(self, ls):
036:           '''if there is a partner for the self in ls'''
037:           return any(self.no == other.no and self.isboy ^ other.isboy for other in ls)
038:   
039:       def __str__(self):
040:           return ('B' if self.isboy else 'G')  + str(self.no)
041:   
042:   
043:   
044:   
045:   class Place (frozenset):
046:       '''Representing river sides and boat.
047:       The state of the place is determined by the number of all people, girls, and couples.'''
048:   
049:       def __init__(self, s=[]):
050:          frozenset.__init__(self,s)
051:   
052:       def __eq__(self, other):
053:           return  hash(self) == hash(other)
054:   
055:       def n_girls(self):
056:           return len( [ x for x in self if x.is_girl() ] )
057:   
058:       def n_couples(self):
059:           return len( [ x for x in self if x.is_girl() and x.is_paired(self) ] )
060:   
061:       def all_girl(self):
062:           return all( x.is_girl() for x in self )
063:   
064:       def all_girls_paired(self):
065:           ls_g = [ x for x in self if x.is_girl() ]
066:           return all( x.is_paired(self) for x in ls_g)
067:   
068:       def is_safe(self):
069:           return self.all_girl() or self.all_girls_paired()
070:      
071:       def __str__(self):
072:          return '{' + ', '.join( str(x) for x in self ) + '}'
073:   
074:       def __add__(self, other):
075:           return Place(frozenset.__or__(self, other))
076:   
077:       def __sub__(self, other):
078:           return Place(frozenset.__sub__(self, other))
079:   
080:       def __hash__(self):
081:           return shift_add(N_SHIFT, self.n_couples(), self.n_girls(), len(self))
082:   
083:   
084:   
085:   
086:   class River:
087:       '''River consists of the left side, the right side, a boat, and the boat position'''
088:       
089:       def __init__(self, lhs, rhs=Place(), boat=Place(), boat_is_left=True):
090:           self.lhs = lhs
091:           self.rhs = rhs
092:           self.boat = boat
093:           self.boat_is_left=boat_is_left
094:   
095:       def __str__(self):
096:           return str(self.lhs) +  \
097:                   '   ' * (not self.boat_is_left) + \
098:                   str(self.boat) + \
099:                  '   ' * self.boat_is_left + \
100:                  str(self.rhs)
101:   
102:       def is_safe(self):
103:           return self.lhs.is_safe() and self.rhs.is_safe() and self.boat.is_safe() and \
104:                  ( (self.lhs + self.boat).is_safe()  if self.boat_is_left else (self.rhs + self.boat).is_safe() )
105:   
106:       def __eq__(self, other):
107:           return hash(self)==hash(other)
108:   
109:       def is_finish(self):
110:           return not self.lhs
111:   
112:       def __hash__(self):
113:           return shift_add(N_SHIFT*3, self.boat_is_left, self.boat, self.lhs, self.rhs)
114:   
115:       def proceed(self, visited):
116:           if self.boat_is_left:
117:               tmp = self.lhs + self.boat
118:               s= { River(tmp - boat, self.rhs, boat, not self.boat_is_left) for boat in onboat(tmp, BOAT_SIZE) }
119:           else:
120:               tmp = self.rhs + self.boat
121:               s= { River(self.lhs , tmp - boat , boat, not self.boat_is_left) for boat in onboat(tmp, BOAT_SIZE) }
122:   
123:           return { r for r in s if r.is_safe() and r not in visited }
124:   
125:   
126:   
127:   
128:   def shift_add(n_shift, *ls):
129:       return reduce(lambda x,y: (x<<n_shift) + (y if isinstance(y, int) else hash(y)), ls, 0)
130:   
131:   
132:   def onboat(p, n):
133:       ''' select upto n from p '''
134:       return  ( Place(c) for c in combinations_with_replacement(p, n) )
135:   
136:   
137:   def cons(x, ls):
138:       ls1=copy(ls)
139:       ls1.append(x)
140:       return ls1
141:   
142:   
143:   def print_path(ls):
144:       '''print path'''
145:       print('\nResult:\nStep\t{Left Side} {Boat} {Right Side}')
146:       for i, x in enumerate(ls):
147:           print ('[{0:2d}]\t{1}'.format(i,x))
148:   
149:   
150:   def river_cross(p0):
151:       visited={p0}
152:       q = Queue()
153:       q.put([p0])
154:       while not q.empty():
155:           #print(q.qsize())
156:           path = q.get()
157:           now = path[-1]
158:           for _next in now.proceed(visited):
159:               path1= cons(_next, path)
160:               if _next.is_finish():
161:                   print_path(path1)
162:                   return
163:               else:
164:                   q.put(path1)
165:                   visited.add(_next)
166:   
167:   
168:   
169:   
170:   if __name__=='__main__':
171:       if len(sys.argv)==3 and sys.argv[1].isdigit() and sys.argv[2].isdigit():
172:           N_OF_COUPLE = int(sys.argv[1])
173:           BOAT_SIZE = int(sys.argv[2])
174:           N_SHIFT = floor(log(N_OF_COUPLE*2, 2))+1
175:       t0 = time.time()
176:       river_cross(  River( Place(                                                  \
177:          [ Person(i, gdr) for i in range(N_OF_COUPLE) for gdr in ('boy', 'girl') ]
178:       )))
179:       t1=time.time()
180:       print('\n{:3.3f} sec'.format(t1-t0))

2.2. 実行結果

次のようになります。

155 行目のコメントをはずしてキューの長さを出力させてみると、常に 5 以下で、無駄な探索はほとんどしていないことがわかります。

Z:\doc\monthly\12-03>d:\python32\python.exe rivercross.py

Result:
Step    {Left Side} {Boat} {Right Side}
[ 0]    {G0, B0, G1, B1, G2, B2}{}   {}
[ 1]    {G1, B1, G2, B2}   {G0, B0}{}
[ 2]    {G1, B1, G2, B2}{B0}   {G0}
[ 3]    {B0, B1, B2}   {G1, G2}{G0}
[ 4]    {B0, B1, B2}{G0}   {G1, G2}
[ 5]    {G0, B0}   {B1, B2}{G1, G2}
[ 6]    {G0, B0}{G1, B1}   {G2, B2}
[ 7]    {G0, G1}   {B0, B1}{G2, B2}
[ 8]    {G0, G1}{G2}   {B0, B1, B2}
[ 9]    {G2}   {G0, G1}{B0, B1, B2}
[10]    {G2}{B2}   {G0, B0, G1, B1}
[11]    {}   {G2, B2}{G0, B0, G1, B1}

0.063 sec

Z:\doc\monthly\12-03>

3. 通常のハッシュ関数との比較

通常のハッシュ関数を用いた幅優先探索のコードを下に示します。ハッシュ関数に出来合いのものを使ったほかは全く同じです。

[rivercross_typical.py]

001:   #! python
002:   
003:   ''' River Crossing'''
004:   
005:   import sys, time
006:   from copy import copy
007:   from queue import Queue
008:   from itertools import combinations_with_replacement
009:   
010:   
011:   
012:   BOAT_SIZE = 2
013:   N_OF_COUPLE = 3
014:   
015:   
016:   class Person:
017:       '''People crossing river:
018:       Couple No = {1,2,3}
019:       isBoy = True or False
020:       '''
021:       
022:       def __init__(self, couple_no, gender):
023:           self.no = couple_no
024:           self.isboy = gender=='boy'
025:   
026:       def __hash__(self):
027:           return self.no * 2 + self.isboy
028:   
029:       def is_girl(self):
030:           return not self.isboy
031:   
032:       def is_paired(self, ls):
033:           '''if there is a partner for the self in ls'''
034:           return any(self.no == other.no and self.isboy ^ other.isboy for other in ls)
035:   
036:       def __str__(self):
037:           return ('B' if self.isboy else 'G')  + str(self.no)
038:   
039:   
040:   
041:   
042:   class Place (frozenset):
043:       '''Representing river sides and boat.
044:       The state of the place is determined by a conventional hash function.'''
045:   
046:       def __init__(self, s=[]):
047:          frozenset.__init__(self,s)
048:   
049:       def __eq__(self, other):
050:           return  hash(self) == hash(other)
051:   
052:       def all_girl(self):
053:           return all( x.is_girl() for x in self )
054:   
055:       def all_girls_paired(self):
056:           ls_g = [ x for x in self if x.is_girl() ]
057:           return all( x.is_paired(self) for x in ls_g)
058:   
059:       def is_safe(self):
060:           return self.all_girl() or self.all_girls_paired()
061:      
062:       def __str__(self):
063:          return '{' + ', '.join( str(x) for x in self ) + '}'
064:   
065:       def __add__(self, other):
066:           return Place(frozenset.__or__(self, other))
067:   
068:       def __sub__(self, other):
069:           return Place(frozenset.__sub__(self, other))
070:   
071:       def __hash__(self):
072:           return frozenset.__hash__(self)
073:   
074:   
075:   
076:   
077:   class River:
078:       '''River consists of the left side, the right side, a boat, and the boat position'''
079:       
080:       def __init__(self, lhs, rhs=Place(), boat=Place(), boat_is_left=True):
081:           self.lhs = lhs
082:           self.rhs = rhs
083:           self.boat = boat
084:           self.boat_is_left=boat_is_left
085:   
086:       def __str__(self):
087:           return str(self.lhs) +  \
088:                   '   ' * (not self.boat_is_left) + \
089:                   str(self.boat) + \
090:                  '   ' * self.boat_is_left + \
091:                  str(self.rhs)
092:   
093:       def is_safe(self):
094:           return self.lhs.is_safe() and self.rhs.is_safe() and self.boat.is_safe() and \
095:                  ( (self.lhs + self.boat).is_safe()  if self.boat_is_left else (self.rhs + self.boat).is_safe() )
096:   
097:       def __eq__(self, other):
098:           return hash(self)==hash(other)
099:   
100:       def is_finish(self):
101:           return not self.lhs
102:   
103:       def __hash__(self):
104:           return hash( ( self.boat_is_left, self.boat, self.lhs, self.rhs) )
105:   
106:       def proceed(self, visited):
107:           if self.boat_is_left:
108:               tmp = self.lhs + self.boat
109:               s= { River(tmp - boat, self.rhs, boat, not self.boat_is_left) for boat in onboat(tmp, BOAT_SIZE) }
110:           else:
111:               tmp = self.rhs + self.boat
112:               s= { River(self.lhs , tmp - boat , boat, not self.boat_is_left) for boat in onboat(tmp, BOAT_SIZE) }
113:   
114:           return { r for r in s if r.is_safe() and r not in visited }
115:   
116:   
117:   
118:   
119:   def onboat(p, n):
120:       ''' select upto n from p '''
121:       return  ( Place(c) for c in combinations_with_replacement(p, n) )
122:   
123:   
124:   def cons(x, ls):
125:       ls1=copy(ls)
126:       ls1.append(x)
127:       return ls1
128:   
129:   
130:   def print_path(ls):
131:       '''print path'''
132:       print('\nResult:\nStep\t{Left Side} {Boat} {Right Side}')
133:       for i, x in enumerate(ls):
134:           print ('[{0:2d}]\t{1}'.format(i,x))
135:   
136:   
137:   def river_cross(p0):
138:       visited={p0}
139:       q = Queue()
140:       q.put([p0])
141:       while not q.empty():
142:           #print(q.qsize())
143:           path = q.get()
144:           now = path[-1]
145:           for _next in now.proceed(visited):
146:               path1= cons(_next, path)
147:               if _next.is_finish():
148:                   print_path(path1)
149:                   return
150:               else:
151:                   q.put(path1)
152:                   visited.add(_next)
153:   
154:   
155:   
156:   
157:   if __name__=='__main__':
158:       if len(sys.argv)==3 and sys.argv[1].isdigit() and sys.argv[2].isdigit():
159:           N_OF_COUPLE = int(sys.argv[1])
160:           BOAT_SIZE = int(sys.argv[2])
161:   
162:       t0=time.time()
163:       river_cross(  River( Place(                                                  \
164:          [ Person(i, gdr) for i in range(N_OF_COUPLE) for gdr in ('boy', 'girl') ]
165:       )))
166:       t1=time.time()
167:       print('\n{:3.3f} sec'.format(t1-t0))

3 組の夫婦の時は実行速度にほとんど差が見られませんが、夫婦の数を増やすと実行時間に差が見られるようになります。下に示すように、7 組の夫婦の場合は、ハッシュ関数を工夫したものでは 25 秒で終了したのに対し、通常のハッシュ関数を使ったものでは 411 秒かかっています。夫婦の数が増えると、ボートの定員を増やさないと川を渡れないので、定員は 4 人にしています。
実行環境は、OS: Windows XP, CPU: AMD Duron 1800 MHz, RAM: 1GB です。

Z:\doc\monthly\12-03>d:\python32\python.exe rivercross.py 7 4

Result:
Step    {Left Side} {Boat} {Right Side}
[ 0]    {G0, B0, G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6}{}   {}
[ 1]    {B0, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6}   {G0, G1}{}
[ 2]    {B0, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6}{G0}   {G1}
[ 3]    {B0, B1, B2, B3, B4, G5, B5, G6, B6}   {G0, G4, G2, G3}{G1}
[ 4]    {B0, B1, B2, B3, B4, G5, B5, G6, B6}{G0}   {G4, G1, G2, G3}
[ 5]    {G0, B0, G5, B5, G6, B6}   {B4, B1, B2, B3}{G4, G1, G2, G3}
[ 6]    {G0, B0, G5, B5, G6, B6}{G1, B1}   {G2, B2, G3, B3, G4, B4}
[ 7]    {G5, B5, G6, B6}   {G0, B0, G1, B1}{G2, B2, G3, B3, G4, B4}
[ 8]    {G5, B5, G6, B6}{G0, B0}   {G1, B1, G2, B2, G3, B3, G4, B4}
[ 9]    {G0, G5, G6}   {B0, B5, B6}{G1, B1, G2, B2, G3, B3, G4, B4}
[10]    {G0, G5, G6}{G1}   {B0, B1, G2, B2, G3, B3, G4, B4, B5, B6}
[11]    {}   {G0, G5, G6, G1}{B0, B1, G2, B2, G3, B3, G4, B4, B5, B6}

24.969 sec

Z:\doc\monthly\12-03>d:\python32\python.exe rivercross_typical.py 7 4

Result:
Step    {Left Side} {Boat} {Right Side}
[ 0]    {G0, B0, G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6}{}   {}
[ 1]    {G1, B1, G2, B2, G3, B3, G4, B4, G6, B6}   {G0, B0, G5, B5}{}
[ 2]    {G1, B1, G2, B2, G3, B3, G4, B4, G6, B6}{B0, B5}   {G0, G5}
[ 3]    {B0, B1, B2, G3, B3, B4, B5, B6}   {G4, G6, G1, G2}{G0, G5}
[ 4]    {B0, B1, B2, G3, B3, B4, B5, B6}{G5, G6}   {G0, G4, G1, G2}
[ 5]    {G3, B3, G5, B5, G6, B6}   {B0, B1, B2, B4}{G0, G4, G1, G2}
[ 6]    {G3, B3, G5, B5, G6, B6}{G1, B1}   {G0, B0, G2, B2, G4, B4}
[ 7]    {G1, B1, G6, B6}   {G5, B5, G3, B3}{G0, B0, G2, B2, G4, B4}
[ 8]    {G1, B1, G6, B6}{G0, B0}   {G2, B2, G3, B3, G4, B4, G5, B5}
[ 9]    {G1, B1}   {G0, B0, G6, B6}{G2, B2, G3, B3, G4, B4, G5, B5}
[10]    {G1, B1}{G3, B3}   {G0, B0, G2, B2, G4, B4, G5, B5, G6, B6}
[11]    {}   {G1, B1, G3, B3}{G0, B0, G2, B2, G4, B4, G5, B5, G6, B6}

410.719 sec

Z:\doc\monthly\12-03>

ハッシュ関数を工夫したものは探索効率がいいので、夫婦の数をさらに増やすこともできます。夫婦の数を 11 組まで増やして試したところ、4 人乗りのボートで 19 ステップで渡れることがわかります。

下の結果を見てみると、4 人乗りボートを使えば、夫婦の数がどれだけ多くても川を渡れることがわかります。

Z:\doc\monthly\12-03>d:\python32\python.exe rivercross.py 11 4

Result:
Step    {Left Side} {Boat} {Right Side}
[ 0]    {G0, B0, G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}{}   {}
[ 1]    {B0, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}   {G0, G1}{}
[ 2]    {B0, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}{G0}   {G1}
[ 3]    {B0, B1, B2, B3, B4, G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10} {G0, G4, G2, G3}{G1}
[ 4]    {B0, B1, B2, B3, B4, G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}{G0}   {G4, G1, G2, G3}
[ 5]    {G0, B0, G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}   {B4, B1, B2, B3}{G4, G1, G2, G3}
[ 6]    {G0, B0, G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}{G1, B1}   {G2, B2, G3, B3, G4, B4}
[ 7]    {G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}   {G0, B0, G1, B1}{G2, B2, G3, B3, G4, B4}
[ 8]    {G5, B5, G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}{G0, B0}   {G1, B1, G2, B2, G3, B3, G4, B4}
[ 9]    {G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}   {G0, B0, G5, B5}{G1, B1, G2, B2, G3, B3, G4, B4}
[10]    {G6, B6, G7, B7, G8, B8, G9, B9, G10, B10}{G0, B0}   {G1, B1, G2, B2, G3, B3, G4, B4, G5, B5}
[11]    {G7, B7, G8, B8, G9, B9, G10, B10}   {G0, B0, G6, B6}{G1, B1, G2, B2, G3, B3, G4, B4, G5, B5}
[12]    {G7, B7, G8, B8, G9, B9, G10, B10}{G0, B0}   {G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6}
[13]    {G8, B8, G9, B9, G10, B10}   {G0, B0, G7, B7}{G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6}
[14]    {G8, B8, G9, B9, G10, B10}{G0, B0}   {G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6, G7, B7}
[15]    {G9, B9, G10, B10}   {G0, B0, G8, B8}{G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6, G7, B7}
[16]    {G9, B9, G10, B10}{G0, B0}   {G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6, G7, B7, G8, B8}
[17]    {G9, G10}   {G0, B0, B9, B10}{G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6, G7, B7, G8, B8}
[18]    {G9, G10}{G0}   {B0, G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6, G7, B7, G8, B8, B9, B10}
[19]    {}   {G0, G9, G10}{B0, G1, B1, G2, B2, G3, B3, G4, B4, G5, B5, G6, B6,7, B7, G8, B8, B9, B10}

300.329 sec

Z:\doc\monthly\12-03>

5. 終わりに

実行速度に難のある幅優先探索ですが、ハッシュ関数を工夫すると、幅優先探索の効率が著しく向上することがわかります。複雑な系を探索する場合には、その系の特徴をハッシュ関数に盛り込むことによって効率的に探索を行える場合があります。

ソースコードはここからダウンロードできます。

ここで掲載したスクリプトは Python 3.2 で動作を確認しています。 Python 2.x では動かないのでご注意ください。