目录

一、实验主要步骤

①.设计界面输入规则

②.判断是否有解

③.求解

二、实验结果展示

 三、附录

完整实验程序代码:

---

一、实验主要步骤

①.设计界面输入规则

有且仅有9位数字代表数码和空格，从左到右，从上至下，空格用0表示。

②.判断是否有解

有判断是否有解至关重要，因为后续求解的过程中包含着循环迭代，若无解的话，程序会始终处于寻找解的状态，陷入死循环无法跳出。作为用户，短时间内无法判断是求解时间过长还是陷入死循环中，影响判断。
经过查阅，得知可以用逆序数解决是否有解问题。

 将其转换为代码：

#先判断八数码问题是否有解
num1=0
num2=0
#求初始状态的逆序数 num1
for i in start:
    if i!="0":
        for j in start[0:start.index(i)]:
            if j>i:
                num1=num1+1
#求目的状态的逆序数 num2
for i in end:
    if i!="0":
        for j in end[0:end.index(i)]:
            if j>i:
                num2=num2+1
if num1%2!=num2%2:
    print("该题无解")
    exit(0)#如果无解则立即退出程序 避免在后面的算法中陷入死循环

③.求解

有解时，首先创建两个矩阵START和END分别存储初始状态和目标状态，之后定义类State，当类实例化的时候，自动调用类函数init，创建结点、给启发函数赋初始值以及给父亲结点赋值。

#创建两个矩阵 分别将初始状态和目标状态赋值给矩阵
START=np.zeros((num,num))
END=np.zeros((num,num))
for i in range(num):
    for j in range(num):
        START[i][j]=start[z]
        END[i][j]=end[z]
        z=z+1
excel=[]

class State:
    def __init__(self,m):
        #node存储矩阵的数据
        self.node=m
        #f(n)为g(n)+h(n)
        self.f=0
        self.g=0
        self.h=0
        #节点的父亲节点赋初始值
        self.father=None

init = State(START)#初始状态
goal=State(END)#目标状态

定义启发函数h：a初始值为，若当前结点与目标结点的值不一致，则a自增1，函数的返回值为a。

#启发函数
def h(s):
    a=0
    for i in range(len(s.node)):
        for j in range(len(s.node[i])):
            if s.node[i][j]!=goal.node[i][j]:
                a=a+1
    return a

定义排序函数list_sort：对结点列表，安装估价函数的值的规则进行排序。

#对节点列表按照估价函数的值的规则排序
def list_sort(l):
    cmp=operator.attrgetter('f')
    l.sort(key=cmp)

定义打印函数printpath：使用递归对路径进行打印。

# 递归打印路径
def printpath(f):
    if f is None:
        return
    #注意print()语句放在递归调用前和递归调用后的区别。放在后实现了倒叙输出
    printpath(f.father)
    print(f.node)

A*算法：当excel表格不为空时循环求解：若结点与目标结点一致，则从excel列表里移除该结点，随后判断空格状态的位置并开始移动，最后再将excel表格排序进行下一次的循环。

#A*算法    
def A_star(s):
    global excel#全局变量可以让excel表进行时时更新
    excel=[s]
    #当excel表不为空时 循环求解
    while(excel):
        get=excel[0] #取出excel表的首节点  
        if (get.node==goal.node).all():#判断是否与目标节点一致
            return get
        excel.remove(get)#将get移出excel表
        #判断此时状态的空格位置
        for a in range(len(get.node)):
            for b in range(len(get.node[a])):
                if get.node[a][b]==0:
                    break
            if get.node[a][b]==0:
                break
        #开始移动
        for i in range(len(get.node)):
            for j in range(len(get.node[i])):
                c=get.node.copy()
                if (i+j-a-b)**2==1:
                    c[a][b]=c[i][j]
                    c[i][j]=0
                    new=State(c)
                    new.father=get#此时取出的get节点成为新节点的父亲节点
                    new.g=get.g+1#新节点与父亲节点的距离
                    new.h=h(new)#新节点的启发函数值
                    new.f=new.g+new.h#新节点的估价函数值
                    excel.append(new)#加入excel表中
        list_sort(excel)#排序 

二、实验结果展示

 三、附录

完整实验程序代码:

import numpy as np
import operator

print("注：本系统应用于八数码问题，加上无数码位共需输入9位数字，数字之间不需要输入空格或标点符号，用数字0表示无数码，如输入123456708，即为：")
print("        1  2  3")
print("        4  5  6")
print("        7  0  8")
start=list(input("初始状态："))
end=list(input("目标状态："))
num=3
z=0

#先判断八数码问题是否有解
num1=0
num2=0
#求初始状态的逆序数 num1
for i in start:
    if i!="0":
        for j in start[0:start.index(i)]:
            if j>i:
                num1=num1+1
#求目的状态的逆序数 num2
for i in end:
    if i!="0":
        for j in end[0:end.index(i)]:
            if j>i:
                num2=num2+1
if num1%2!=num2%2:
    print("该题无解")
    exit(0)#如果无解则立即退出程序 避免在后面的算法中陷入死循环

    
#创建两个矩阵 分别将初始状态和目标状态赋值给矩阵
START=np.zeros((num,num))
END=np.zeros((num,num))
for i in range(num):
    for j in range(num):
        START[i][j]=start[z]
        END[i][j]=end[z]
        z=z+1
excel=[]

class State:
    def __init__(self,m):
        #node存储矩阵的数据
        self.node=m
        #f(n)为g(n)+h(n)
        self.f=0
        self.g=0
        self.h=0
        #节点的父亲节点赋初始值
        self.father=None

init = State(START)#初始状态
goal=State(END)#目标状态

#启发函数
def h(s):
    a=0
    for i in range(len(s.node)):
        for j in range(len(s.node[i])):
            if s.node[i][j]!=goal.node[i][j]:
                a=a+1
    return a

#对节点列表按照估价函数的值的规则排序
def list_sort(l):
    cmp=operator.attrgetter('f')
    l.sort(key=cmp)
    
#A*算法    
def A_star(s):
    global excel#全局变量可以让excel表进行时时更新
    excel=[s]
    #当excel表不为空时 循环求解
    while(excel):
        get=excel[0] #取出excel表的首节点  
        if (get.node==goal.node).all():#判断是否与目标节点一致
            return get
        excel.remove(get)#将get移出excel表
        #判断此时状态的空格位置
        for a in range(len(get.node)):
            for b in range(len(get.node[a])):
                if get.node[a][b]==0:
                    break
            if get.node[a][b]==0:
                break
        #开始移动
        for i in range(len(get.node)):
            for j in range(len(get.node[i])):
                c=get.node.copy()
                if (i+j-a-b)**2==1:
                    c[a][b]=c[i][j]
                    c[i][j]=0
                    new=State(c)
                    new.father=get#此时取出的get节点成为新节点的父亲节点
                    new.g=get.g+1#新节点与父亲节点的距离
                    new.h=h(new)#新节点的启发函数值
                    new.f=new.g+new.h#新节点的估价函数值
                    excel.append(new)#加入excel表中
        list_sort(excel)#排序 
# 递归打印路径
def printpath(f):
    if f is None:
        return
    #注意print()语句放在递归调用前和递归调用后的区别。放在后实现了倒叙输出
    printpath(f.father)
    print(f.node)
    

final=A_star(init)

if final:
    print("有解，解为：")
    printpath(final)