八数码与十五数码问题

八数码问题

八数码问题也叫九宫问题，是人工智能中状态搜索中的经典问题，其中，该问题描述为：在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

这是一个典型的图搜索问题，但是该问题并不需要正在建立图数据结构来进行求解，而是将图的搜索方法抽象，运用到该问题上。以下是分析过程：

首先考虑将算法问题进行抽象和编码。如果把空格记成0，棋盘上的所有状态共有 9! =

362880种。我们要先找到一种方法把棋盘的状态进行编码。

下图是计算机如何求解的一种模拟图：

十五数码问题

十五数码问题就是四宫格问题，描述同上。

解决思路：

1. BFS

BFS（广度优先搜索）是一种图遍历算法，它从一个起始点开始，逐层扩展搜索范围，直到找到目标节点为止。

这种算法通常用于解决“最短路径”问题，比如在迷宫中找到从起点到终点的最短路径

首先，你会从起点开始，检查所有与它相邻的位置，也就是距离起点为1的位置

然后，你会继续向外扩展，检查所有距离起点为2的位置，以此类推，直到找到出口

在BFS中，你可以使用队列来存储待搜索的节点。起始点首先加入队列中，然后不断从队列中取出节点，检查它是否是目标节点。如果不是，就将它的所有未被访问过的邻居加入队列中。这样，队列中的节点总是按照它们距离起点的距离排序，先加入队列的节点总是先被取出来搜索。

通过这种方式，BFS可以找到起点到目标节点的最短路径。在实际应用中，BFS还可以用于拓扑排序、连通性检测等问题的解决。

2. 启发式搜索算法

和其它的图搜索算法一样，A*潜在地搜索图中一个很大的区域。和Dijkstra一样，A*能用于搜索最短路径。和BFS一样，A*能用启发式函数（注：原文为heuristic）引导它自己。在简单的情况中，它和BFS一样快。

成功的秘决在于，它把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。在讨论A*的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价（heuristic estimated cost）。在上图中，yellow(h)表示远离目标的结点而teal(g)表示远离初始点的结点。当从初始点向目标点移动时，A*权衡这两者。每次进行主循环时，它检查f(n)最小的结点n，其中f(n) = g(n) + h(n)。

启发式函数可以控制A*的行为：

• 一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A*演变成Dijkstra算法，这保证能找到最短路径。

• 如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A*保证能找到一条最短路径。h(n)越小，A*扩展的结点越多，运行就得越慢。

• 如果h(n)精确地等于从n移动到目标的代价，则A*将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A*会运行得很完美，认识这一点很好。

• 如果h(n)有时比从n移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。

• 另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A*演变成BFS算法。

　　所以我们得到一个很有趣的情况，那就是我们可以决定我们想要从A*中获得什么。理想情况下（注：原文为At exactly the right point），我们想最快地得到最短路径。如果我们的目标太低，我们仍会得到最短路径，不过速度变慢了；如果我们的目标太高，那我们就放弃了最短路径，但A*运行得更快。

在游戏中，A*的这个特性非常有用。例如，你会发现在某些情况下，你希望得到一条好的路径（"good" path）而不是一条完美的路径（"perfect" path）。为了权衡g(n)和h(n)，你可以修改任意一个。

注:在学术上，如果启发式函数值是对实际代价的低估，A*算法被称为简单的A算法（原文为simply A）。然而，我继续称之为A*，因为在实现上是一样的，并且在游戏编程领域并不区别A和A*。

本次实现A*算法解决数码问题（python版）

#导入数学库以及优先队列
import math
from queue import PriorityQueue

#定义隐状态节点
class Node:def __init__(self,status,cost):#优先级和节点名称self.status = statusself.cost = costdef __lt__(self, other):""" 定义<比较操作符。这是为了优先队列的比较"""# 从大到小排序return self.cost < other.costdef __str__(self):return "Task(priority={p}, name={n})".format(p=self.status, n=self.cost)

