Recherche de chemin DFS avec des obstacles

Question

J'ai la grille suivante et j'essaie d'atteindre les 1 dans cette grille, l'obstacle est montré par 2. Le robot a priorisé le mouvement dans cet ordre: haut, droite, bas, gauche . La position de départ a un * à côté.

0 0* 0 
0 2 0 
1 1 0 

Ce que je l'ai fait jusqu'à présent est de mettre la position de cette grille en une forme graphique, et aussi généré tous les mouvements possibles de chaque position dans l'ordre de priorité. Mais mon problème est que l'algorithme reste coincé dans une boucle quand il arrive à la dernière section de la deuxième rangée. J'essaie de mettre en place une sorte de détecteur de cycle afin que je ne sois pas coincé dans cette boucle.

Je devrais également mentionner que le robot peut visiter la même position deux fois plus longtemps que par des chemins différents. Donc ce que j'ai à ce jour est:

def dfs(grid,start): 

    #find the routes in U,R,D,L order 
    height = len(grid) 

    width = len(grid[0]) 

    routes = {(i, j) : [] for j in range(width) for i in range(height)} 

    for row, col in routes.keys(): 
     # Left moves 
    if col > 0: 
      routes[(row, col)].append((row , col - 1)) 
     # Down moves  
    if row < height - 1: 
      routes[(row, col)].append(((row + 1, col))) 
    # Right moves 
    if col < width - 1: 
     routes[(row, col)].append(((row , col + 1))) 
    # Up moves 
    if row > 0: 
     routes[(row, col)].append(((row - 1, col))) 

    #find the blocked ones 

    blocked = {(i,j) for j in range(width) for i in range(height) if grid[i][j] == 2} 

    path = [] 

    stack = [start] 

    while stack: 
    node = stack.pop() 

    if node not in blocked: 
     path.append(node) 
     stack = [] 
     for x in routes[node]: 
      stack.extend([x]) 

    return path 

Où

grid = [[0, 0, 0], [0, 2, 0], [1, 1, 0]] 
start = (0,1) 

Faire cela à la main montre que le chemin doit aller comme suit: droite, bas, bas, gauche, droite, haut, haut, gauche, gauche, bas, bas

des suggestions sur la façon dont je peux mettre en œuvre le détecteur serait génial, je suis très nouveau à AI et python et j'ai essayé de comprendre cela toute la journée ... merci

Answer 1

Essayez ceci:

def dfs2(grid,pos,curr,height,width): 
    x = pos[0] 
    y = pos[1]  
    if grid[x][y]==1: 
     print str(curr) 
     return None 
    elif grid[x][y] ==2: 
     return None   
    last = curr[-1]  
    if x-1 >= 0 and last != 'DOWN':   
     curr.append('UP') 
     dfs2(grid,(x-1,y),curr,height,width) 
     curr.pop() 
    if y+1 < width and last != 'LEFT':   
     curr.append('RIGHT') 
     dfs2(grid,(x,y+1),curr,height,width) 
     curr.pop() 
    if x+1 < height and last != 'UP': 
     curr.append('DOWN') 
     dfs2(grid,(x+1,y),curr,height,width) 
     curr.pop() 
    if y-1>=0 and last != 'RIGHT': 
     curr.append('LEFT') 
     dfs2(grid,(x,y-1),curr,height,width) 
     curr.pop() 


def dfs(grid,pos): 
    dfs2(grid,pos,['START'],len(grid),len(grid[0])) 

########MAIN######### 
#up, right, down, left 
grid = [[0, 0, 0], [0, 2, 0], [1, 1, 0]] 
start = (0,1) 
print str(grid) 
dfs(grid,start) 

Ceci est basé sur la récursivité. Attente pour passer à la position suivante en fonction de l'ordre spécifié dans la question et stocke les mouvements dans une liste qui s'imprime en atteignant la destination