アルゴリズム 幅優先探索をPythonで。

1．アルゴリズムとは

今回の説明においては、「解法」です。手順ややり方とも同義です。
例えば、5人の友達で10個あるビスケットを分けるとき、全員同じ数に分けるなら「10÷2」が解放です。

プログラムにおいては、プログラムが達成すべき目的(要件)を、「どう実現するか」が「解法」となります。

2．「幅優先探索」について

アルゴリズムの一つとして、幅優先探索という手法があります。

幅優先探索とは、グラフや木構造を探索するためのアルゴリズムの一つで、探索を開始する頂点から近い順に探索する方式。

例えば、以下のような迷路があったとします。スタートからゴールまで最短でたどり着くには何回移動が必要でしょうか。

今回は、これをPythonでプログラムを書いて解いてみたので、考え方やコードについて記載していきます。

3．迷路をPythonのプログラムで表現する

まずは、迷路を再現することが必要です。
壁・通路・スタート・ゴール・・・これらをどうプログラムで再現するか。

壁を■という文字、通路を0という数字、スタートはＳという文字で表現することとします。（やり方は人それぞれだと思うので、あくまで例です）

#迷路を多重リストで作成
line_1 = ['■','■','■','■','■','■','■','■','■','■']

line_2 = ['■', 0, '■', 0, 0, 0, 0, '■', 0, '■']
line_3 = ['■', 0, '■', 0, '■', 0, 0, 0, 0, '■']
line_4 = ['■', 0, 0, 0, '■', 0, '■', '■', 0, '■']
line_5 = ['■', '■', 0, '■', '■', 0, 0, 0, '■', '■']
line_6 = ['■', 0, 0, 0, '■', '■', '■', 0, '■', '■']
line_7 = ['■', 0, '■', 0, 0, 0, 0, 0, '■', '■']
line_8 = ['■', 0, 0, 0, '■', 0, '■', 0, 0, '■']
line_9 = ['■', 'S', 0, 0, 0, 0, 0, 0, 0, '■']

maze = [
	line_1, line_2, line_3, line_4, line_5, line_6,
	line_7, line_8, line_9, line_1
	]

print('***開始時***')

