使用 Python 解决迷宫问题

Question

我的目标是创建一个函数，让机器人能够解决迷宫问题。出于课堂练习的目的，这里的深度优先搜索是模板....

Todo = (root,[])
visited = []
while Todo not empty:
   node,path = Todo[0]
   Todo = Todo[1:]
   if node in visited:
       pass
   else:
       children = node.children
       children.remove(visited)
       if node is good:
           done(return path)
       Todo = [(child, path[child])]
           for child in children

机器人只能前进或右转，我想知道如何命名代码中的每个模板......例如“孩子”是什么或“节点”？

我正在使用 Calico（它可以让我用 python 编程）和 Myro 库来执行此操作。

这是一篇相当晚的文章，但对于那些感兴趣的人来说，这最终成为了最终的 DFS 。 还有计划动作的代码

class Node:
    def __init__(self, x, y, direction):
        self.x = x
        self.y = y
        self.direction = direction

    __left = { 'N' : 'W',
               'E' : 'N',
               'S' : 'E',
               'W' : 'S' }

    __right = { 'N' : 'E',
                'E' : 'S',
                'S' : 'W',
                'W' : 'N' }

    __dx = { 'N' : 0,
             'E' : 1,
             'S' : 0,
             'W' : -1 }

    __dy = { 'N' : 1,
             'E' : 0,
             'S' : -1,
             'W' : 0 }

def __str__(self):
    return "<%d,%d,%s>" % (self.x, self.y, self.direction)


def _left(self):
    return Node(self.x, self.y,
                self.__left[self.direction])

def _right(self):
    return Node(self.x, self.y,
                self.__right[self.direction])

def _forward(self):
    return  Node(self.x + self.__dx[self.direction], 
                 self.y + self.__dy[self.direction], 
                 self.direction)

def children(self):      
    return [ ('left',    self._left()), 
             ('right',   self._right()),
             ('forward', self._forward()),
           ]

def dfs(node, soughtValue, visitedNodes):
     if node.x == soughtValue.x and node.y == soughtValue.y and node.direction ==      soughtValue.direction:
      return []

 newVisited = visitedNodes[:]
 newVisited.append(node)
 for action, adjNode in node.children():
      if adjNode not in newVisited:
          plan = dfs(adjNode, soughtValue, newVisited)
          if plan is not None:
              p = [action]
              p.extend(plan)
              return p
 return None

感谢您的所有回答！

Answer 1

假设结构如

class Node(object):
    def __init__(self):
        self.children = set()

你的深度优先看起来像：

Todo = [(root, [])]
visited = set()
while Todo:
    node, path = Todo.pop()
    path.append(node)
    if node is good:
        return path
    visited.add(node)
    children = node.children.copy()
    Todo.extend([(child, path[:]) for child in children if child not in visited])

Todo 包含一个元组列表。每个元组都是一个节点和到达那里的路径。

测试将是

good = Node()
a = Node()
b = Node()
b.children.add(good)
c = Node()
root = Node()
root.children.add(a)
root.children.add(b)
root.children.add(c)

Answer 2

“子级”和“节点”指的是树数据结构中的项目。节点就是树中的节点或项目。子项是指紧邻您在树中查看的节点下方的项目。

您的“Todo”元组看起来第一项是有问题的节点，第二项是子项数组。这可以是表示树的嵌套数据结构。子数组下的每个项目本身都可以是节点元组。

我不确定你在这里指的“模板”是什么。现在你有一棵空树，你的遍历应该什么也不做，因为没有什么可做的。理想情况下，树的内容可能是穿过迷宫的不同路径。