A* 算法求解八数码问题 Python 代码实现

{ "title": "import numpy as np\n\n\nclass State:\n def init(self, state, directionFlag=None, parent=None, f=0):\n self.state = state\n self.direction = ['up', 'down', 'right', 'left']\n if directionFlag:\n self.direction.remove(directionFlag)\n self.parent = parent\n self.f = f\n\n def getDirection(self):\n return self.direction\n\n def setF(self, f):\n self.f = f\n return\n\n # 打印结果\n def showInfo(self):\n for i in range(len(self.state)):\n for j in range(len(self.state)):\n print(self.state[i, j], end=' ')\n print("\n")\n print('->')\n return\n\n # 获取0点\n def getZeroPos(self):\n postion = np.where(self.state == 0)\n return postion\n\n # 曼哈顿距离 f = g + h，g=1，如果用宽度优先的评估函数可以不调用该函数\n def getFunctionValue(self):\n cur_node = self.state.copy()\n fin_node = self.answer.copy()\n dist = 0\n N = len(cur_node)\n\n for i in range(N):\n for j in range(N):\n if cur_node[i][j] != fin_node[i][j]:\n index = np.argwhere(fin_node == cur_node[i][j])\n x = index[0][0] # 最终x距离\n y = index[0][1] # 最终y距离\n dist += (abs(x - i) + abs(y - j))\n return dist + 1\n\n def nextStep(self):\n if not self.direction:\n return []\n subStates = []\n boarder = len(self.state) - 1\n # 获取0点位置\n x, y = self.getZeroPos()\n # 向左\n if 'left' in self.direction and y > 0:\n s = self.state.copy()\n tmp = s[x, y - 1]\n s[x, y - 1] = s[x, y]\n s[x, y] = tmp\n news = State(s, directionFlag='right', parent=self)\n news.setF(news.getFunctionValue())\n subStates.append(news)\n # 向上\n if 'up' in self.direction and x > 0:\n # it can move to upper place\n s = self.state.copy()\n tmp = s[x - 1, y]\n s[x - 1, y] = s[x, y]\n s[x, y] = tmp\n news = State(s, directionFlag='down', parent=self)\n news.setF(news.getFunctionValue())\n subStates.append(news)\n # 向下\n if 'down' in self.direction and x < boarder:\n # it can move to down place\n s = self.state.copy()\n tmp = s[x + 1, y]\n s[x + 1, y] = s[x, y]\n s[x, y] = tmp\n news = State(s, directionFlag='up', parent=self)\n news.setF(news.getFunctionValue())\n subStates.append(news)\n # 向右\n if self.direction.count('right') and y < boarder:\n # it can move to right place\n s = self.state.copy()\n tmp = s[x, y + 1]\n s[x, y + 1] = s[x, y]\n s[x, y] = tmp\n news = State(s, directionFlag='left', parent=self)\n news.setF(news.getFunctionValue())\n subStates.append(news)\n # 返回F值最小的下一个点\n subStates.sort(key=compareNum)\n return subStates[0]\n\n # A* 迭代\n def solve(self):\n openTable = [self]\n closeTable = []\n while openTable:\n # 获取F值最小的点\n curState = openTable.pop(0)\n # 加入close表\n closeTable.append(curState)\n # 获取下一步的点\n subStates = curState.nextStep()\n for state in subStates:\n # 判断是否已经在close表中\n if state in closeTable:\n continue\n # 判断是否已经在open表中\n if state not in openTable:\n # 判断是否和最终结果相同\n if (state.state == state.answer).all():\n path = [state]\n while state.parent and state.parent != originState:\n path.append(state.parent)\n state = state.parent\n path.reverse()\n return path\n openTable.append(state)\n else:\n # 更新F值\n index = openTable.index(state)\n if state.f < openTable[index].f:\n openTable[index].f = state.f\n openTable[index].parent = state.parent\n # open表按F值进行排序\n openTable.sort(key=compareNum)\n return None, None\n\n\ndef compareNum(state):\n return state.f\n\n\nif name == 'main':\n originState = State(np.array([[1, 5, 3], [2, 4, 6], [7, 0, 8]]))\n State.answer = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 0]])\n\n s1 = State(state=originState.state)\n path = s1.solve()\n if path:\n for node in path:\n node.showInfo()\n print(State.answer)\n print('Total steps is %d' % len(path))