python-3.x - 寻求有关在 Python 中使用 BFS 创建迷宫的建议

Question

寻求有关如何构造 python 来创建迷宫的建议，使用 BFS 解决它，并在迷宫中进行基本导航以及导航所需的移动次数。使用沿路径移动，上、左、右、下。下面是一些代码，我将它们拼凑在一起思考并弄清楚如何为这个 BFS 算法代码构建 python。

有人愿意指导这个 BFS 算法导航迷宫 python 结构吗？

基本上遵循以下算法：

函数 BREADTH-FIRST-SEARCH(problem) 返回解决方案节点或失败节点 ← NODE(problem.INITIAL) 如果 issue.IS-GOAL(node.STATE) 然后返回节点边界 ← FIFO 队列，节点作为元素到达 ← {problem.INITIAL} 而不是 IS-EMPTY(frontier) 为 EXPAND(problem, node) 中的每个子节点执行 node ← POP(frontier) 执行 ← child.STATE if problem.IS-GOAL(s) then return child if s未到达然后添加 s 到达 将子项添加到边界返回失败

import sys

def parse_map(filename):
    with open(filename, "r") as f:
        return [[char for char in line] for line in f.read().rstrip("\n").split("\n")][3:]

def count_x(house_map):
    return sum([ row.count('p') for row in house_map ] )

def printable_house_map(house_map):
    return "\n".join(["".join(row) for row in house_map])

def add_x(house_map, row, col):
    return house_map[0:row] + [house_map[row][0:col] + ['p',] + house_map[row][col+1:]] + house_map[row+1:]

def successors(house_map):
    return [ add_x(house_map, r, c) for r in range(0, len(house_map)) for c in range(0,len(house_map[0])) if house_map[r][c] == '.' ]

def is_goal(house_map, k):
    return count_x(house_map) == k 

def bfs_graph_search(house_map):
    fringe = [initial_house_map]
    if house_map.goal_test(node.state):
        return fringe
    fringe = deque([house_map])
    visited = set()
    while fringe:
        fringe = fringe.popleft()
        visited.add(node.state)
        for child in node.expand(problem):
            if child.state not in fringe and child not in visited:
                if house_map.goal_test(child.state):
                    return child
                fringe.append(child)
    return None

def solve(initial_house_map,k):
    fringe = [initial_house_map]
    while len(fringe) > 0:
        for new_house_map in successors( fringe.pop() ):
            if is_goal(new_house_map,k):
                return(new_house_map,True)
            fringe.append(new_house_map)

if __name__ == "__main__":
    
    house_map=parse_map('map1.txt')
    k = 2 
    print ("Initial ]house map:\n" + printable_house_map(house_map) + "\n\nSearching for solution...\n")
    solution = solve(house_map,k)
    print ("Found:")
    print (printable_house_map(solution[0]) if solution[1] else "False")


class Agent:

    def __init__(self, initial, goal=None):
        self.initial = initial
        self.goal = goal

    def actions(self, state):
        raise NotImplementedError

    def result(self, state, action):
        raise NotImplementedError

    def goal_test(self, state):
        if isinstance(self.goal, list):
            return is_in(state, self.goal)
        else:
            return state == self.goal

    def path_cost(self, c, state1, action, state2):
        return c + 1

    def value(self, state):
        raise NotImplementedError

class FringeGraph:

    def __init__(self, state, parent=None, action=None, path_cost=0):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost
        self.depth = 0
        if parent:
            self.depth = parent.depth + 1
    
    def path(self):
        node, path_back = self, []
        while node:
            path_back.append(node)
            node = node.parent
        return list(reversed(path_back))

    def solution(self):
        return [node.action for node in self.path()[1:]]

    def expand(self, agent):
        return [self.child_node(agent, action)
                for action in agent.actions(self.state)]

    def child_node(self, agent, action):
        next_state = agent.result(self.state, action)
        next_node = Node(next_state, self, action, problem.path_cost(self.path_cost, self.state, action, next_state))
        return next_node

class Agent:

    def __init__(self, initial, goal=None):
        self.initial = initial
        self.goal = goal

    def actions(self, state):
        raise NotImplementedError

    def result(self, state, action):
        raise NotImplementedError

    def goal_test(self, state):
        if isinstance(self.goal, list):
            return is_in(state, self.goal)
        else:
            return state == self.goal

    def path_cost(self, c, state1, action, state2):
        return c + 1

    def value(self, state):
        raise NotImplementedError

class FringeGraph:

    def __init__(self, state, parent=None, action=None, path_cost=0):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost
        self.depth = 0
        if parent:
            self.depth = parent.depth + 1
    
    def path(self):
        node, path_back = self, []
        while node:
            path_back.append(node)
            node = node.parent
        return list(reversed(path_back))

    def solution(self):
        return [node.action for node in self.path()[1:]]

    def expand(self, agent):
        return [self.child_node(agent, action)
                for action in agent.actions(self.state)]

    def child_node(self, agent, action):
        next_state = agent.result(self.state, action)
        next_node = Node(next_state, self, action, agent.path_cost(self.path_cost, self.state, action, next_state))
        return next_node

标签： python-3.xalgorithmnavigationbreadth-first-search