简介
八数码问题：在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算法）编程求解八数码问题（初始状态任选，并对实验结果进行分析得出合理的结论。
流程图
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 |
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_()) |
效果如顶部的图所示
注意GUI部分方向键自己控制，空格键利用算法自动走。
