Astar算法解决八数码问题Python实现（GUI）

里克贝斯

发布于 2021-05-21 06:48:29

1.7K00

代码可运行

文章被收录于专栏：图灵技术域图灵技术域

运行总次数：0

代码可运行

简介

八数码问题：在3*3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

状态图搜索：

搜索树：搜索过程中经过的节点和边按原图的连接关系构成一个树型的有向图，称为搜索树。
搜索方式
- 树式搜索：记录搜索过程中所经过的所有节点和边
路径的获得
- 树式搜索：反向求解

树式搜索算法：

步1 把初始节点放入OPEN表；
步2 检查OPEN表，若为空，则问题无解，退出；
步3 移出OPEN表中第一个节点N并放入CLOSED表中，并编号为n;
步4 考察节点N是否为目标节点，若是，则搜索成功，退出；
步5 若N不可扩展，则转步2；
步6 扩展节点N，生成所有子节点，对这组子节点作如下处理：
（1）、如果有节点N的先辈节点，则删除；
（2）、如果有已存在于OPEN表的节点，也删除；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原指向父节点的指针，使其指向新的父节点。
（3）、如果有已存在于CLOSED表中的节点，则作与（2）同样的处理，并且再将其移出CLOSED表，放入OPEN表重新扩展；
（4）、对其余子节点，配上指向父节点n的指针后放入OPEN表，对OPEN表按某种搜索策略排序后转步2。

启发式搜索的实验原理：

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。评估函数f(x)定义为：从初始节点S0出发，约束地经过节点X到达目标节点Sg的所有路径中最小路径代价的估计值。

其一般形式为：

f(x)=g(x)+h(x)

其中g(x)表示从初始节点S0到节点X的实际代价；h(x)表示从X到目标节点Sg的最优路径的估计代价。但是实际的形式要根据问题特性确定。

Closed表和open表

——closed表对树式搜索来说存储的是正在成长的搜索树，对线式搜索来说存储的是不断伸长的折现，本省就是所求的路径。

——open表存储当前待考察的节点。

使用一种启发式搜索方法（A算法）编程求解八数码问题（初始状态任选，并对实验结果进行分析得出合理的结论。

流程图

代码

import sys
import random
from enum import IntEnum
from PyQt5.QtWidgets import QLabel, QWidget, QApplication, QGridLayout, QMessageBox
from PyQt5.QtGui import QFont, QPalette
from PyQt5.QtCore import Qt
import copy

solution = []
solutionStep = 0
times = 0

# 用枚举类表示方向
class Direction(IntEnum):
    UP = 0
    DOWN = 1
    LEFT = 2
    RIGHT = 3


class NumberHuaRong(QWidget):
    def __init__(self):
        super().__init__()
        self.blocks = []
        self.zero_row = 0
        self.zero_column = 0
        self.gltMain = QGridLayout()
        self.initUI()

    def initUI(self):
        # 设置方块间隔
        self.gltMain.setSpacing(10)

        self.onInit()

        # 设置布局
        self.setLayout(self.gltMain)
        # 设置宽和高
        self.setFixedSize(400, 400)
        # 设置标题
        self.setWindowTitle('八数码问题')
        # 设置背景颜色
        self.setStyleSheet("background-color:gray;")
        self.show()

    # 初始化布局
    def onInit(self):
        # 产生顺序数组
        self.numbers = list(range(1, 9))
        self.numbers.append(0)

        # 将数字添加到二维数组
        for row in range(3):
            self.blocks.append([])
            for column in range(3):
                temp = self.numbers[row * 3 + column]

                if temp == 0:
                    self.zero_row = row
                    self.zero_column = column
                self.blocks[row].append(temp)
        print(self.blocks)
        # 打乱数组
        for i in range(500):
            random_num = random.randint(0, 3)
            self.move(Direction(random_num))

        self.updatePanel()

    # 检测按键
    def keyPressEvent(self, event):
        key = event.key()
        if key == Qt.Key_Up or key == Qt.Key_W:
            self.move(Direction.UP)
        if key == Qt.Key_Down or key == Qt.Key_S:
            self.move(Direction.DOWN)
        if key == Qt.Key_Left or key == Qt.Key_A:
            self.move(Direction.LEFT)
        if key == Qt.Key_Right or key == Qt.Key_D:
            self.move(Direction.RIGHT)
        if key == Qt.Key_Enter or key == Qt.Key_Space:
            global solution
            solutionLen = len(solution)
            global solutionStep
            global times
            self.blocks = solution[solutionLen-solutionStep-3]
            print(self.blocks)
            solutionStep = solutionStep + 1
            times += 1
        self.updatePanel()
        if self.checkResult():
            if QMessageBox.Ok == QMessageBox.information(self, '挑战结果', '恭喜您完成挑战！总步数：' + str(times)):
                self.onInit()

    # 方块移动算法
    def move(self, direction):
        if(direction == Direction.UP): # 上
            if self.zero_row != 2:
                self.blocks[self.zero_row][self.zero_column] = self.blocks[self.zero_row + 1][self.zero_column]
                self.blocks[self.zero_row + 1][self.zero_column] = 0
                self.zero_row += 1
        if(direction == Direction.DOWN): # 下
            if self.zero_row != 0:
                self.blocks[self.zero_row][self.zero_column] = self.blocks[self.zero_row - 1][self.zero_column]
                self.blocks[self.zero_row - 1][self.zero_column] = 0
                self.zero_row -= 1
        if(direction == Direction.LEFT): # 左
            if self.zero_column != 2:
                self.blocks[self.zero_row][self.zero_column] = self.blocks[self.zero_row][self.zero_column + 1]
                self.blocks[self.zero_row][self.zero_column + 1] = 0
                self.zero_column += 1
        if(direction == Direction.RIGHT): # 右
            if self.zero_column != 0:
                self.blocks[self.zero_row][self.zero_column] = self.blocks[self.zero_row][self.zero_column - 1]
                self.blocks[self.zero_row][self.zero_column - 1] = 0
                self.zero_column -= 1

    def updatePanel(self):
        for row in range(3):
            for column in range(3):
                self.gltMain.addWidget(Block(self.blocks[row][column]), row, column)

        self.setLayout(self.gltMain)

    # 检测是否完成
    def checkResult(self):
        # 先检测最右下角是否为0
        if self.blocks[2][2] != 0:
            return False

        for row in range(3):
            for column in range(3):
                # 运行到此处说名最右下角已经为0，pass即可
                if row == 2 and column == 2:
                    pass
                #值是否对应
                elif self.blocks[row][column] != row * 3 + column + 1:
                    return False

        return True

