八数码难题——启发算法_八数码open表与closed表

启发算法和盲目搜索算法，同样需要open表和closed表，最大的不同之处是：每个节点有一个启发值，然后优先搜索启发值小的节点。

因为每个节点都有一个启发值属性，需把启发值和节点一同放入open表，所以管理open表的方式略有不同，这里定义了一个新的expand_new函数管理open。还有，open表也不再按先进先出或后进先出的原则弹出节点，而是按启发值大小弹出节点。此外还需要定义一个按启发值大小弹出节点的新函数pop。

代码在前面盲目搜索（带路径的）的基础编写，加入启发函数部分。

from cha2_8数码_带路径 import find_path 
import cha2_8数码_带路径 as ch 
# 这里两种方式引入前面盲目搜索（带路径）代码，一个是只引入函数find_path，一个是整个文件引入为ch（作为当下的文件中的一个对象），可以ch.xxx 访问ch中定义的变量和函数。但是有一点需要注意，就是 if __name__ == "__main__": 后面的不被导入。
 
# 全局变量：
closed = [] # 字典
# open = [] # 此处不再定义open，用导入的ch 中的open，方式 ch.open，
son_father = {} # 记录搜索树的字典。
 
# 定义函数。原来的expand 需要重新定义，因为需要计算节点的启发函数，并把节点的启发函数值当作节点的属性一起放到open中。原来压入节点的是str，现在压入的节点是这样的列表 [g(str),h(str),str]，还需要定义计算h(str) 的函数
 
def expand_new(now,endlayout):
        zero_pos = now[2].index("0")
        allowed_pos = ch.dic_of_rule[zero_pos] #当前可进行交换的位置集合
        for k in allowed_pos:
            newstr = ch.swap_chr(now[2],k, zero_pos) # 对每个允许的交换执行交换
            if newstr not in closed: # 检测newstr在不在closed中
                ch.open.append([now[0]+1, heu(newstr,endlayout), newstr])
            if son_father.get(newstr) == None:
               son_father[newstr] = now[2] 
        return
 
def pop(open): # 在open中弹出启发函数值最小的节点，启发值就是 g + h
    w = min(open, key=lambda x: x[0] + x[1]) #试试X[0]**2+x[1],能找到移动21步的解
    open.remove(w) # 删除 w。
    return w
 
# 下面定义了三个启发函数heu_1, heu_2, heu_3
def heu_1(strr,endlayout): # 用strr中各字符的位置和在目标中的位置的差，作为启发函数
    total_var = 0
    for i in [str(k) for k in range(9)]: # 所有差累加
          total_var = total_var + abs(strr.index(i)-endlayout.index(i))
    return total_var
 
def heu_2(strr,endlayout): # 所有差的最大值
    max_var = 0
    for i in [str(k) for k in range(9)]: 
          if abs(strr.index(i)-endlayout.index(i)) > max_var:
               max_var = abs(strr.index(i)-endlayout.index(i))
    return max_var
 
def heu_3(strr,endlayout): # 所有差的平方和。
    total_var = 0
    for i in [str(k) for k in range(9)]: 
          total_var = total_var + abs(strr.index(i)-endlayout.index(i))**2
    return total_var
 
# 主程序
if __name__ == "__main__":
    heu = heu_3 # 选择第三个启发函数，选择heu_2费时较长。
    startlayout = "541203786"
    endlayout = "123804765"
    son_father[startlayout] = -1 
    ch.open.append([0,heu(startlayout,endlayout),startlayout])
    iter = 0 
    while 1:
        print(iter)
        iter +=1
        if len(ch.open) == 0:
            print('搜索到头了，没有移动方案能移动到目标')
            break
        else:
            # now = open.popleft()
            now = pop(ch.open) # 弹出 启发函数值最小的节点
            closed.append(now[2]) # 放入closed
            if now[2] == endlayout: # 如到达目标
                print('能移动到目标，共搜索步数：', iter)
                path = find_path(son_father,endlayout) # 生成移动路径 
                print('需要移动 {} 步,\n移动路径是：{}'.format(len(path),path))
                break
            else:
                expand_new(now,endlayout) # 展开当前now 节点，管理open和son_father

运行结果：

能移动到目标，总搜索步数： 208

需要移动 25 步,

移动路径是：deque(['541203786', '501243786', '051243786', '251043786', '251403786', '201453786', '210453786', '213450786', '213405786', '213485706', '213485760', '213480765', '210483765', '201483765', '281403765', '281043765', '081243765', '801243765', '810243765', '813240765', '813204765', '813024765', '013824765', '103824765', '123804765'])