8数码问题

问题描述

• 在一个3x3的方格盘上，放有1~8的数码，余下一格为空，空格四周上下左右的数码可移到空格，需要找到一个数码移动序列使初识的无序数码转变为一些特殊的排列。

算法设计

• 定义h*(n)为状态n到目的状态的最优路径的代价，则当A搜索算法的启发函数h(n)小于等于h*(n)，即满足h(n)<=h*(n)，对所有结点n时，被称为A*搜索算法。

代码实现

import copy
import heapq

class Node:
    def __init__(self, state, actions=None, cost=0):
        self.state = state
        self.actions = actions
        self.cost = cost
        self.length = len(state)
        self.space_ij = self.find_zero_ij()

    def find_zero_ij(self):
        for i in range(self.length):
            for j in range(self.length):
                if self.state[i][j] == 0:
                    return i, j

    # 用于优先队列排序。
    def __lt__(self, other):
        return self.cost <= other.cost

    # 用于输出结点的状态。
    def __str__(self):
        msg = ''
        for i in range(self.length):
            msg += str(self.state[i]) + '\n'
        return msg


def h(node_state, end_state):
    #     return 0
    # return h1(node_state, end_state,n)
    return h2(node_state, end_state)


# 统一代价搜索
def h1(node_state, end_state):
    length = len(node_state)
    cost = 0
    for i in range(length):
        for j in range(length):
            if node_state[i][j] != end_state[i][j]:
                cost += 1
    return cost


# Manhattan距离
def h2(node_state, end_state):
    length = len(node_state)
    cost = 0
    for i in range(length):
        for j in range(length):
            for x in range(length):
                for y in range(length):
                    if node_state[i][j] == end_state[x][y]:
                        cost += abs(x - i) + abs(y - j)
    return cost


def move(node, action, end_state):
    next_node = None
    state = copy.deepcopy(node.state)
    (i, j) = node.space_ij
    has_next = False
    # Up
    if action == 'Up' and i - 1 >= 0:
        state[i][j] = state[i - 1][j]
        state[i - 1][j] = 0
        has_next = True
    # Down
    if action == 'Down' and i + 1 < 3:
        state[i][j] = state[i + 1][j]
        state[i + 1][j] = 0
        has_next = True
    # Left
    if action == 'Left' and j - 1 >= 0:
        state[i][j] = state[i][j - 1]
        state[i][j - 1] = 0
        has_next = True
    # Right
    if action == 'Right' and j + 1 < 3:
        state[i][j] = state[i][j + 1]
        state[i][j + 1] = 0
        has_next = True
    if has_next:
        actions = node.actions.copy()
        actions.append(action)
        cost = h(state, end_state) + len(actions)
        next_node = Node(state, actions, cost)
    return next_node


def a_star(start_state, end_state):
    start_node = Node(start_state, [], 0 + h(start_state, end_state))
    fringe = []
    closed = []
    end_node = None
    # 入优先队列。
    heapq.heappush(fringe, start_node)
    n = 0
    while len(fringe) > 0:
        # 从优先队列中选出一个代价最小的。
        current_node = heapq.heappop(fringe)
        # 如果当前状态与最终状态一致。
        if current_node.state == end_state:
            end_node = current_node
            break
        for action in ['Up', 'Down', 'Left', 'Right']:
            # 使用move(）遍历每个action
            next_node = move(current_node, action, end_state)
            if next_node is not None:
                if next_node.state in closed:
                    pass
                else:
                    heapq.heappush(fringe, next_node)
        # 入结果队列。
        closed.append(current_node.state)
        # 判断计算次数是否过大。
        n += 1
        if n % 10000 == 0:
            print(n, current_node.cost)
        if n >= 100000:
            print('Do not find resolution after searching 100000 nodes ...')
    # 打印步骤。
    next_node = start_node
    print('Initial state')
    print(next_node, '\n')
    for action in end_node.actions:
        next_node = move(next_node, action, end_state)
        print(action)
        print(next_node, '\n')
    print(n, len(end_node.actions), end_node.actions)
    return end_node


if __name__ == '__main__':
    # 初始状态。
    startState = [[7, 2, 4], [5, 0, 6], [8, 3, 1]]
    # start_state = [[4, 0, 5], [1, 2, 3], [7, 8, 6]]

    # 目标状态。
    endState = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
    a_star(startState, endState)

• a_star(start_state, end_state)：根据起始状态和目标状态，计算出求解的方法并输出。
  • start_state：起始状态。
  • end_state：目标状态。
• h1(node_state, end_state)：盲目搜索算法。
  • node_state：节点目前的状态。
  • end_state：目标状态。
• h2(node_state, end_state):：曼哈顿距离启发式搜索算法。
  • node_state：节点目前的状态。
  • end_state：目标状态。
• move(node, action, end_state)：将该节点的空白区域移动。
  • node：当前节点。
  • action：移动的方向。
  • end_state：目标状态。