class Block(QLabel):
    """ 数字方块 """

    def __init__(self, number):
        super().__init__()

        self.number = number
        self.setFixedSize(80, 80)

        # 设置字体
        font = QFont()
        font.setPointSize(30)
        font.setBold(True)
        self.setFont(font)

        # 设置字体颜色
        pa = QPalette()
        pa.setColor(QPalette.WindowText, Qt.white)
        self.setPalette(pa)

        # 设置文字位置
        self.setAlignment(Qt.AlignCenter)

        # 设置背景颜色\圆角和文本内容
        if self.number == 0:
            self.setStyleSheet("background-color:white;border-radius:10px;")
        else:
            self.setStyleSheet("background-color:blue;border-radius:10px;")
            self.setText(str(self.number))

#########################################
app = QApplication(sys.argv)
ex = NumberHuaRong()
start = ex.blocks
start.append(0)
start.append(0)
target = [[1, 2, 3], [4, 5, 6], [7, 8, 0], -1]


def evaluate(state):
    global target
    f = 0
    for i in range(3):
        for j in range(3):
            if state[i][j] != target[i][j]:
                f += 1
    return f


def findSpace(state):
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                return i, j


def expand(state, t):
    x = findSpace(state)[0]
    y = findSpace(state)[-1]
    expState = []
    # up
    if x-1 >= 0 and t == 0:
        up = copy.deepcopy(state)
        up[x-1][y], up[x][y] = up[x][y], up[x-1][y]
        expState.append(up)
        return up
    if x+1 <= 2 and t == 1:
        down = copy.deepcopy(state)
        down[x+1][y], down[x][y] = down[x][y], down[x+1][y]
        expState.append(down)
        return down
    if y-1 >= 0 and t == 2:
        left = copy.deepcopy(state)
        left[x][y-1], left[x][y] = left[x][y], left[x][y-1]
        expState.append(left)
        return left
    if y+1 <= 2 and t == 3:
        right = copy.deepcopy(state)
        right[x][y+1], right[x][y] = right[x][y], right[x][y+1]
        expState.append(right)
        return right


def findBestID():
    global openValue
    tmin = 10
    flag = 0
    for i in range(len(openList)):
        if openList[i][-1] == 0 and openValue[i] < tmin:
            tmin = openValue[i]
            flag = i
    return flag


def judgeSame(state1, state2):
    for i in range(3):
        for j in range(3):
            if state1[i][j] != state2[i][j]:
                return False
    return True


def evaOpenValue():
    global openList
    global openValue
    openValue = []
    for i in range(len(openList)):
        temp = evaluate(openList[i])
        openValue.append(temp)

def evaCloseValue():
    global closeList
    global closeValue
    closeValue = []
    for i in range(len(closeList)):
        temp = evaluate(closeList[i])
        closeValue.append(temp)


openList = []
openValue = []
closeList = []
closeValue = []
openList.append(start)

tarID = 0
while openList is not None:
    evaOpenValue()
    minID = findBestID()
    if judgeSame(openList[minID], target):
        print('ok')
        tarID = minID
        break
    for t in range(4):
        expTemp = expand(openList[minID], t)
        if expTemp is not None:
            evai = evaluate(expTemp)

            expTemp[3] = minID
            expTemp[-1] = 0
            flag1 = 0
            for j in range(len(openList)):
                if judgeSame(expTemp, openList[j]) and openList[j][-1] == 0:
                    flag1 = 1
                    break
            flag2 = 0
            for j in range(len(closeList)):
                if judgeSame(expTemp, closeList[j]):
                    flag2 = 1
                    break
            if flag2 == 0 and flag1 == 0:
                openList.append(expTemp)
                openValue.append(evai)
    closeList.append(openList[minID])
    openList[minID][-1] = 1


temp = openList[tarID]

while temp[-2] != 0:
    for i in range(3):
        for j in range(3):
            print(temp[i][j], end=' ')
        print('\n')
    print('---------')
    solution.append(temp[:3])
    temp = openList[temp[-2]]


solution.append(temp[:3])
print(temp[:3])
solution.append(start[:3])
print(start[:3])
solutionStep = len(solution) - 1
print(solution)
sys.exit(app.exec_())