algorithm - 如何改进我的交通拥堵递归求解器的算法？

Question

Android 上有一个可爱的小游戏，叫做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)

网格在文件中的位置:

abccdd
abeef 
azzhfi
jjjhfi
  kll
  kmm

但是，它需要 8000 多步才能找到解决方案，而无法找到简单的 30 步解决方案。算法有什么问题？

Answer 1

如果搜索空间的分支因子为 r，则搜索树中深度为 n 的顶点数为 (1-r^n)/(1-r)。最小 30 步解决方案的问题，即使在 r = 2 的简单情况下，也会有一个具有大约 2^30 - 1 ~= 1,000,000,000 个顶点的搜索树。现在，您的分支因子可能大于 2，因此 30 步问题远非微不足道!

就是说，我倾向于 (a) 找到更好的问题表示方法(搜索字符串数组很慢)和 (b) 考虑最佳优先搜索来指导您的问题使用启发式搜索(例如，黄色汽车与其目的地的距离或阻挡黄色汽车路径的汽车数量)。

希望这对您有所帮助。