使用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

机器人只能向前走或者向右转，我在想代码里每个模板该怎么命名……比如“children”应该叫什么，或者“node”呢？

我在用Calico（这让我可以用Python编程）和Myro库来实现这个。

虽然这个帖子发得有点晚，但对感兴趣的人来说，这就是最终的深度优先搜索结果。还有规划移动的代码

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

“孩子”和“节点”是指在一种叫做树形数据结构中的项目。节点就是树中的一个点或项目。而“孩子”指的是在你正在查看的节点下面直接连接的项目。

你的“待办事项”元组看起来第一个项目是你关注的节点，第二个项目是一个孩子数组。这可以是一个嵌套的数据结构，用来表示一棵树。孩子数组下的每个项目本身也可以是节点元组。

我不太明白你提到的“模板”是什么意思。现在你有一棵空树，你的遍历操作应该什么都不做，因为没有任何内容可以处理。理想情况下，你的树的内容可能是通过迷宫的不同路径。

Answer 2

假设有一个这样的结构：

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)