for rows in maze:
	for key,row in enumerate(rows):
		if key == 9:
			if row == '■':
				print('  ' + str(row),end = '\n'
			elif row == 'S':
			    print('  ' + str(row),end = '\n')
			elif row < 10:
				print(' ' + str(row),end = '\n')
			else:
				print(row, end = '\n')
		
		else:
			if row == '■':
				print(' ' + str(row),end = ',')
			elif row == 'S':
			    print('  ' + str(row),end = ',')
			elif row < 10:
				print('  ' + str(row),end = ',')
			else:
				print(' ' + str(row), end = ',')

print('************\n\n\n')

mazeというリスト型に、それぞれline1～line9までのリストを格納して多重しています。

なお、幅優先探索をする際に、リスト外を選択してエラー(index_error)にならないように、外周も壁にしています。
こんなイメージです。

なお、出力時にスペースをいれたりしているのは綺麗に縦列が並ぶようにです。僕はJupyter Notebookで作業しましたが、エディターによってはスペースの数の調整が必要かもしれません。

出力すると・・・

こんな感じです。これで迷路は再現できました。

4．迷路を探索する方法①（周囲を探索する関数）

どうやって迷路を探索して、ゴールまでの移動数を算出すればいいでしょうか。

これも、解き方は人それぞれでしょうが、以下のようにしました。

【前提】
・通路は0、壁は■
・移動可能なのは上下左右の4方向

【解き方】
①自分の位置の周囲4マスを取得する
➁4マスのうち、0のマス(通路)を移動数で更新していく
➂4マスのうち、0のマス(通路)を次の探索先として保存しておく
➃通路マスの更新、探索先の更新が一通り終わったら、移動数に1を加算
①～➃を通路マスがなくなるまで繰り返す

以上です。なお、僕が詰まったポイントは以下です。

次の探索先は複数ある。探索先をまたそれぞれ探索して、そこで取得した探索先を保存して・・・という部分がなかなか再現できず苦労しました。

まずは、周囲4マスを探索して、通路マスを確認する関数を作りました。

#四方のマスの値をリスト形式で取得し返す関数
def get_around(row, colomn):
	position_list = []
	position = maze[row][colomn]
	
	#四方の0のマスをposition_listに格納
	if maze[row - 1][colomn] == 0:
		position_list.append((row - 1, colomn))
	if maze[row][colomn - 1] == 0:
		position_list.append((row, colomn - 1))
	if maze[row][colomn + 1] == 0:
		position_list.append((row,colomn + 1))
	if maze[row + 1][colomn] == 0:
		position_list.append((row + 1,colomn))
		
	return position_list

多重リストは、リスト変数[外側リストのインデックス][内側リストのインデックス]で値を指定できます。

例えば、上のマスなら「一つ上の行の同列」、右のマスなら「同行の一つ右の列」のようになります。欲しいのは値じゃなく、その行数・列数になるので、行列をタプル形式でリストに追加していき、戻り値としてリストを返しています。

5．迷路を探索する方法➁（通路が残っているかチェックする関数）

もう一つ、ゴールに辿りつくまでは探索を続ける必要があります。
これは、mazeリストに0が残っているかチェックし、なければ「もう通路はないよ」とフラグに1をたてる行為が必要です。
（メインのループ処理の終了条件に利用）

そのための関数を作成しました。

#迷路から道(0)がなくなっていないかチェックする関数
def check_maze():
	flug = 0
	check_list = []
	for rows in maze:
		for row in rows:
			check_list.append(row)
			
	if 0 in check_list:
		flug = 0
	else:
		flug = 1
		
	return flug

やっていることとしては、一旦多重リストの値をすべてチェック用のリストに格納し、1個1個チェックしていき一つでも0があればflugは0を、なければ1を戻り値として返すという関数です。

6．迷路を探索する方法➂（一連の処理）

では、これまでに作った関数も組合せて一通り処理を書いていきます。

つまづいた、探索先が複数存在し、さらにその探索先に探索を行い、新たな探索先を保存する必要がある点については、探索先の座標(行・列）を2個用意しました。

では、先ほどの関数も交え全てのコードを記載します。

#迷路を多重リストで作成
line_1 = ['■','■','■','■','■','■','■','■','■','■']

line_2 = ['■', 0, '■', 0, 0, 0, 0, '■', 0, '■']
line_3 = ['■', 0, '■', 0, '■', 0, 0, 0, 0, '■']
line_4 = ['■', 0, 0, 0, '■', 0, '■', '■', 0, '■']
line_5 = ['■', '■', 0, '■', '■', 0, 0, 0, '■', '■']
line_6 = ['■', 0, 0, 0, '■', '■', '■', 0, '■', '■']
line_7 = ['■', 0, '■', 0, 0, 0, 0, 0, '■', '■']
line_8 = ['■', 0, 0, 0, '■', 0, '■', 0, 0, '■']
line_9 = ['■', 'S', 0, 0, 0, 0, 0, 0, 0, '■']

maze = [
	line_1, line_2, line_3, line_4, line_5, line_6,
	line_7, line_8, line_9, line_1
	]

print('***開始時***')

for rows in maze:
	for key,row in enumerate(rows):
		if key == 9:
			if row == '■':
				print('  ' + str(row),end = '\n')
			elif row == 'S':
			    print('  ' + str(row),end = '\n')
			elif row < 10:
				print(' ' + str(row),end = '\n')
			else:
				print(row, end = '\n')
		
		else:
			if row == '■':
				print(' ' + str(row),end = ',')
			elif row == 'S':
			    print('  ' + str(row),end = ',')
			elif row < 10:
				print('  ' + str(row),end = ',')
			else:
				print(' ' + str(row), end = ',')

print('************\n\n\n')
		
	

#四方のマスの値をリスト形式で取得し返す関数
def get_around(row, colomn):
	position_list = []
	position = maze[row][colomn]
	
	#四方の0のマスをposition_listに格納
	if maze[row - 1][colomn] == 0:
		position_list.append((row - 1, colomn))
	if maze[row][colomn - 1] == 0:
		position_list.append((row, colomn - 1))
	if maze[row][colomn + 1] == 0:
		position_list.append((row,colomn + 1))
	if maze[row + 1][colomn] == 0:
		position_list.append((row + 1,colomn))
		
	return position_list

#迷路から道(0)がなくなっていないかチェックする関数
def check_maze():
	flug = 0
	check_list = []
	for rows in maze:
		for row in rows:
			check_list.append(row)
			
	if 0 in check_list:
		flug = 0
	else:
		flug = 1
		
	return flug
	
#探索開始

#turn_num変数を1に設定	
turn_num = 1

#スタート位置を格納
target_area = [(8, 1)]
#四方探索結果を格納するリストを2個用意
position_list_1 = []
position_list_2 = []

#フラグを初期化
flug = 0

#フラグが0のかぎりループ処理
while flug == 0:
	
	if turn_num == 1:
		for position in target_area:
			target_area = get_around(position[0],position[1])
			position_list_1 = get_around(position[0],position[1])
		
		for target in target_area:
			maze[target[0]][target[1]] = turn_num
			
		target_area = []
		turn_num += 1
	
	elif turn_num % 2 == 0:
		for position in position_list_1:
			target_area+=get_around(position[0],position[1])
			position_list_2+=get_around(position[0],position[1])
			
			
		for target in target_area:
			maze[target[0]][target[1]] = turn_num
		
		target_area = []
		turn_num += 1
		position_list_1 = []
		
		flug = check_maze()

		
	elif turn_num % 2 == 1:
		
		for position in position_list_2:
			target_area+=get_around(position[0],position[1])
			position_list_1+=get_around(position[0],position[1])
			
		for target in target_area:
			maze[target[0]][target[1]] = turn_num
		
		target_area = []
		turn_num += 1
		position_list_2 = []
		
		flug = check_maze()

print('**探索終了時**')


for rows in maze:
	for key,row in enumerate(rows):
		if key == 9:
			if row == '■':
				print('  ' + str(row),end = '\n')
			elif row == 'S':
			    print('  ' + str(row),end = '\n')
			elif row < 10:
				print(' ' + str(row),end = '\n')
			else:
				print(row, end = '\n')
		
		else:
			if row == '■':
				print(' ' + str(row),end = ',')
			elif row == 'S':
			    print('  ' + str(row),end = ',')
			elif row < 10:
				print('  ' + str(row),end = ',')
			else:
				print(' ' + str(row), end = ',')

ポイントは以下です。

・初回は座標が一つ（スタート地点）
・探索先を格納するリストを2個用意
・探索回数が奇数・偶数かで、リストの使い分け・次の探索先のキープを実現

7.  探索結果

探索結果は以下となります。

最短、16回の移動で、ゴールにたどり着けることが分かりました。

8.  応用編（迷路もプログラムで自動作成）

迷路もプログラムを動かす度に、変わったら面白いですよね。
ということで、迷路を自動作成するプログラムも考えてみました。

#迷路を作成する関数
def make_maze():
   maze_parts = ['■', '■', 0, 0, 0, 0, 0, 0]

   maze = []

   line1 = ['■','■','■','■','■','■','■','■','■','■']

   maze.append(line1)
   
   for i in range(8):
       line = []
       if i < 7:
           for j in range(10):
               if j == 0 or j == 9:
                   line.append('■')
               else:
                   line.append(random.choice(maze_parts))
       else:
           for j in range(10):
               if j == 1:
                   line.append('S')
               elif j == 0 or j ==9:
                   line.append('■')
               else:
                   line.append(random.choice(maze_parts))
       
       maze.append(line)
   
   maze.append(line1)
   
   return maze

実行してみます。

maze = make_maze()

for rows in maze:
   for key,row in enumerate(rows):
       if key == 9:
           if row == '■':
               print('  ' + str(row),end = '\n')
           elif row == 'S':
               print('  ' + str(row),end = '\n')
           elif row < 10:
               print(' ' + str(row),end = '\n')
           else:
               print(row, end = '\n')
       else:
           if row == '■':
               print(' ' + str(row),end = ',')
           elif row == 'S':
               print('  ' + str(row),end = ',')
           elif row < 10:
               print('  ' + str(row),end = ',')
           else:
               print(' ' + str(row), end = ',')

実行結果

迷路が作成されました。

もう一度実行してみます。

違う迷路となりました！

ポイントは、2行目から8行目までは、0(通路）と■(壁）が格納されたパーツリストからランダムで値を抽出して、行を作成していってます。

その際、パーツリストに通路を多めにしておくことで、比較的ゴールまで辿りつけるよう、迷路が作成されるようにしています。

9. 自動作成迷路を探索する

では、自動作成迷路を探索してみます。
基本的には、さっきのコードとガッチャンコでいいのですが、、、
自動作成なので、ゴールにたどり着けないパターンや、立ち入れないマスが出てくる可能性があります。

そこで、check_maze関数を少し修正する必要があります。

#迷路から道(0)がなくなっていないかチェックする関数
def check_maze(position_list_1,position_list_2):
   flug = 0
   
   check_list = []
   for rows in maze:
       for row in rows:
           check_list.append(row)
   if 0 in check_list:
       flug = 0
   else:
       flug = 1
   
   if flug == 0:
       if position_list_1 == [] and position_list_2 == []:
           flug = 1
   return flug

追加したのは、後半部分。

たどり着けないマスがあると、迷路内に通路マスが残り、ループ処理が永遠に終わらない。そのため、「探索リストが2つとも空になってしまったらflugを1にする」ようにしています。

9.  応用編(自動作成迷路を探索する)

では、コード全文を書いて実行します。

from pprint import pprint
import random

#迷路を作成する関数
def make_maze():
   maze_parts = ['■', '■', 0, 0, 0, 0, 0, 0]

   maze = []

   line1 = ['■','■','■','■','■','■','■','■','■','■']

   maze.append(line1)
   
   for i in range(8):
       line = []
       if i < 7:
           for j in range(10):
               if j == 0 or j == 9:
                   line.append('■')
               else:
                   line.append(random.choice(maze_parts))
       else:
           for j in range(10):
               if j == 1:
                   line.append('S')
               elif j == 0 or j ==9:
                   line.append('■')
               else:
                   line.append(random.choice(maze_parts))
       
       maze.append(line)
   
   maze.append(line1)
   
   return maze


maze = make_maze()

print('***開始時***')

for rows in maze:
   for key,row in enumerate(rows):
       if key == 9:
           if row == '■':
               print('  ' + str(row),end = '\n')
           elif row == 'S':
               print('  ' + str(row),end = '\n')
           elif row < 10:
               print(' ' + str(row),end = '\n')
           else:
               print(row, end = '\n')
       else:
           if row == '■':
               print(' ' + str(row),end = ',')
           elif row == 'S':
               print('  ' + str(row),end = ',')
           elif row < 10:
               print('  ' + str(row),end = ',')
           else:
               print(' ' + str(row), end = ',')

print('************\n\n\n')

#四方のマスの値をリスト形式で取得し返す関数
def get_around(row, colomn):
   position_list = []
   position = maze[row][colomn]

   #四方の0のマスをposition_listに格納
   if maze[row - 1][colomn] == 0:
       position_list.append((row - 1, colomn))
   if maze[row][colomn - 1] == 0:
       position_list.append((row, colomn - 1))
   if maze[row][colomn + 1] == 0:
       position_list.append((row,colomn + 1))
   if maze[row + 1][colomn] == 0:
       position_list.append((row + 1,colomn))

   return position_list

#迷路から道(0)がなくなっていないかチェックする関数
def check_maze(position_list_1,position_list_2):
   flug = 0
   
   check_list = []
   for rows in maze:
       for row in rows:
           check_list.append(row)

   if 0 in check_list:
       flug = 0
   else:
       flug = 1

   if flug == 0:
       if position_list_1 == [] and position_list_2 == []:
           flug = 1

   return flug

#探索開始

#turn_num変数を1に設定	
turn_num = 1

#スタート位置を格納
target_area = [(8, 1)]
#四方探索結果を格納するリストを2個用意
position_list_1 = []
position_list_2 = []

#フラグを初期化
flug = 0
print(flug)

#フラグが0のかぎりループ処理
while flug == 0:

   if turn_num == 1:
       for position in target_area:
           target_area = get_around(position[0],position[1])
           position_list_1 = get_around(position[0],position[1])

       for target in target_area:
           maze[target[0]][target[1]] = turn_num

       target_area = []
       turn_num += 1
  

   elif turn_num % 2 == 0:
       for position in position_list_1:
           target_area+=get_around(position[0],position[1])
           position_list_2+=get_around(position[0],position[1])
       for target in target_area:
           maze[target[0]][target[1]] = turn_num

       target_area = []
       turn_num += 1
       position_list_1 = []

       flug = check_maze(position_list_1,position_list_2)

   elif turn_num % 2 == 1:
       for position in position_list_2:
           target_area+=get_around(position[0],position[1])
           position_list_1+=get_around(position[0],position[1])
       
       for target in target_area:
           maze[target[0]][target[1]] = turn_num

       target_area = []
       turn_num += 1
       position_list_2 = []

       flug = check_maze(position_list_1,position_list_2)

print('**探索終了時**')


for rows in maze:
   for key,row in enumerate(rows):
       if key == 9:
           if row == '■':
               print('  ' + str(row),end = '\n')
           elif row == 'S':
               print('  ' + str(row),end = '\n')
           elif row < 10:
               print(' ' + str(row),end = '\n')
           else:
               print(row, end = '\n')

       else:
           if row == '■':
               print(' ' + str(row),end = ',')
           elif row == 'S':
               print('  ' + str(row),end = ',')
           elif row < 10:
               print('  ' + str(row),end = ',')
           else:
               print(' ' + str(row), end = ',')

実行結果

1回目

2回目

はい、2回目は立ち入れないマスがありますが、ちゃんとゴールしてプログラムは終了しました。

読んでいただきありがとうございました！！