0

我正在尝试编写一个深度优先搜索算法，该算法将找到代理（黑色立方体所在）到右侧路径底部出口的路径形式。但是我编写的算法会作为找到的路径的一部分在自身上循环。如何实现不这样做的 DFS 算法？

关于我做错了什么的任何想法？

任何帮助非常感谢，请。

谢谢 世界是什么样子的：

世界/迷宫。

深度优先搜索路径规划的结果：

路径规划的输出/结果

我的代理类代码：

class Agent(turtle.Turtle):
    def __init__(self, location, endPoint, world): 
        turtle.Turtle.__init__(self)
        self.shape("square")
        self.color("black")
        self.penup()
        self.speed(0)
    
        # Variables
        self._bump = 0
        self._location = location
        self._endPoint = endPoint
        self._world = world
        self._map = dict()
    
    def dfs_paths(self, start, goal, path=None):
        if path is None:
            path = [start]
        if start == goal:
            yield path
        for next in self._map[tuple(start)] - set(path):
            yield from dfs_paths(next, goal, path + [next])
    
    def _planPath(self, node, visited=None):
        if visited is None:
            visited = [node]
        self._map[tuple(node)] = self._world.testDirections(node)
        if node not in visited:
            visited.append(tuple((node)))
            print("Visited = " + str(visited))
            for neighbour in self._map[tuple((node))]:
                print("Neighbour = " + str(neighbour))
                if neighbour == self._endPoint:
                    visited.append(neighbour)
                    print("Here 1...")
                    return [node, neighbour]
                else:     
                    path = self._planPath(neighbour,visited)
                    if path:
                        print("Here 2...")
                        return [node] + path
4

1 回答 1

0

您正在根据visited信息构建路径。但这并不代表路径。它只代表您访问过的节点，其中包括您已经回溯的不成功路径。

当您找到目标节点时，您应该创建一个仅包含结束节点的（部分）路径，并将其返回给调用者。调用者可以从递归调用的返回值中检测到找到了目标，然后可以将其自己的节点添加到该部分路径，并将其返回给自己的调用者。

这样，回溯阶段（成功后）将用于构建路径。

所以，为了让你开始，替换这个：

self._planPath(neighbour, visited)

和：

path = self._planPath(neighbour, visited)
if path:  # success!
    return [node] + path

或者做一个append更有效的方法，但是你必须在最后反转路径。

并替换这个：

self._world.showPath(visited)

和：

return [node, neighbor]

的主要调用者self._planPath可能会做这样的事情：

path = self._planPath(startnode, [])
if path:
    self._world.showPath(path)

请注意，visited您应该真正使用的是set，而不是列表。

于 2021-04-20T17:47:36.917 回答