人工智能（Educoder）-- 搜索技术 -- 启发式搜索_educoder启发式搜索算法

任务描述

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

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

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

相关知识

为了完成本关任务，你需要掌握：1.评估函数，2.贪婪最佳优先搜索，3.A*搜索：缩小总评估代价，4.求解思路。

评估函数

在有信息搜索 Informed Search 策略中，常使用的是最佳优先搜索 Best First Search ，它的结点扩展是基于评估函数值f(n)选择的。评估函数被看做是代价估计，因此代价最低的结点最先被选择扩展。

对f(n)的选择决定了搜索策略，大部分的最佳优先搜索算法的f(n)由启发式函数h(n)构成：

h(n)=结点n到目标的最小代价路径的代价估计值

贪婪最佳优先搜索

贪婪最佳优先搜索 Greedy Best-First Search 试图扩展距离目标结点最近的结点，原因是这种策略可能可以非常快的找到解，因此，贪婪最佳优先搜索只使用启发式信息，即f(n)=h(n)。

A*搜索：缩小总评估代价

A* 搜索（A 星搜索）是最广为人知的最佳优先搜索，它对结点n的代价评估结合了g(n)，即到达此结点n已经花费的路径代价，和h(n)，即从该结点n到目标结点所花代价。

f(n)=g(n)+h(n)

由于g(n)是从开始结点到结点n的路径代价，而h(n)是从结点n到目标结点的最小路径代价的估计值因此：

f(n)=经过结点n的最小代价解的估计代价

所以，要寻找最小代价的解，首先扩展的是g(n)+h(n)值最小的结点。可以发现，A* 搜索算法与一致代价搜索算法类似，区别是 A* 搜索算法使用g(n)+h(n)而不是g(n)。

求解思路

该问题是将与空格相连的数字移动到空格的位置上，也就相当于将空格移动到与之相连的位置，因此，以空格为当前结点，扩展结点可能为上下左右四个相连的位置，若使用一般的搜索算法，可能陷入无限搜索中，永远搜不到目标解，而 A* 搜索算法则能非常好的将搜索过程导向求解目标。

问题给的是字符串数据724506831，可以还原成如下形式：

那么空格的l移动操作即为下标4和下标3上所对应的数字的交换，分别为0和5，交换后的新的状态为：

以此类推，空格的lrud各操作均可用以上的交换过程表达。

A* 算法的重中之重就是启发式函数h(n)的设计，不同的设计方法可能产生不同的求解路径。在这里，可以选择欧氏距离作为评估函数值：除0之外，各个数字在当前状态的下标与目标状态的下标的绝对值之和。例如：当前状态为123456780，目标状态为：012345678，数字1的下标分别为0和1，数字2的下标分别为1和2，...，数字8的下标分别为7和8，则当前状态与目标状态的评估值为h(n)=abs(1−2)+abs(2−3)+⋯+abs(7−8)=8。

编程要求

本关的编程任务是补全右侧代码片段 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 -*-
 
