使用BFS解决8难题游戏使用Python 2

Question

我试图用BFS、DFS和A*算法来解决使用Python2.7实现的8字谜游戏。目前，我已经成功地使用BFS解决了几个测试用例，我想知道如何改进算法的实现以及我的程序的结构。

该程序目前分为4个文件：

class Board:
    """ The Board class represents the low-level physical configuration of the 
        8-puzzle game. """

    # The 8-puzzle board can be represented as a list of length 8
    def __init__(self, initial_values=[]):
        self.value = initial_values

    def __eq__(self, other): 
        return self.value == other.value

    def __str__(self):
        return str(self.value)

    def __hash__(self):
        return hash(str(self))

    # If 0 is in the top most block, then up is invalid
    def up(self):
        pos = self.value.index(0)
        if pos in (0, 1, 2):
            return None
        else:
            new_val = list(self.value)
            new_val[pos], new_val[pos-3] = new_val[pos-3], new_val[pos]
            return new_val

    # If 0 is in the bottom most block, then up is invalid
    def down(self):
        pos = self.value.index(0)
        if pos in (6, 7, 8):
            return None
        else:
            new_val = list(self.value)
            new_val[pos], new_val[pos+3] = new_val[pos+3], new_val[pos]
            return new_val

    # If 0 is in the left most block, then up is invalid
    def left(self):
        pos = self.value.index(0)
        if pos in (0, 3, 6):
            return None
        else:
            new_val = list(self.value)
            new_val[pos], new_val[pos-1] = new_val[pos-1], new_val[pos]
            return new_val

    # If 0 is in the right most block, then up is invalid
    def right(self):
        pos = self.value.index(0)
        if pos in (2, 5, 8):
            return None
        else:
            new_val = list(self.value)
            new_val[pos], new_val[pos+1] = new_val[pos+1], new_val[pos]
            return new_val

然后我们有state.py来代表游戏的高级动作：

from board import Board
class State:
    """ Handles the state of the game """

    def __init__(self, initial_state=[]):
        self.current = Board(initial_state)

    def __eq__(self, other): 
        return self.current == other.current

    def __str__(self):
        return str(self.current)

    def __hash__(self):
        return hash(str(self))

    def up(self):
        up = self.current.up()
        if up is not None:
            return State(up)
        else:
            return self

    def down(self):
        down = self.current.down()
        if down is not None:
            return State(down)
        else:
            return self

    def left(self):
        left = self.current.left()
        if left is not None:
            return State(left)
        else:
            return self

    def right(self):
        right = self.current.right()
        if right is not None:
            return State(right)
        else:
            return self

    def successors(self):
        succ = []

        up = self.current.up()
        if up != None:
            succ.append(State(up))


        down = self.current.down()
        if down != None:
            succ.append(State(down))


        left = self.current.left()
        if left != None:
            succ.append(State(left))


        right = self.current.right()
        if right != None:
            succ.append(State(right))

        return succ

然后，search.py模块包含算法(目前只包含BFS )：

from collections import namedtuple


def goal_test(state):
    return str(state) == str(range(0, 9))


# BFS Search
def bfs(start):
    """ 
    Performs breadth-first search starting with the 'start' as the beginning
    node. Returns a namedtuple 'Success' which contains namedtuple 'position'
    (includes: node, cost, depth, prev), 'max_depth' and 'nodes_expanded'
    if a node that passes the goal test has been found.

    """

    # SearchPos used for bookeeping and finding the path:
    SearchPos = namedtuple('SearchPos', 'node, cost, depth, prev')

    # Initial position does not have a predecessor
    position = SearchPos(start, 0, 0, None)


    # frontier contains unexpanded positions
    frontier = [position]
    explored = set()
    while len(frontier) > 0:

        # current position is the first position in the frontier
        position = frontier.pop(0)

        node = position.node

        # goal test: return success if True
        if goal_test(node):
            max_depth = max([pos.depth for pos in frontier])
            Success = namedtuple('Success', 
                        'position, max_depth, nodes_expanded')
            success = Success(position, max_depth, len(explored))
            return success

        # expanded nodes are added to explored set
        explored.add(node)

        # All reachable positions from current postion is added to frontier
        for neighbor in node.successors():
            new_position = SearchPos(neighbor, position.cost + 1,
                                    position.depth + 1, position)
            frontier_check = neighbor in [pos.node for pos in frontier]
            if neighbor not in explored and not frontier_check:
                frontier.append(new_position)

    # the goal could not be reached.
    return None

最后，使用solver.py执行搜索：

from state import State
import search
import time
import resource


def trace_path(last_pos):
    pos = last_pos.prev
    next_pos = last_pos

    path = []

    while pos != None:
        if pos.node.up() == next_pos.node:
            path.append("Up")
        elif pos.node.down() == next_pos.node:
            path.append("Down")
        elif pos.node.left() == next_pos.node:
            path.append("Left")
        elif pos.node.right() == next_pos.node:
            path.append("Right")

        pos = pos.prev
        next_pos = next_pos.prev

    return path[::-1]


start_time = time.time()
config = [1,2,5,3,4,0,6,7,8]

game = State(config)

result = search.bfs(game)
final_pos = result.position
max_depth = result.max_depth
nodes_expanded = result.nodes_expanded

