八数码的问题描述为:
在 3*3 的棋盘上, 摆有八个棋子, 每个棋子上标有 1 至 8 的某一数字. 棋盘中留有一个空格, 空格用 - 1 来表示. 空格周围的棋子可以移到空格中. 要求解的问题是: 给出一种初始布局 (初始状态) 和目标布局, 找到一种最少步骤的移动方法, 实现从初始布局到目标布局的转变.
解决八数码的方法很多, 本文采用 1. 广度优先搜索的策略, 和 A 星算法两种比较常用的算法思想解决此问题
广度优先搜索的策略一般可以描述为以下过程:
状态空间的一般搜索过程
OPEN 表: 用于存放刚生成的节点
CLOSE 表: 用于存放将要扩展或已扩展的节点
1) 把初始节点 S0 放入 OPEN 表, 并建立只含 S0 的图, 记为 G
OPEN:=S0,G:=G0(G0=S0)
2) 检查 OPEN 表是否为空, 若为空则问题无解, 退出
LOOP:IF(OPEN)=() THEN EXIT(FAIL)
3) 把 OPEN 表的第一个节点取出放入 CLOSE 表, 记该节点为节点 n
N:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSE)
4) 观察节点 n 是否为目标节点, 若是, 则求得问题的解, 退出
IF GOAL(n) THEN EXIT(SUCCESS)
5) 扩展节点 n, 生成一组子节点. 把其中不是节点 n 先辈的那些子节点记作集合 M, 并把这些节点作为节点 n 的子节点加入 G 中.
EXPAND(n)-->M(mi),G:=ADD(mi,G)
7) 转第 2 步
下面贴出代码:
- import time
- import copy
- class list():
- def __init__(self,info):
- self.info = info
- self.front = None
- class Solution():
- def __init__(self):
- self.open = []
- self.closed = []
- self.co = 0
- def msearch(self,S0, Sg):
- head = list(S0)
- self.open.append(head)
- while self.open:
- n = self.open.pop(0)
- self.co += 1
- print('取得节点 n:',n.info)
- if n.info == Sg:
- print('得到问题的解!')
- print('一共进行了',self.co,'次查找')
- print('该问题的解为:') #对 n 进行
- while n:
- print(n.info)
- n = n.front
- return
- if n in self.closed:
- #节点判定是否为扩展问题
- print('该结点不可扩展')
- else:
- print('该节点可扩展')
- #扩展节点 n,
- #将其子节点放入 open 的尾部,
- #为每一个子节点设置指向父节点的指针
- nkongdi, nkongdj = 0, 0
- for i in range(3):
- for j in range(3):
- if n.info[i][j] == -1:
- nkongdi = i
- nkongdj = j
- ln,un,rn,dn =copy.deepcopy(n.info),copy.deepcopy(n.info),copy.deepcopy(n.info),copy.deepcopy(n.info)
- if nkongdj != 0: #right
- rn[nkongdi][nkongdj],rn[nkongdi][nkongdj-1] = rn[nkongdi][nkongdj-1],rn[nkongdi][nkongdj]
- rn = self.link(n,rn)
- if rn not in self.closed:
- self.open.append(rn)
- if nkongdi != 0: #down
- dn[nkongdi][nkongdj],dn[nkongdi-1][nkongdj] = dn[nkongdi-1][nkongdj],dn[nkongdi][nkongdj]
- dn = self.link(n,dn)
- if dn not in self.closed:
- self.open.append(dn)
- if nkongdj != 2: #left
- ln[nkongdi][nkongdj],ln[nkongdi][nkongdj+1] = ln[nkongdi][nkongdj+1],ln[nkongdi][nkongdj]
- ln = self.link(n,ln)
- if ln not in self.closed:
- self.open.append(ln)
- if nkongdi != 2: #up
- un[nkongdi][nkongdj],un[nkongdi+1][nkongdj] = un[nkongdi+1][nkongdj],un[nkongdi][nkongdj]
- un = self.link(n,un)
- if un not in self.closed:
- self.open.append(un)
- self.closed.append(n)
- def link(self, n ,willn):
- willnn = list(willn)
- willnn.front = n
- return willnn
- if __name__ == '__main__':
- S0 = [[2,8,3],
- [1,-1,4],
- [7,6,5]]
- S1 = [[1,2,3],
- [8,-1,4],
- [7,6,5]]
- Solution().msearch(S0,S1)
代码的一些问题:
1. 对于八数码这种状态, 可以采用一些常用的压缩策略来减少对内存空间的使用. 本文为简单其间, 并为采用压缩策略, 直接以数组表示.
2. 对于查找 n 的后继节点, 应该是可以采用一个循环来减少代码冗余的.
此方法优点, 缺点:
1. 完备的策略 ->必定会找到一个解
2. 找到的解必定是路径最短的解
3. 盲目性大, 搜索效率低
为了解决以上, 盲目性大, 搜索效率低的问题: 我们引出 A 算法. A 算法的原理如下:
A* [1] (A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法, 也是许多其他问题的常用启发式算法. 注意 -- 是最有效的直接搜索算法, 之后涌现了很多预处理算法(如 ALT,CH,HL 等等), 在线查询效率是 A * 算法的数千甚至上万倍.
公式表示为: f(n)=g(n)+h(n),
其中, f(n) 是从初始状态经由状态 n 到目标状态的代价估计,
g(n) 是在状态空间中从初始状态到状态 n 的实际代价,
h(n) 是从状态 n 到目标状态的最佳路径的估计代价.
可以看出, A 星算法比上述算法的最大的区别, 就是多了这个 估价函数 f(n) = 实际代价 g(n ) + 估计代价 h(n)
A * 算法的好处如下:
其实 A 算法也是一种最好优先的算法
只不过要加上一些约束条件罢了. 由于在一些问题求解时, 我们希望能够求解出状态空间搜索的最短路径, 也就是用最快的方法求解问题, A 就是干这种事情的!
我们先下个定义, 如果一个估价函数可以找出最短的路径, 我们称之为可采纳性. A 算法是一个可采纳的最好优先算法. A 算法的估价函数可表示为:
f'(n) = g'(n) + h'(n)
这里, f'(n)是估价函数, g'(n)是起点到节点 n 的最短路径值, h'(n)是 n 到目标的最短路经的启发值. 由于这个 f'(n)其实是无法预先知道的, 所以我们用前面的估价函数 f(n)做近似. g(n)代替 g'(n), 但 g(n)>=g'(n)才可 (大多数情况下都是满足的, 可以不用考虑),h(n) 代替 h'(n), 但 h(n)<=h'(n)才可(这一点特别的重要). 可以证明应用这样的估价函数是可以找到最短路径的, 也就是可采纳的. 我们说应用这种估价函数的最好优先算法就是 A 算法.
举一个例子, 其实广度优先算法就是 A 算法的特例. 其中 g(n)是节点所在的层数, h(n)=0, 这种 h(n)肯定小于 h'(n), 所以由前述可知广度优先算法是一种可采纳的. 实际也是. 当然它是一种最臭的 A * 算法.
再说一个问题, 就是有关 h(n)启发函数的信息性. h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件, 如果信息越多或约束条件越多则排除的节点就越多, 估价函数越好或说这个算法越好. 这就是为什么广度优先算法的不甚为好的原因了, 因为它的 h(n)=0, 没有一点启发信息. 但在游戏开发中由于实时性的问题, h(n)的信息越多, 它的计算量就越大, 耗费的时间就越多. 就应该适当的减小 h(n)的信息, 即减小约束条件. 但算法的准确性就差了, 这里就有一个平衡的问题.
总结下来, 其实就是 A 算法的重点为: 在众多的估计代价函数中的最优的即为 A(需证明是最优的)
有了以上的一些结论, 可以迅速的改改上述代码, 得到 A * 算法:
- import time
- import copy
- class list():
- def __init__(self,info):
- self.info = info
- self.fn = 0 #估价: 越小越好
- self.front = None
- class Solution():
- def __init__(self):
- self.open = []
- self.closed = []
- self.co = 0
- #A 算法的重点: 估价函数 f(n) = 实际代价 g(n ) + 估计代价 h(n)
- #A * 算法的重点为: 在众多的估计代价函数中的最优的即为 A*(需证明是最优的)
- def Asearch(self,S0, Sg):
- head = list(S0)
- head.fn = self.getfn(head,Sg)
- self.open.append(head)
- while self.open:
- #对 open 表的全部节点按照 fn 从小到大排序~~~~
- self.open.sort(key=lambda ele:ele.fn) #默认从小到大
- n = self.open.pop(0)
- self.co += 1
- print('取得节点 n:',n.info)
- if n.info == Sg:
- print('得到问题的解!')
- print('一共进行了',self.co,'次的查找')
- print('该问题的解为:') #对 n 进行
- while n:
- print(n.info)
- n = n.front
- return
- if n in self.closed:
- #节点判定是否为扩展问题
- print('该结点不可扩展')
- else:
- print('该节点可扩展')
- #扩展节点 n,
- #将其子节点放入 open 的尾部,
- #为每一个子节点设置指向父节点的指针
- nkongdi, nkongdj = 0, 0
- for i in range(3):
- for j in range(3):
- if n.info[i][j] == -1:
- nkongdi = i
- nkongdj = j
- ln,un,rn,dn =copy.deepcopy(n.info),copy.deepcopy(n.info),copy.deepcopy(n.info),copy.deepcopy(n.info)
- if nkongdj != 0: #right
- rn[nkongdi][nkongdj],rn[nkongdi][nkongdj-1] = rn[nkongdi][nkongdj-1],rn[nkongdi][nkongdj]
- rn = self.link(n,rn)
- if rn not in self.closed:
- #计算子节点估值~~~
- rn.fn = self.getfn(rn,Sg)
- self.open.append(rn)
- if nkongdi != 0: #down
- dn[nkongdi][nkongdj],dn[nkongdi-1][nkongdj] = dn[nkongdi-1][nkongdj],dn[nkongdi][nkongdj]
- dn = self.link(n,dn)
- if dn not in self.closed:
- dn.fn = self.getfn(dn,Sg)
- self.open.append(dn)
- if nkongdj != 2: #left
- ln[nkongdi][nkongdj],ln[nkongdi][nkongdj+1] = ln[nkongdi][nkongdj+1],ln[nkongdi][nkongdj]
- ln = self.link(n,ln)
- if ln not in self.closed:
- ln.fn = self.getfn(ln,Sg)
- self.open.append(ln)
- if nkongdi != 2: #up
- un[nkongdi][nkongdj],un[nkongdi+1][nkongdj] = un[nkongdi+1][nkongdj],un[nkongdi][nkongdj]
- un = self.link(n,un)
- if un not in self.closed:
- un.fn = self.getfn(un,Sg)
- self.open.append(un)
- self.closed.append(n)
- def link(self, n ,willn):
- willnn = list(willn)
- willnn.front = n
- return willnn
- def h(self, ninfo,Sg):
- #将不再位的 A 算法和 A * 算法个数, 作为启发信息
- enlight = 0
- for i in range(3):
- for j in range(3):
- if ninfo[i][j] != Sg[i][j]:
- enlight += 1
- return enlight
- def g(self,n):
- #g(n) = d(n)
- depth = 0
- while n:
- #print(n.info)
- n = n.front
- depth += 1
- return depth
- def getfn(self, n ,Sg):
- #传入进的是一个 listn
- return self.g(n) + self.h(n.info,Sg)
- if __name__ == '__main__':
- S0 = [[2,8,3],
- [1,-1,4],
- [7,6,5]]
- S1 = [[1,2,3],
- [8,-1,4],
- [7,6,5]]
- Solution().Asearch(S0,S1)
可以看出 A 星算法最为重要的就是启发函数 h(n)的选取, h(n)选取的好坏直接关系到了 A 星算法的好坏.
ps:
A * 算法也有一些优化, 有兴趣的同学也可以看一下 - - ~
来源: http://www.bubuko.com/infodetail-2775239.html