使用Python解決迷宮問題

我的目標是創建一個功能，讓機器人解決迷宮問題。該類鍛鍊; Tibial其目的這裏深度優先搜索是模板....使用Python解決迷宮問題

機器人只能前進或右轉即時知道什麼名字代碼中的每個模板......比如什麼「孩子」會成爲「節點」嗎？

我使用印花布（讓我在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

感謝，雖然所有的答案！

來源

2014-04-01 Scymantic

哦，通常'node'和'children'意味着你要使用[鏈接列表]的一些變種（http://en.wikipedia.org/wiki/Linked_list）。由於您正在嘗試建模迷宮，因此您將使用[圖表]（http://en.wikipedia.org/wiki/Graph_%28data_structure%29）。否則，我不確定你的問題是什麼。 – 2rs2ts

爲什麼你初始化Todo'（root，[]）'？不應該是'[root]'？ – njzk2

'在訪問過的節點'和'children.remove（visited）'實現相同我認爲 – njzk2

假設結構，如

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])

藤含有元組的列表。每個元組都是一個節點並且是到達那裏的路徑。

測試將

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)

來源

2014-04-01 19:19:51 njzk2

「兒童」和「節點」是指什麼是tree data structure.節點就是 - 樹中的節點或項目。孩子是指你正在樹中看到的節點下的項目。

您的「Todo」元組看起來像第一個項目是有問題的節點，第二個項目是一組子項目。這可以是表示樹的嵌套數據結構。 children數組下的每個項目本身都可以是節點元組。

我不確定你在這裏用「模板」指的是什麼。現在你有一棵空樹，你的遍歷應該什麼都不做，因爲沒有什麼可做的。理想情況下，你的樹的內容可能是迷宮中可用的不同路徑。

來源

2014-04-01 19:05:10 FrobberOfBits

使用Python解決迷宮問題

回答

相關問題