class Astar:def __init__(self,code = [0,1,2,3,4,5,6,7,8,9]):#类的一些一些结果self.count_sumnode = 0#生成节点self.count_extendnode = 0#扩展节点self.res = []#结果self.code = code#n数码问题的n个符号self.iter = 0#迭代次数def salvePuzzle(self, start, goal):#解决问题函数主体self.iter = 0frontier = PriorityQueue()#传入初始状态init,目标状态targ，返回移动路径（string形式）frontier.put(Node(start, self.calcDistH2(start, goal)))#访问过的节点#移动方向，对应二维坐标的变化dirs = ['up', 'down', 'left', 'right']dict_depth = {start: 0}#深度表，用来记录节点是否被访问过及对应的深度close = {}#来向came_from = {}#当前代价#起点来向置空came_from[start]=Nonen = int (math.sqrt(len(start)+1))count_status = 0;while not frontier.empty():self.count_extendnode = self.count_extendnode + 1current = frontier.get()count_status = count_status + 1print("状态",count_status," ")for i in range(n):print(current.status[3*i]," ",current.status[3*i+1]," ",current.status[3*i+2])print("状态",count_status," ",current.status," f值：",dict_depth[current.status],"g值：",self.calcDistH2(current.status, goal))#print(current.status,self.calcDistH(current.status, goal))#如果队列头元素在closed表中，移出优先队列while current.status in close:current = frontier.get()#如果队列头元素为goal,找到解if current.status == goal:self.count_extendnode = self.count_extendnode - 1print("找到解！迭代次数为:{}".format(self.iter))break#将当前节点加入close表close[current.status]=current.cost#压入相邻节点for i in range(4):next_status = self.move(current.status,dirs[i])if next_status == None:continueelse:self.iter = self.iter + 1depth = dict_depth[current.status]+1#print(next_status,depth+self.calcDistH(next_status, goal))if ((next_status in dict_depth) == False):self.count_sumnode = self.count_sumnode +1dict_depth[next_status] = depthfrontier.put(Node(next_status, depth+self.calcDistH2(next_status, goal)))came_from[next_status] = current.statuselse:#当前节点在深度表中且当前深度小于深度表中的值，更新深度表，建立父子关系if (depth < dict_depth[next_status]):dict_depth[next_status] = depthcame_from[next_status] = current.status#如果当前节点在close表中，将其移出close表，将更新后的节点移入open表if (next_status in close):del close[next_status]frontier.put(Node(next_status, depth+self.calcDistH2(next_status, goal)))s = goalif frontier.empty():print("未找到解！迭代次数为:{}".format(self.iter))return while came_from[s] !=None:#print(came_from[s])self.res.append([s,self.moveMap(came_from[s],s)])s = came_from[s]self.res = self.res[::-1]def move(self,status,direction):#move传入状态和方向，返回该方向移动后的结果n = int(math.sqrt(len(status)+1))#得到行列大小flag = status.index('0')#找到0的位置x0=flag//ny0=flag%n#print(status,x0,y0)ans = [[0 for i in range(n)]for i in range(n)]pos = 0for i in range(n):for j in range(n):ans[i][j]=status[pos]pos = pos+1   if direction=="up":if x0==0:return Noneelse:ans[x0][y0] = ans[x0-1][y0]ans[x0-1][y0]='0'res = ''for i in range(n):for j in range(n):res = res + ans[i][j]return reselif direction=="down":if x0 ==n - 1:return Noneelse:ans[x0][y0] = ans[x0+1][y0]ans[x0+1][y0]='0'res = ''for i in range(n):for j in range(n):res = res + ans[i][j]return reselif direction=="left":if y0 == 0:return Noneelse:ans[x0][y0] = ans[x0][y0-1]ans[x0][y0-1]='0'res = ''for i in range(n):for j in range(n):res = res + ans[i][j]return reselse:if y0 == n - 1:return Noneelse:ans[x0][y0] = ans[x0][y0+1]ans[x0][y0+1]='0'res = ''for i in range(n):for j in range(n):res = res + ans[i][j]return resdef calcDistH(self, src_map, dest_map):#采用曼哈顿距离作为估值函数cost = 0src_dic={}dest_dic={}code_n = self.codefor i in range(len(src_map)):src_dic[src_map[i]]=[i//3,i%3]dest_dic[dest_map[i]]=[i//3,i%3]#print(src_map[i],dest_map[i])for i in range(len(src_map)):cost = cost + abs(src_dic[code_n[i]][0]-dest_dic[code_n[i]][0])+abs(src_dic[code_n[i]][1]-dest_dic[code_n[i]][1])return costdef calcDistH1(self, src_map, dest_map):#采用不一样数字个数和作为估值函数cost = 0for i in range(len(src_map)):if(src_map[i]!=dest_map[i]):cost =cost +1return costdef calcDistH2(self, src_map, dest_map):#BFSreturn 0def moveMap(self, src_map, dest_map):#给定输入状态和输出状态，判断怎么移动的n = int(math.sqrt(len(self.code)+1))#得到行列大小src_pos = src_map.index('0')dest_pos = dest_map.index('0')d = src_pos - dest_posif d==-n:return "down"elif d == n:return "up"elif d == 1:return "left"elif d == -1:return "right"

test=Astar(['0','1','2','3','4','5','6','7','8'])#类的实例化，传入九个符号
test.salvePuzzle("876543210","012345678")#输入输出状态
print('path:',len(test.res))#最短路径长度
for i in test.res:print(i)#打印走的方案
print(test.count_extendnode)#扩展结点
print(test.count_sumnode)#生成节点