print "path_to_goal:", trace_path(final_pos)
print "cost_of_path:", final_pos.cost
print "nodes_expanded:", nodes_expanded
print "search_depth:", final_pos.depth
print "max_search_depth:", max_depth
print "running_time:", time.time() - start_time
print "max_ram_usage", resource.getrusage(1)[2]

Answer 1

我注意到你代码中只有一条线索，

当您检查邻居是否在边境线时，

使用此代码：

 frontier_check = neighbor in [pos.node for pos in frontier]

列表中的成员资格测试比集合中的成员资格测试要慢。有关更多信息，请考虑这个问题。

在edx平台上讨论这个作业这是链接时，我找到了一些有用的技巧。

以下是他所说的话：

刚开始时，我使用了一个普通的python列表来跟踪探索过的节点。当解决方案的深度大于6或7时，它运行得非常慢。我开始了一些研究，发现99%的cpu时间用于成员资格测试。因此，我更改了一组提高性能的列表，但是程序仍然花费了太多的时间才能找到解决方案。这是因为我的前沿类使用了一个deque，它还具有指数成员测试时间。所以我做了一个实现，我在字典中跟踪状态，它对成员资格测试具有线性时间复杂度，队列只是用于节点扩展的顺序，现在它在10秒内计算出任何问题的解决方案。总之，当“列表”进行指数成员资格测试时，不要使用“列表中的节点”。没有指数成员资格测试的数据结构:像Sets这样的无序列表，或者哈希映射/字典

下面是我的一个工作实现：

在前沿和frontier_set中，我将跟踪探索过的节点，以便进行未来的测试。下面是对您的代码的更正：

只需添加2行代码并删除1，就会加快整个过程。

from collections import deque
def bfs(start):
    """ 
    Performs breadth-first search starting with the 'start' as the beginning
    node. Returns a namedtuple 'Success' which contains namedtuple 'position'
    (includes: node, cost, depth, prev), 'max_depth' and 'nodes_expanded'
    if a node that passes the goal test has been found.

    """

    # SearchPos used for bookeeping and finding the path:
    SearchPos = namedtuple('SearchPos', 'node, cost, depth, prev')

    # Initial position does not have a predecessor
    position = SearchPos(start, 0, 0, None)
    # frontier contains unexpanded positions
    frontier = deque([position])
    frontier_set = {position}
    explored = set()
    while frontier:

        # current position is the first position in the frontier
        position = frontier.popleft()

        node = position.node

        # goal test: return success if True
        if goal_test(node):
            max_depth = max(pos.depth for pos in frontier)
            Success = namedtuple('Success', 
                        'position, max_depth, nodes_expanded')
            success = Success(position, max_depth, len(explored))
            return success

        # expanded nodes are added to explored set
        explored.add(node)

        # All reachable positions from current postion is added to frontier
        for neighbor in node.successors():
            new_position = SearchPos(neighbor, position.cost + 1,
                                    position.depth + 1, position)

            if neighbor not in explored and new_position not in frontier_set:
                frontier.append(new_position)
                frontier_set.add(new_position)

Answer 2

State

这个类几乎没有什么有用的工作，可以集成到Board类中。

Board

在这里，对董事会的内部表示进行解释的docstring可能会有所帮助。我设法推断出你的董事会结构是这样的：

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+

您可以使用0作为空闲位置的占位符，其余的只是这个板子的扁平列表。

它将帮助您下次访问该Board时，您需要向任何想要在此上进行维护的人表明这一点。您的用户不需要知道这种表示。

这样做的缺点是缺乏灵活性。假设您想要使用另一个板大小，那么您将需要对这个类进行巨大的更改。这可以像这样变得更容易：

class Board(object):
    def __init__(self, initial_values=(), dimensions=(3,3)):
        rows, columns = dimensions
        assert len(initial_values) == rows * columns

        self._values = tuple(initial_values)
        self._rows = rows
        self._columns = columns

在这里，我使用一个元组，而不是一个列表，以使板不变。这样，您就不需要在str中转换为__hash__。

而不是硬编码的坐标不能做某些移动，我会提供4个小助手方法。

    def _top_row(self):
        return range(self._rows)

    def _bottom_row(self):
        bottom_left = (self._rows - 1) * self._columns
        return range(bottom_left, self._rows * self._columns, self._columns)

    def _left_row(self):
        return range(0, self._rows * self._columns, self._columns)

    def _right_row(self):
        return range(self._columns - 1, self._columns * self._rows, self._columns)

和另一个小帮手为目前的位置。

    @property
    def _current(self):
        return self.values.index(0)

对于板上的移动，我会提出一个Exception来表示一个非法的举动，而不是返回None。

    def up(self):
        """
        if `up` is a valid move, return a new board position
        with the empty piece shifted up. 

        If `up` is invalid, raise an `IllegalMove`
        """
        pos = self._current
        if pos in self._top_row():
            raise IllegalMove

        new_pos = pos - self._columns
        new_board = list(self._values)
        new_board[pos], new_board[new_pos] = new_board[new_pos], new_board[pos]
        return Board(new_board, dimensions=(self._rows, self._columns))

要定义有效的接班人，我将使用generator，而不是返回列表。这使得这很简单

    def valid_successors(self):
        moves = self.up, self.down, self.left, self.right

        for move in moves:
            try:
                yield move()
            except IllegalMove:
                pass

goal_test也可以是这个Board的一部分：

    def goal_test(self):
        return self._values == sorted(self._values)