DFS路径查找与障碍

-1

我有以下网格，我试图去1，在该网格中，障碍显示2.机器人已按此顺序优先运动：上，右，下，左。起始位置旁边有一个*号。DFS路径查找与障碍

0 0* 0 
0 2 0 
1 1 0

是我迄今所做的是把该网格的位置成为图形的形式，也产生了从优先次序每个位置的所有可能移动。但是我的问题是，当算法到达第二行的最后一部分时，算法会陷入循环。我试图实现某种循环检测器，所以我不会陷入这种循环。

我还应该提到，机器人可以通过两次不同的路径访问相同的位置。所以我至今是：

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

凡

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

做手工。这表明该路径应该如下：右，下，下，左，右，上，上，左，下，下，下

关于如何实现探测器的任何建议将是伟大的，我对AI和Python非常新，我一直试图弄清楚这一整天......谢谢

来源

2016-09-17 Ghazal

什么使路径终止于'（2,0）'？它应该在所有单元已被访问或全部1被访问或有其他一些条件时终止？ – niemmi

机器人**是否在尝试其他选项之前采取了首选步骤？如果迷宫是'1 0 0 *'，是正确的答案是左，还是没有路径？ – niemmi

当所有1都被访问时，路径终止，机器人按照首选顺序进行步骤，所以如果迷宫是1 0 0 *它会尝试向右，向下，但这些都不可能移动，所以它就会移动左侧左侧 – Ghazal

试试这个：

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)

这是基于递归的。尝试根据问题中指定的顺序移动到下一个位置，并将移动存储到打印到达目的地的列表中

来源

2016-09-17 05:47:41 Fayaz

我对这是如何工作有点困惑，代码提供了两个解决方案，从开始的位置开始，但是，一旦它到达第一个解决方案，它应该继续在同一条路径上，而不是在（0 ，1）。我无法确定第二次以（0,1）再次启动的部分 – Ghazal

其实我设法修复了这个部分，但这是不对的，因为一旦它变成（2,1）就不是回溯，而是向左走 – Ghazal

'if grid [x] [y] == 1： print str（curr） return None' 所以一旦找到解决方案就应该返回。您是否取消了退货？ – Fayaz

DFS路径查找与障碍

回答

相关问题