#给出一个转化后的c++代码，思路一致，不注释啦
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
struct Node
{string status;ll cost;Node(string _status, ll _cost){status = _status;cost = _cost;}bool operator<(const Node &other) const{// 定义＜运算符优先级小先输出return cost > other.cost;}
};class Astar
{
private:string code;vector<pair<string, string>> res;ll iter;public:void output(){cout << res.size() << endl;for (auto i = res.begin(); i != res.end(); i++){cout << (*i).first << " " << (*i).second << endl;}}Astar(string _code){code = _code;iter = 0;}void solve(string &start, string &goal){priority_queue<Node, vector<Node>> frontier;frontier.push(Node(start, 0));// 方向数组string dirs[4];dirs[0] = "up";dirs[1] = "down";dirs[2] = "left";dirs[3] = "right";string N = "None";map<string, ll> dict_depth;dict_depth[start] = 0;set<string> close;map<string, string> came_from;came_from[start] = "None";int n = sqrt((int)code.size());int count_status = 0;while (!frontier.empty()){Node current = frontier.top();frontier.pop();count_status++;cout << "状态" << count_status << ":" << "\n";for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){cout << current.status[3 * i + j] << " ";}cout << "\n";}cout<<"g值 "<<dict_depth[current.status]<<" h值 "<<calcDistH(current.status, goal)<<"\n";while (close.find(current.status) != close.end()){current = frontier.top();frontier.pop();}if (current.status == goal){cout << "找到解！迭代次数为" << iter << endl;break;}close.insert(current.status);for (int i = 0; i < 4; ++i){string next_status = move(current.status, dirs[i]);if (next_status == N)continue;else{iter++;ll depth = dict_depth[current.status] + 1;if (dict_depth.find(next_status) != dict_depth.end()){if (depth < dict_depth[next_status]){dict_depth[next_status] = depth;came_from[next_status] = current.status;if (close.find(next_status) != close.end()){close.erase(next_status);frontier.push(Node(next_status, depth + calcDistH(next_status, goal)));}}}else{dict_depth[next_status] = depth;frontier.push(Node(next_status, depth + calcDistH(next_status, goal)));came_from[next_status] = current.status;}}}}string s = goal;if (came_from.find(s) == came_from.end()){cout << "未找到解！迭代次数为" << iter << endl;return;}while (came_from[s] != N){res.push_back(make_pair(s, moveMap(came_from[s], s)));s = came_from[s];}reverse(res.begin(), res.end());}ll calcDistH(string &src, string &dest){ll cost = 0;/* map<char, pair<int, int>> src_mp;map<char, pair<int, int>> dest_mp;for (int i = 0; i < src.size(); ++i){src_mp[src[i]] = make_pair(i / 3, i % 3);dest_mp[dest[i]] = make_pair(i / 3, i % 3);}for (int i = 0; i < src.size(); ++i){cost += (abs(src_mp[code[i]].first - dest_mp[code[i]].first) + abs(src_mp[code[i]].second - dest_mp[code[i]].second));} */return cost;}string move(string &status, string &direction){int n = sqrt((int)code.size());int flag = status.find('0');int x0 = flag / 3;int y0 = flag % 3;string res = status;if (direction == "up"){if (x0 == 0){return "None";}else{swap(res[flag], res[flag - 3]);return res;}}else if (direction == "down"){if (x0 == n - 1){return "None";}else{swap(res[flag], res[flag + 3]);// cout<<res;return res;}}else if (direction == "left"){if (y0 == 0){return "None";}else{swap(res[flag], res[flag - 1]);return res;}}else{if (y0 == n - 1){return "None";}else{swap(res[flag], res[flag + 1]);return res;}}}string moveMap(string &src_map, string &dest_map){int n = sqrt((int)code.size());int src_pos = src_map.find('0');int dest_pos = dest_map.find('0');int d = src_pos - dest_pos;if (d == -n)return "down";else if (d == n)return "up";else if (d == 1)return "left";elsereturn "right";}
};main()
{Astar myAstar("012345678");string a = "742065831";string b = "012345678";myAstar.solve(a, b);myAstar.output();
}

参考 A*算法 原文链接：A*启发式搜索算法详解 人工智能 - 小兔子来运动 - 博客园 (cnblogs.com)

参考 如何通透理解：BFS和DFS优先搜索算法 原文链接：https://blog.csdn.net/v_JULY_v/article/details/6111353

参考 AdaMeta作者八数码问题 原文链接：https://blog.csdn.net/OCEANtroye/article/details/103859243