BFS解Nデジタル(python)
18242 ワード
pythonで簡単な文法の問題を書き、アルゴリズムに集中する.
[1]その他の要点はA*アルゴリズムと同様であるが、8デジタルのバージョンを解くには従来のBFSを用いる、16デジタルを解くには大きすぎるため、dictを用いてhashを調べる.またここでは,コントロ展開による圧縮状態である.
ここでは16デジタルを解くコードであり、8デジタルに比べていくつかの改良がなされている.まず1行のコードは0からNの階乗のlistを書くことができて、このように私達はNの大きさを修正する時Nを修正するだけでいいです.そして、この状態の価値を測定し、キューに挿入する方法を採用しました.しかしこの時点でA*アルゴリズムの実装の詳細はまだ見ていないので、簡単にキューを挿入するだけですが、直接のBFSよりはかなり速いです.(もちろん必ずしも最適とは限らない)
[1]その他の要点はA*アルゴリズムと同様であるが、8デジタルのバージョンを解くには従来のBFSを用いる、16デジタルを解くには大きすぎるため、dictを用いてhashを調べる.またここでは,コントロ展開による圧縮状態である.
import os
import time
N = 9
T = [1,2,3,4,5,6,7,8,0]#the original state
obj = [2,4,3,1,6,0,7,5,8]#the final state
factory = [1, 1, 2, 6, 24, 120,720, 5040,40320]
def formed_print(L):
n = 0;
for i in range(0,7,3):
t = L[i:i+3]
print(t[0],t[1],t[2])
print('
')
def get_state(node):
used,sum = [0]*9,0
for pos,i in enumerate(node):
num = 0
used[i] = 1
for k in range(0,i):
if(used[k]==0):num += 1
sum += num*factory[8-pos]
return sum
def find_next_nodes(curr_node):
def swap(L,i,j):#return a list with swapped items
temp = L[::]
temp[i],temp[j] = temp[j],temp[i]
return temp
pos = curr_node.index(0)#find the position of 0
i,j = pos//3,pos%3#convert pos to grid coordinates
nextnodes = []
if(i!=2):nextnodes.append(swap(curr_node,pos,pos+3))
if(i!=0):nextnodes.append(swap(curr_node,pos,pos-3))
if(j!=2):nextnodes.append(swap(curr_node,pos,pos+1))
if(j!=0):nextnodes.append(swap(curr_node,pos,pos-1))
return pos,nextnodes
def bfs():
path = [[] for i in range(362880)]
iscompleted = False
openlist = []#the statelist
visit = [0]*362880
openlist.append(T)#add the first node
visit[get_state(T)] = 1
path[get_state(T)] = [-1,0]
count = 100000;
while(len(openlist)!=0 and count>0):#if the open list is empty,loop ends
count -= 1
curr_node = openlist[0]
state = get_state(curr_node)
openlist.remove(curr_node)
if(curr_node == obj):#if the obj is found,break the loop
iscompleted = True;
return path,curr_node.index(0),state
break;
zero_pos,nextnodes = find_next_nodes(curr_node)#return all nodes near to 0 and pos of 0
for node in nextnodes:
next_state = get_state(node)
if(visit[next_state]==0):#ensure the node is not visited
openlist.append(node)
visit[next_state] = 1
path[next_state] = [state,zero_pos]#record the state path and the solution
#print(path[next_state])
return False
def move(path,zero_pos,state):
zero_list = [zero_pos]
while(path[state][0]!=-1):
zero_list = [path[state][1]]+zero_list
state = path[state][0]
for i in range(len(zero_list)-1):
os.system('cls')
formed_print(T)
time.sleep(0.5)
T[zero_list[i]],T[zero_list[i+1]] = T[zero_list[i+1]],T[zero_list[i]]
os.system('cls')
formed_print(T)
path,zero_pos,state = bfs()
move(path,zero_pos,state)
ここでは16デジタルを解くコードであり、8デジタルに比べていくつかの改良がなされている.まず1行のコードは0からNの階乗のlistを書くことができて、このように私達はNの大きさを修正する時Nを修正するだけでいいです.そして、この状態の価値を測定し、キューに挿入する方法を採用しました.しかしこの時点でA*アルゴリズムの実装の詳細はまだ見ていないので、簡単にキューを挿入するだけですが、直接のBFSよりはかなり速いです.(もちろん必ずしも最適とは限らない)
import os
import time
from functools import reduce
N = 16
T = [4,7,8,3,6,13,15,2,1,11,5,12,0,14,10,9]
#obj = [4,7,8,3,1,6,15,2,13,0,5,12,14,11,10,9]#2
#obj = [1,2,4,3,7,8,0,12,13,6,5,15,14,11,10,9] #25s
#obj = [1,2,0,3,7,8,4,12,13,6,5,15,14,11,10,9]#29
#obj = [1,2,3,12,7,8,15,0,13,6,4,5,14,11,10,9] #34#
#obj = [1,2,15,3,7,8,4,12,13,6,0,5,14,11,10,9] #39
#obj = [1,2,3,4,7,8,15,12,13,6,5,0,14,11,10,9] #45
#obj = [1,2,3,4,7,8,15,0,13,6,5,12,14,11,10,9] #47
#obj = [1,2,3,4,7,8,0,15,13,6,5,12,14,11,10,9]#48
#obj = [1,2,3,4,7,8,5,15,13,6,0,12,14,11,10,9]#49
#obj =[1,2,3,4,7,8,5,15,13,6,12,0,14,11,10,9] #50
obj = [1,2,3,4,5,13,6,15,14,7,11,10,0,9,8,12]#59
#obj = [1,2,3,4,5,13,6,15,14,11,0,10,9,7,8,12]#the final state
factory = list(map(lambda x:reduce(lambda f,n:f*n,range(1,x+1),1),range(8)))##
def formed_print(L):
n = 0;
for i in range(0,13,4):
t = L[i:i+4]
print(t[0],t[1],t[2],t[3])
print('
')
def displacement(lhs,rhs):#compare the displacement
count = 0
for i in range(len(lhs)):
if(lhs[i]!=rhs[i]): count += 1
return count
def get_state(node):
#used,sum = [0]*N,0
#for i in node:
#num = 0
#used[i] = 1
#for k in range(0,i):
#if(used[k]==0):num += 1
#sum += num*factory[N-i-1]
sum = ''
for i in node:
sum += str(i)
return sum
def find_next_nodes(curr_node):
def swap(L,i,j):#return a list with swapped items
temp = L[::]
temp[i],temp[j] = temp[j],temp[i]
return temp
pos = curr_node.index(0)#find the position of 0
i,j = pos//4,pos%4#convert pos to grid coordinates
nextnodes = []
if(i!=3):nextnodes.append(swap(curr_node,pos,pos+4))
if(i!=0):nextnodes.append(swap(curr_node,pos,pos-4))
if(j!=3):nextnodes.append(swap(curr_node,pos,pos+1))
if(j!=0):nextnodes.append(swap(curr_node,pos,pos-1))
return pos,nextnodes
def bfs():
path = {}
iscompleted = False
openlist = []#the statelist
openlist.append(T)#add the first node
visit = {}#use visit to indicate being visited
visit[get_state(T)] = 1;
print(visit)
path[get_state(T)] = [-1,0]
while(len(openlist)!=0):#if the open list is empty,loop ends
curr_node = openlist[0]
state = get_state(curr_node)
openlist.remove(curr_node)
if(curr_node == obj):#if the obj is found,break the loop
iscompleted = True;
return path,curr_node,curr_node.index(0),state
break;
zero_pos,nextnodes = find_next_nodes(curr_node)#return all nodes near to 0 and pos of 0
for node in nextnodes:
if(node == obj):formed_print(node)
next_state = get_state(node)
if(not(next_state in visit)):#ensure the node is not visited
visit[next_state] = 1
path[next_state] = [state,zero_pos]#record the state path and the solution
if(node == obj):openlist.insert(0,node)
elif(displacement(node,obj)<=2):openlist.insert(1,node)
elif(displacement(node,obj)<=4):openlist.insert(2,node)
elif(displacement(node,obj)<=6):openlist.insert(3,node)
else:openlist.append(node)
return False
def move(path,zero_pos,state):
zero_list = [zero_pos]
while(path[state][0]!=-1):
zero_list = [path[state][1]]+zero_list
state = path[state][0]
print(len(zero_list))
return
for i in range(len(zero_list)-1):
os.system('cls')
formed_print(T)
#time.sleep(0.00001)
T[zero_list[i]],T[zero_list[i+1]] = T[zero_list[i+1]],T[zero_list[i]]
os.system('cls')
formed_print(T)
path,node,zero_pos,state = bfs()
move(path,zero_pos,state)