5
即使世界在Android上一個可愛的小遊戲叫Traffic Jam如何改進我的Traffic Jam遞歸求解器的算法？
我寫了一個遞歸求解：
import copy,sys
sys.setrecursionlimit(10000)
def lookup_car(car_string,ingrid):
car=[]
i=0
for row in ingrid:
j=0
for cell in row:
if cell == car_string:
car.append([i,j])
j+=1
i+=1
return car
#True if up/down False if side to side
def isDirectionUp(car):
init_row=car[0][0]
for node in car:
if node[0] != init_row:
return True
return False
def space_up(car,grid):
top_node=car[0]
m_space_up = (top_node[0]-1,top_node[1])
if top_node[0] == 0:
return -1
elif grid[m_space_up[0]][m_space_up[1]] != " ":
return -1
else:
return m_space_up
def space_down(car,grid):
bottom_node = car[-1]
m_space_down = (bottom_node[0]+1,bottom_node[1])
if bottom_node[0] == 5 :
return -1
elif grid[m_space_down[0]][m_space_down[1]] != " ":
return -1
else:
return m_space_down
def space_left(car,grid):
left_node = car[0]
m_space_left = (left_node[0],left_node[1]-1)
if left_node[1] == 0 :
return -1
elif grid[m_space_left[0]][m_space_left[1]] != " ":
return -1
else:
return m_space_left
def space_right(car,grid):
right_node = car[-1]
m_space_right = (right_node[0],right_node[1]+1)
if right_node[1] == 5 :
return -1
elif grid[m_space_right[0]][m_space_right[1]] != " ":
return -1
else:
return m_space_right
def list_moves(car,grid):
ret =[]
if isDirectionUp(car):
up = space_up(car,grid)
if up != -1:
ret.append(("UP",up))
down = space_down(car,grid)
if down != -1:
ret.append(("DOWN",down))
else:
left = space_left(car,grid)
if left != -1:
ret.append(("LEFT",left))
right = space_right(car,grid)
if right != -1:
ret.append(("RIGHT",right))
return ret
def move_car(car_string,move,ingrid):
grid = copy.deepcopy(ingrid)
car = lookup_car(car_string,grid)
move_to = move[1]
front = car[0]
back = car[-1]
if(move[0] == "UP" or move[0] == "LEFT"):
grid[back[0]][back[1]] = " "
grid[move_to[0]][move_to[1]] = car_string
elif(move[0] == "DOWN" or move[0] == "RIGHT"):
grid[front[0]][front[1]] = " "
grid[move_to[0]][move_to[1]] = car_string
return grid
def is_solution(grid):
car = lookup_car("z",grid)
if(car[-1] == [2,5]):
return True
elif space_right(car,grid) == -1:
return False
else:
solgrid = move_car("z",("RIGHT",space_right(car,grid)),grid)
return is_solution(solgrid)
def print_grid(grid):
for row in grid:
print ''.join(row)
def solve(grid,solution,depth):
global stop
global state
if grid in state:
return
else:
state.append(grid)
if stop:
return
if is_solution(grid):
print_grid(grid)
print len(solution)
else:
for each in "abcdefzhijklm":
car = lookup_car(each,grid)
moves = list_moves(car,grid)
for move in moves:
solution.append((each,move))
moved_grid = move_car(each,move,grid)
solve(moved_grid,solution,depth)
stop=False
state=[]
recdepth=0
#grid file using a-w and x means free space, and ' ' means yellow car
grid=[list(x) for x in file(sys.argv[1]).read().split('\n')[0:-1]]
solve(grid,[],0)
WHERE網格是在一個文件中：
abccdd
abeef
azzhfi
jjjhfi
kll
kmm
但是，它需要超過8000個移動尋找解決方案，並找不到一個簡單的30移動解決方案。算法有什麼問題？
什麼阻止它進入週期？ – 2010-12-08 18:12:28
另外，請考慮http://en.wikipedia.org/wiki/Breadth-first_search和http://en.wikipedia.org/wiki/Depth-first_search之間的差異，看看最適合該問題的是什麼。 – 2010-12-08 18:15:19
問題在於你的solve（）函數。你試圖實施什麼樣的搜索算法？假設BFS，看看維基百科關於「廣度優先搜索」的文章，並嘗試將它們的僞代碼更忠實地轉換成python。 – jtdubs 2010-12-08 18:15:24