class Solution:
 
    def salvePuzzle(self, init, targ):
        ''' 求解8数码问题
        参数：
        init - 初始状态 例如'123046758'
        targ - 目标状态 均为'012345678'
        返回值：
        clf - 由udlr组成的移动路径字符串
        '''
 
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        clf = ''  # 初始化移动路径字符串
        state_open = []  # 初始化开放列表
        state_close = []  # 初始化关闭列表
        state_open.append([init,99,'test',init,0])  # 将初始状态加入开放列表
        fn = 2  # 初始化启发式函数的权重
        flag = 1  # 初始化标志位
        while True:
            cur_state = state_open.pop(0)  # 取出开放列表中的第一个状态
            state_close.append(cur_state)  # 将当前状态加入关闭列表
            if cur_state[0] == targ:  # 如果当前状态等于目标状态
                while 1:
                    clf += cur_state[2]  # 将当前状态的移动方向加入移动路径字符串
                    if cur_state[3] == init:  # 如果当前状态的父状态等于初始状态
                        break
                    for id,item in enumerate(state_close[1:]):  # 遍历关闭列表中的状态
                        if item[0] == cur_state[3]:  # 如果找到父状态
                            cur_state = item  # 更新当前状态为父状态
                return  clf[::-1]  # 返回逆序的移动路径字符串
 
            i = cur_state[0].find('0')  # 找到空格0的位置索引
            flag = 1  # 重置标志位
 
            if str(i) not in '036':  # 如果空格0不在第一行、第三行和第六行
                tmp_map = self.moveMap(cur_state[0],i,i-1)  # 尝试将空格0向左移动
                if tmp_map not in [tmp[0] for tmp in state_close]:  # 如果新状态不在关闭列表中
                    for id,item in enumerate(state_open):  # 遍历开放列表中的状态
                        if item[0] == tmp_map:  # 如果找到新状态
                            if item[1] + item[4] > self.calcDistH(tmp_map,targ) + cur_state[4] + fn:  # 如果新状态的代价大于当前状态的代价
                                state_open[id] = [tmp_map,self.calcDistH(tmp_map,targ),'l',cur_state[0],cur_state[4]+fn]  # 更新开放列表中的状态
                                flag = 0  # 设置标志位为0
                                break
                            break
                    if flag == 1:  # 如果标志位为1
                        state_open.append([tmp_map,self.calcDistH(tmp_map,targ),'l',cur_state[0],cur_state[4]+fn])  # 将新状态加入开放列表
            flag = 1  # 重置标志位
 
            if str(i) not in '258':  # 如果空格0不在第二行、第五行和第八行
                tmp_map = self.moveMap(cur_state[0],i,i+1)  # 尝试将空格0向右移动
                if tmp_map not in [tmp[0] for tmp in state_close]:  # 如果新状态不在关闭列表中
                    for id,item in enumerate(state_open):  # 遍历开放列表中的状态
                        if item[0] == tmp_map:  # 如果找到新状态
                            if item[1] + item[4] > self.calcDistH(tmp_map,targ) + cur_state[4] + fn:  # 如果新状态的代价大于当前状态的代价
                                state_open[id] = [tmp_map,self.calcDistH(tmp_map,targ),'r',cur_state[0],cur_state[4]+fn]  # 更新开放列表中的状态
                                flag = 0  # 设置标志位为0
                                break
                            break
                    if flag ==1:  # 如果标志位为1
                        state_open.append([tmp_map,self.calcDistH(tmp_map,targ),'r',cur_state[0],cur_state[4]+fn])  # 将新状态加入开放列表
            flag = 1  # 重置标志位
 
            if i-3>=0:  # 如果空格0不在最左边的三列
                tmp_map = self.moveMap(cur_state[0],i,i-3)  # 尝试将空格0向上移动
                if tmp_map not in [tmp[0] for tmp in state_close]:  # 如果新状态不在关闭列表中
                    for id,item in enumerate(state_open):  # 遍历开放列表中的状态
                        if item[0] == tmp_map:  # 如果找到新状态
                            if item[1] + item[4] > self.calcDistH(tmp_map,targ) + cur_state[4] + fn:  # 如果新状态的代价大于当前状态的代价
                                state_open[id] = [tmp_map,self.calcDistH(tmp_map,targ),'u',cur_state[0],cur_state[4]+fn]  # 更新开放列表中的状态
                                flag = 0  # 设置标志位为0
                                break
                            break
                    if flag ==1:  # 如果标志位为1
                        state_open.append([tmp_map,self.calcDistH(tmp_map,targ),'u',cur_state[0],cur_state[4]+fn])  # 将新状态加入开放列表
            flag = 1  # 重置标志位
 
            if i+3<=8:  # 如果空格0不在最右边的三列
                tmp_map = self.moveMap(cur_state[0],i,i+3)  # 尝试将空格0向下移动
                if tmp_map not in [tmp[0] for tmp in state_close]:  # 如果新状态不在关闭列表中
                    for id,item in enumerate(state_open):  # 遍历开放列表中的状态
                        if item[0] == tmp_map:  # 如果找到新状态
                            if item[1] + item[4] > self.calcDistH(tmp_map,targ) + cur_state[4] + fn:  # 如果新状态的代价大于当前状态的代价
                                state_open[id] = [tmp_map,self.calcDistH(tmp_map,targ),'d',cur_state[0],cur_state[4]+fn]  # 更新开放列表中的状态
                                flag = 0  # 设置标志位为0
                                break
                            break
                    if flag ==1:  # 如果标志位为1
                        state_open.append([tmp_map,self.calcDistH(tmp_map,targ),'d',cur_state[0],cur_state[4]+fn])  # 将新状态加入开放列表
 
            state_open.sort(key=lambda x : x[1] + x[4])  # 根据代价对开放列表进行排序
        #********** End **********#
 
    def calcDistH(self, src_map, dest_map):
        '''启发式函数h(n)
        参数：
        src_map  - 当前8数码状态
        dest_map - 目标8数码状态
        返回值：
        clf - 当前状态到目标状态的启发式函数值
        '''
 
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if src_map is None or dest_map is None:
            return 0 
 
        clf = 0
        for i in range(9):
            clf += abs(int(src_map[i])-int(dest_map[i]))
        return clf
        #********** End **********#
 
    def moveMap(self, cur_map, i, j):
        '''状态转换（交换位置i和j）
        参数：
        cur_map - 当前8数码状态
        i - 当前8数码状态中空格0的位置索引
        j - 将空格0的位置i移动到位置j，位置j移动到位置i
        返回值：
        clf - 新的8数码状态
        '''
 
        #请在这里补充代码，完成本关任务
        #********** Begin **********#
        if i>j:
            i,j=j,i
        tmp_i = cur_map[i]
        tmp_j = cur_map[j]
        tmp_map = cur_map[:i]+tmp_j+cur_map[i+1:j]+tmp_i+cur_map[j+1:]
 
        return tmp_map
        #********** End **********#