【头歌实验】人工智能之启发式搜索算法

人工智能之启发式搜索算法

任务描述

本关任务：八数码问题是在一个3×3的棋盘上有1−8位数字随机分布，以及一个空格，与空格相连的棋子可以滑动到空格中，问题的解是通过空格滑动，使得棋盘转化为目标状态，如下图所示。

为了简化问题的输入，首先将空格用数字0表示，然后将3×3的棋盘用9位长的字符串表示，则上图的初始状态为724506831，目标状态为012345678，本关卡所有目标状态均为012345678，也保证初始状态到目标状态有解。

对于上图的初始状态，将数字2移动到空格，称之为u操作（空格上移），将数字3移动到空格，称之为d操作（空格下移），将数字5移动到空格，称之为l操作（空格左移），将数字6移动到空格，称之为r操作（空格右移），则一个合法移动路径为lurdrdllurrdllurrulldrrull。

724        724        024        204        254            ...        012
506        056        756        756        706            ...        345
831        831        831        831        831            ...        678
        l            u            r            d            ...            l

编程要求

本关的编程任务是补全右侧代码片段 salvePuzzle 、 calcDistH 和 moveMap 中 Begin 至 End 中间的代码，具体要求如下：

在 salvePuzzle 中，根据输入参数init（初始状态，如724506831）和targ（目标状态，均为012345678），实现 A* 搜索算法，返回八数码问题的移动路径，如上图的移动路径：lurdrdllurrdllurrulldrrull。

在 calcDistH 中，计算当前状态（参数srcmap，如724506831）到目标状态（参数destmap，如012345678）的启发式函数值h(n)，并返回h(n)。

在 moveMap 中，实现行动转换，并返回下一个状态，例如当前状态为参数curmap=724506831，当前 8 数码状态curmap中空格 0 的位置索引i=4，移动空格到位置j=3，则返回的新状态为newmap=724056831。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着测试程序会调用上述函数，并判断函数返回的路径是否为合法解，若是则输出 Accepted 表示程序正确，否则程序错误。

以下是平台的测试样例：

测试输入：
724506831
预期输出：
Accepted

代码

# -*- coding:utf-8 -*-
import heapq

class Solution:
    def salvePuzzle(self, init, targ):
        ''' 求解8数码问题
        参数：
        init - 初始状态 例如'123046758'
        targ - 目标状态 均为'012345678'
        返回值：
        clf - 由udlr组成的移动路径字符串
        '''
        heap = []
        h_init = self.calcDistH(init, targ)
        heapq.heappush(heap, (h_init + 0, 0, init, ''))
        closed = set()
        
        while heap:
            f, g, current, path = heapq.heappop(heap)
            if current == targ:
                return path
            if current in closed:
                continue
            closed.add(current)
            i = current.index('0')
            row, col = divmod(i, 3)
            moves = []
            if row > 0:
                moves.append((i - 3, 'u'))
            if row < 2:
                moves.append((i + 3, 'd'))
            if col > 0:
                moves.append((i - 1, 'l'))
            if col < 2:
                moves.append((i + 1, 'r'))
            for j, direction in moves:
                new_state = self.moveMap(current, i, j)
                if new_state not in closed:
                    new_g = g + 1
                    new_h = self.calcDistH(new_state, targ)
                    new_f = new_g + new_h
                    new_path = path + direction
                    heapq.heappush(heap, (new_f, new_g, new_state, new_path))
        return ''

    def calcDistH(self, src_map, dest_map):
        '''启发式函数h(n)
        参数：
        src_map - 当前8数码状态
        dest_map - 目标8数码状态
        返回值：
        clf - 当前状态到目标状态的启发式函数值
        '''
        h = 0
        for i in range(9):
            c = src_map[i]
            if c == '0':
                continue
            j = dest_map.index(c)
            x1, y1 = divmod(i, 3)
            x2, y2 = divmod(j, 3)
            h += abs(x1 - x2) + abs(y1 - y2)
        return h

    def moveMap(self, cur_map, i, j):
        '''状态转换（交换位置i和j）
        参数：
        cur_map - 当前8数码状态
        i - 当前8数码状态中空格0的位置索引
        j - 将空格0的位置i移动到位置j，位置j移动到位置i
        返回值：
        clf - 新的8数码状态
        '''
        lst = list(cur_map)
        lst[i], lst[j] = lst[j], lst[i]
        return ''.join(lst)