用A*和IDA*解决15-Puzzle问题
完整代码见该项目仓库
1. 算法原理
与无信息搜索相对的是启发式搜索，它利用启发信息构造估价函数，来减少搜索范围，优化搜索算法。常见的无信息搜索有BFS和DFS算法，分别基于BFS和DFS，启发式搜索有A* 和 IDA*算法。
估价函数：f(x)=h(x)+g(x)
其中，g(x)是从初始结点到结点x已付出的实际代价；h(x)是从结点x到目标结点的最优路径估计代价。通过更改两者的系数占比，或添加附加值，能对搜索结点做进一步筛选，以改变搜索效率。
1、启发式函数的设计
A* 和 IDA*算法的估价函数都是：f(x)=h(x)+g(x)
对于h(x)，有以下几种情况：
设h*(x)为从x移动到目标的实际代价，则
| h(n)=0 | 只有g(n)起作用，A*演变成Dijkstra算法，保证找到最短路径 |
|---|---|
| h(n)<=h*(n) | *保证找到最短路径，且h(n)越接近h(n)，算法的搜索范围越精准，运行越快 ** |
| h(n)>h*(n) | A*不能保证找到一条最短路径，但运行更快 |
| h(n)»g(n) | 只有h(n)起作用，A*演变成BFS算法 |
在15-Puzzle问题中，在正方形网格内，空白格只能向4邻域移动，故采用曼哈顿函数作为启发式函数。将每一步棋盘状态储存为结点，则此处的h(x)为当前结点棋盘状态每个数字达到目标位置所需要的横、纵轴平移量之和。注意，此时不能将空白格（0）距离目标位置的距离计入，否则将导致h(n)>h*(n)，失去可采纳性，无法得到最短路径。
2、算法描述
1）A*
A*是在BFS的基础上，添加启发信息的启发式搜索算法。
首先，定义作为被搜索结点的抽象类。创建一个棋盘类，其主要成员有：棋盘数组（为压缩存储空间，用一维数组按行优先顺序存储数字）、从初始状态到当前状态的路径（为方便估价函数的计算，还可能含有当前路径长度、目标棋盘数组）、得到邻居结点的函数，计算曼哈顿距离和估价得分的函数。
与BFS算法类似，设置一个优先队列作为边界队列，记录访问结点的相邻结点，以估价函数的返回值为权重，权重越小、估计路径越短，优先级越高。
设置一个set类型的并查集或者字典的关闭集合，来记录已关闭的结点。
将队列中的结点依次出队，出队时将该结点的相邻按照权重大小的优先级入队，再将该结点加入关闭集合。由于A*算法是在广度优先搜索的基础上，每次择优先级最高的结点进行扩展，因此第一次扩展某点时一定是最短路径。
A*的算法思路为：
1、开始时，起点入队。
2、取队头并出队，将队头的相邻结点中不在关闭集合内的结点依次入优先级队列，将队头标记为已关闭，加入关闭集合。
3、重复第二步直到搜索到终点时结束循环，得到最优解和路径；或队列为空，代表无路径。
由于边界队列是优先级队列，并且保证不将已关闭的结点再次加入边界队列，因此当新的、更优的相邻结点遇到棋盘状态相同的旧结点已经在边界队列中时，不需要搜索到它并更新其g(x)值，只需直接入队，它会先于旧结点出队、被关闭。
2）IDA*
IDA*是在DFS的基础上，添加启发信息的启发式搜索算法。
在DFS中，假如我们不给予一个最大深度阈值，算法可能无止境地向着一个方向做无效的搜索。而IDA* 便是基于这点，在算法迭代的每一步深度优先搜索中，当某一步所有可访问结点对应的最小可估价函数值大于某个给定的阈值时，将会剪枝。
IDA* 的算法思路如下：
1、开始时，计算起点所有邻居结点的估价函数，选取估价函数最小的结点作为下一个访问结点。
2、重复步骤一，在递归过程中，若当前结点的估价函数大于阈值bound，则返回当前结点的估价得分。
3、若当前结点是目标结点，则得到最优解，返回路径。
2. 关键代码展示
1、曼哈顿函数
A* 与 IDA*都使用曼哈顿函数作为启发式函数，其算法大致如下，返回值根据具体计算需要有不同情况。
1
2
3
4
5
6
7
8
9
10
#计算曼哈顿距离
def manhatten(map):
dx = 0
dy = 0
for i in range(16):
if map[i] != 0: #跳过空白格
j = map[i]-1 #数字的目标下标比数字本身小1
dy += abs(i-j)/4
dx += abs((i % 4) - (j % 4))
return dx,dy #return dx+dy
2、判断棋盘是否有解
N是奇数时，当且仅当当前棋盘的逆序对是偶数的时候有解。
N是偶数时，当且仅当当前棋盘的逆序对数加上空格所在的行（从0开始算）是奇数的时候有解。
在15-Puzzle问题中，N=4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#通过逆序性判断有无解
def solvable(map):
cnt = 0
flag = 0
for i in range(16):
if map[i] == 0:
flag = int(i/4) #向下取整即为行数
continue
for j in range(i,16):
if map[j] == 0:
continue
if map[i] > map[j]: #说明是逆序数对
cnt+=1
return (cnt + flag) % 2 != 0
3、棋盘类
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
#设置棋盘结点
class board():
def __init__(self,map_=(),path_='',cnt_= 0): #用元组存储棋盘数组，字符串存储路径
self.map = map_
self.path = path_
self.cnt = cnt_
self.dx,self.dy = manhatten(map_) #调用曼哈顿函数
self.score = (self.dx+self.dy)*1.0143+self.cnt
#得到邻居节点
def getNeighbour(self):
for i in range(16):
if self.map[i] == 0:
break
neighbour = []
#空白格的移动方向
move = {
'left': -1,
'down': 4,
'up': -4,
'right': 1
}
#查找四个方向的相邻结点
for direc in move:
if i + move[direc] < 16 and i + move[direc] >= 0:
if i + move[direc] > i:
x,y = i,i+move[direc]
else:
x,y = i+move[direc],i
#用元组切片拼接来实现两个数字的位置交换
map_ = self.map[:x]+self.map[y:y+1]+self.map[x+1:y]+self.map[x:x+1]+self.map[y+1:]
path_ = self.path
#在路径中添加当前被替换的数字
path_ += str(map_[i]) + ' '
if solvable(map_): #假如有解才记录该相邻结点，剪枝
neighbour.append(board(map_,path_,self.cnt+1))
#在返回邻居列表时就对其权重进行排序，首要是估价得分，其次是h(x)的大小，为了避免调用曼哈顿函数耗时，采用当前实际路径长度的相反数，效果相同
return sorted(neighbour,key=lambda x:[x.score,-x.cnt])
4、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
def Astar(map):
frontier = queue.PriorityQueue()
closed = dict() #用字典作为关闭集合，存储对应结点的估价得分
#判断有无解
if solvable(map) is False:
return "No Solution"
else:
#起点入队
frontier.put((0,0,0,board(map)))
j = 0 #为比较算法效率，设置一个计数值，计算搜索过的结点
while not frontier.empty():
top = frontier.get() #取队头
node = top[3] #棋盘结点
nsco = top[0] #该结点的估价得分
print(j)
#假如当前结点在关闭集合中，并且估价得分大于集合中旧结点的估价得分，则进行剪枝
if node.map in closed and nsco > closed[node.map]:
continue
#反之，在字典中添加或更新该结点与当前估价得分的键值对
closed.update({node.map: nsco})
#若当前结点即为目标结点，返回路径
if node.map == goal:
return node.path + "\nA optimal solution " + str(node.cnt) + " moves\n" +"Searched for " + str(j) + " times!"
nei = node.getNeighbour() #取邻居结点
for n in nei:
j+=1
if n.map not in closed: #假如当前邻居节点不在关闭集合中，入队
frontier.put((n.score,-n.cnt,j,n)) #优先队列以元组内先后次序为优先次序比较，将计数值j作为第三项权重，防止有前两项权重都相同，无法比较的情况
return "Error!" #既非无解，又直到边界队列为空都未搜索到解，返回出错
5、IDA*
IDA* 算法由两部分构成，一是DFS递归函数，另一部分是IDA*在DFS基础上的启发式搜索函数。
DFS：
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
#深度遍历搜索
count = 0 #为比较算法效率，设置一个计数值，计算搜索过的结点
def dfs(path,g,bound,visited):
#判断有无解
node = list(path.keys())[-1] #路径是有序字典，取倒数第一个结点进行扩展
f = g + manhatten(node) #计算估价函数
if f > bound: #假如估价得分大于当前设定的最大深度，退出
return f
if node == goal: #找到目标解，返回
return -1
min = 9999
global count
nei = getNeighbour(node) #取依照估价得分排序的邻居结点，列表中存储的是（邻居结点棋盘状态元组，当前替换的值）
for n in nei:
#假如对于全局都未访问过当前棋盘状态，或旧结点的实际路径大于当前实际路径
if n[0] not in visited or visited[n[0]] >= g:
visited.update({n[0]:g}) #则在已访问字典中添加或更新当前棋盘状态和对应的实际路径的键值对，反之剪枝
#假如当前路径未访问过当前棋盘状态
if n[0] not in path:
path.update({n[0]:n[1]}) #更新路径
t = dfs(path,g+1,bound,visited) #继续深度遍历
count += 1
print(count,t,sep=' ')
if t == -1:
return -1
if t < min:
min = t
path.pop(n[0]) #删除当前相邻结点，准备遍历下一相邻结点
return min #返回相邻结点中超过当前bound值的估价得分中的最小值
IDA*：
1
2
3
4
5
6
7
8
9
10
11
def IDAstar(map):
bound = manhatten(map) #以曼哈顿函数的值作为初始的bound值
path = collections.OrderedDict({map:0}) #用有序字典存储路径
visited = {} #用于记录全局的已搜索结点及其最小实际代价
while(True):
t = dfs(path, 0, bound, visited)
if t == -1: #找到最优解，返回
return (path, bound)
if t > 70: #超过最大深度，退出
return ([], bound)
bound += 2 #每次递归，实际代价g+1，曼哈顿距离h也随之改变±1，因此0<=Δf(x)<=2，最大深度至多增加2
3. 创新点与优化
1、为启发式函数添加附加值（创新）
在搜索过程中，当边界队列中有估价得分相同的结点时，我们无法判断它们的优先级，冗余的、无效的搜索会导致性能的下降。并且，在大小4X4、相邻方向固定上下左右的棋盘中，估价得分相同的情况相当普遍，对搜索效率有较大影响。
为解决该问题，我们尝试为启发式函数添加附加值。
1）曼哈顿函数的返回值精度
首先，按照曼哈顿函数的定义，其结点之间横纵轴移动应以1为步长，即其曼哈顿距离应是整型数据。在PYTHON中，若没有对变量做int()强制类型转换，则默认为浮点数。经过测试，我发现返回浮点数能减少估价得分相等的概率，相比用整型数据累加，搜索效率要更高。
2）改变曼哈顿函数的系数
如果我们减少曼哈顿函数的系数，那么当搜索范围朝着目标移动的时候f将逐渐增加，而这意味着算法倾向于扩展靠近起点的结点，而不是靠近目标的结点。因此，增加曼哈顿函数的系数，能使算法倾向于扩展靠近目标的结点。
给该函数添加一个选择因子p来增加搜索效率，使h(x)*=(1.0+p).
其中，$p<\frac{最小步长}{期望的最长路径长度}$
在15-Puzzle问题的求解中，根据测例，将最优解的最大可能路径设定为70步，令$p = \frac{1}{70}≈0.0143$.
添加这个附加值的结果是，搜索的结点更少了。
3）将曼哈顿距离作为仅次于估价得分的第二权重
当估价得分f相等时，曼哈顿距离h越大，实际代价g越小，因此，要使曼哈顿距离尽可能小，避免重复调用曼哈顿函数耗时，采用当前实际代价g的相反数-g作为第二权重，作为优先级的比较信息之一。
4）添加初始-目标向量和当前-目标向量的向量叉积作为附加值
该附加值的添加使得搜索方向倾向于尽量沿起点到目标点的直线连线，提高搜索效率。
1
2
3
4
5
6
dx1 = current.x - goal.x
dy1 = current.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
heuristic += cross*k #系数由具体情况决定
此处设k = 0.0143，搜索的结点数有所减少。
2、优化空间开销
由于A*需要维护边界队列和关闭集合，其空间复杂度较高，棋盘情况较复杂时容易出现内存不足、程序跑满磁盘、不得不强行退出的状况。因此，对存储空间进行优化是相当有必要的。通过用一维元组存储棋盘数组，以及用字符串存储路径，能在一定程度上提高存储效率。
相较用列表存储棋盘数组，用元组的优点有两点：一是占据空间更小，二是元组可以直接作为哈希值进行比较与匹配，在判断与目标棋盘数组是否相等时，不必将列表数组转换为字符串或通过循环比较是否达到目标状态，同时，更方便作为字典的索引，维护关闭集合。
最开始，为求路径清晰，我在路径列表中保存了每个结点的棋盘状态，而这造成了巨大的内存开销。改为用字符串存储路径，每次添加当前替换的数字后，存储效率大大提高。
3、环检测与剪枝操作
1）对无解棋盘进行剪枝
在求邻居结点时，判断邻居结点是否有解，无解则剪枝，有解则被添加入邻居列表。经过实验检测，这能减少搜索结点。
2）用字典维持环检测，存储棋盘与最小估价得分
用字典按键索引，更便于更新最小估价得分或判断是否扩展过当前结点。
在A*算法中，用字典closed维持关闭集合，以棋盘元组和最小估价得分作为键值对。从边界队列中取队头准备进行扩展时，若当前棋盘在关闭集合中，且当前估价得分大于集合中旧结点的估价得分，则进行剪枝；反之，在字典中添加或更新该结点与当前估价得分的键值对，并进行扩展、获取邻居结点。在遍历邻居结点入队时，同样检测该邻居结点的棋盘是否在关闭集合中，是则剪枝；反之，入边界队列。
在IDA*算法中，每结点皆用有序字典path记录当前路径，以当前棋盘元组和替换数字为键值对；用一个无序字典visited记录全局状态的结点访问状态，以棋盘元组和最小实际代价g（达到该状态的最小深度）作为键值对。在遍历邻居结点时，若该结点不在visited字典中，或它在visited字典中的实际路径g’≥当前实际代价g，则在visited字典中添加或更新当前结点，反之剪枝。在搜索到目标状态时，h=0，这意味着f=g，而g必然是最小值，这能保证得到最优解。在添加邻居结点至路径中时，若已在当前路径中则剪枝，这保证不会出现结点间的死循环。