¿Cómo puedo mejorar el algoritmo para mi solucionador recursivo Traffic Jam?

Question

Hay un pequeño juego lindo en Android llamados Traffic Jam

He escrito un solucionador recursivo:

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) 

DONDE rejilla está en un archivo:

abccdd 
abeef 
azzhfi 
jjjhfi 
    kll 
    kmm 

embargo, se necesita más de 8000 se mueve para encontrar una solución y no encuentra una solución simple de 30 movimientos. ¿Qué está mal con el algoritmo?

Answer 1

Si el factor de bifurcación de su espacio de búsqueda es r, el número de vértices en el árbol de búsqueda para la profundidad n es (1-r^n)/(1-r). Un problema con una solución mínima de 30 pasos, incluso en el caso simple donde r = 2, tendrá un árbol de búsqueda con alrededor de 2^30 - 1 ~ = 1,000,000,000 de vértices. Ahora, es probable que su factor de bifurcación sea mayor que 2, por lo que un problema de 30 pasos está muy lejos de ser trivial.

Dicho esto, me inclinaría a (a) encontrar una mejor representación de su problema (buscar matrices de cadenas se lenta) y (b) considerar primero el mejor de búsqueda en el que guía su búsqueda con una heurística (por ejemplo, la distancia del automóvil amarillo desde su destino o la cantidad de autos que bloquean el camino del automóvil amarillo).

Espero que esto ayude.

Answer 2

Esto es esencialmente un problema de búsqueda (relativamente token), con un gran espacio de búsqueda. Como otros recomendaron, lea en Depth-first search, y luego lea en Breadth-first search, y cuando vea la diferencia, lea en A* Search y obtenga una función de puntuación pesimista.

Además, tenga en cuenta que en este caso, ya sabe cuál debería ser el estado final, por lo tanto, otro enfoque sería buscar desde ambos extremos y encontrarse en el medio. Esto debería reducir considerablemente su espacio de búsqueda.

Si eso no es suficiente, ¡puede combinar las técnicas!