Comment améliorer l'algorithme de mon solveur récursif Traffic Jam?

Question

Theres un petit jeu mignon sur Android appelé Traffic Jam

J'ai écrit un solveur récursive:

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 grille est dans un fichier:

abccdd 
abeef 
azzhfi 
jjjhfi 
    kll 
    kmm 

Mais, il faut plus de 8000 se déplace pour trouver une solution, et ne parvient pas à trouver une solution simple de 30 mouvements. Quel est le problème avec l'algorithme?

Answer 1

Si le facteur de branchement de votre espace de recherche est r alors le nombre de sommets dans l'arbre de recherche à la profondeur n est (1-r^n)/(1-r). Un problème avec une solution minimale de 30 étapes, même dans le cas simple où r = 2, aura un arbre de recherche avec environ 2^30 - 1 ~ = 1 000 000 000 sommets. Maintenant, votre facteur de branchement est susceptible d'être plus grand que 2, donc un problème de 30 étapes est loin d'être trivial!

Cela dit, je serais enclin à (a) trouver une meilleure représentation de votre problème (tableaux de chaînes de recherche est lent) et (b) d'envisager plus première recherche où vous guidez votre recherche avec une heuristique (par exemple, la distance de la voiture jaune de sa destination ou le nombre de voitures bloquant le chemin de la voiture jaune).

Espérons que cela aide.

Answer 2

Ceci est essentiellement un problème de recherche (relativement symbolique), avec un énorme espace de recherche. Comme d'autres l'ont recommandé, lisez Depth-first search, puis lisez Breadth-first search, et quand vous apprenez la différence, lisez A* Search et trouvez une fonction de notation pessimiste.

Notez également que dans ce cas, vous savez déjà quel devrait être l'état final, donc une autre approche consisterait à rechercher des deux côtés et à se rencontrer au milieu. Cela devrait considérablement réduire votre espace de recherche.

Si cela ne suffit pas, vous pouvez combiner les techniques!