Traffic Jam özyineli özümü için algoritmayı nasıl geliştirebilirim?

Question

Orada Android'de şirin bir oyun Traffic Jam

Ben özyinelemeli çözücüsü yazdık seslendi:

ızgara bir dosyada olduğu

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) 

: o 8000 devralır,

abccdd 
abeef 
azzhfi 
jjjhfi 
    kll 
    kmm 

Ama bir çözüm bulmak için hareket eder ve basit bir 30 hareket çözümünü bulamaz. Algoritmada neyin var? Arama alanı dallanma faktörü r ise

Answer 1

sonra derinlik n arama ağacının tepe nokta sayısını (1-r^n)/(1-r) 'dir. En az 30 basamaklı bir çözümde, r = 2'nin bulunduğu basit durumda bile, yaklaşık 2^30 - 1 ~ = 1,000,000,000 köşeli bir arama ağacına sahip olacaktır. Şimdi, dallanma faktörünüzün 2'den büyük olması muhtemeldir, bu yüzden 30 basamaklı bir problem önemsizden çok uzaktır! Ben eğimli olacağını söyledi

(a) sorunun daha iyi bir temsilini bulmak (yavaş dizeleri diziler edilir arama) ve (b) Eğer bir sezgisel yöntem ile aramanıza yol en birinci aramayı düşünün (örneğin, sarı arabanın hedefinden uzaklığı veya sarı arabanın yolunu engelleyen araçların sayısı).

Bu yardımcı olur umarım.

Answer 2

Bu büyük bir arama alanı ile, esasen bir (nispeten jetonu) arama sorundur. Başkaları önerildiği üzere, Depth-first search kadar okuyun ve sonra Breadth-first search kadar okumak, ve farkı öğrendiğinizde, A* Search kadar okuyun ve kötümser puanlama fonksiyonu ile geliyor.

Ayrıca bu durumda, zaten son durum ne olması gerektiğini biliyor unutmayın, bu nedenle, başka bir yaklaşım iki ucundan arama ve ortada karşılamak olacaktır. Bu, arama alanınızı önemli ölçüde azaltmalıdır.

Bu hala yeterli değilse, teknikleri birleştirebilirsiniz!