状态空间法解决八数码难题
实验内容
用状态空间法解决八数码难题，采用 盲目式搜索算法（宽度优先搜索、深度优先搜索）。
其中，八数码难题指的是：在 $3×3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。当你真正去解决他的时候，发现也并不是很难。
实验原理
状态空间法：
所谓状态空间法，就是描述某一类事物在不同时刻所处于的信息状况。当状态发生变化时，亦即进行了操作，即指状态与状态之间的关系。
问题的状态空间可以用一个三元序组来表示<S、F、G>：
$S$：问题的全部初始状态的集合
$F$：操作的集合
$G$：目标状态的集合
其中，利用状态空间法来求解问题的具体思路和步骤：
- 设定状态变量及确定值域。
- 确定状态组，分别列出初始状态集和目标状态集。
- 定义并确定操作集。
- 估计全部状态空间数，并尽可能列出全部状态空间或予以描述之。
- 当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。
盲目式搜索：
盲目搜索方法又叫非启发式搜索，是一种无信息搜索，一般只适用于求解比较简单的问题，盲目式搜索通常是按预定的搜索策略进行搜索，而不会考虑到问题本身的特性。常用的盲目式搜索有宽度优先搜索和深度优先搜索。
盲目搜索算法是不使用领域知识的不知情搜索算法，。这些方法假定不知道状态空间的任何信息。其中的 3 钟主要算法是：深度优先搜索$（DFS）$、广度优先搜索$（BFS）$和迭代加深$（DFS-ID）$的深度优先搜索。这些算法都具有如下的两个性质：
1.它们不使用启发式估计。如果使用启发式估计，那么搜索将沿着最优希望得到解决方案的路径向前进。
2.它们的目标是找出给定问题的某个解。这些算法中的一些算法试图去寻找最优解，这意味着搜索时间增加，但是如果打算多次使用最优解，那么额外的工作是值得的。
在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可以较快的得到问题解。但若目标节点不再该分支上，且该分支又是一个无穷分支，那么则不可能得到解。（对于这种情况，设置一定深度的搜索可以比较有效的解决这个问题。）所以，深度优先搜索是不完备的搜索。
广度优先搜索：
广度优先搜索算法（缩写为 $BFS$），又称为宽度优先搜索，是一种图形搜索算法。简单来说，$BFS$ 是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问或找到了目标节点，则算法终止，广度优先搜索的实现一般采用 Open-closed 表。
$BFS$ 是一种暴力搜索算法，目的是系统地展开并检查图中的所有节点以找寻结果。换句话说，它并不去考虑结果的可能存在的位置，而是彻底地搜索整张图，知道找到结果位置。因为，$BFS$ 并不使用经验法则算法。
从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实现里，其邻居节点尚未被检验过的节点会被放置在一个被称为 $open$ 的容器中（例如队列或是列表），而被检验过的节点则被放置在被称为 $closed$ 的容器中。（open-closed表）
空间复杂度
| 因为所有节点都必须被存储，因此 $BFS$ 的空间复杂度为$O( | V | + | E | )$，其中 $ | V | $ 是节点的数目，而是 $ | E | $ 图中边的数目。注：另一种说法称 $BFS$ 的空间复杂度为 $O(B^{{M}})$，其中 $B$ 是最大分支系数，而 $M$ 是树的最长路径长度。由于对空间的大量需求，因此 $BFS$ 并不适合解非常大的问题，对于类似的问题，应用 $IDDFS$ 以达节省空间的效果。 |
时间复杂度
| 最差情形下，$BFS$ 必须查找所有到可能节点的所有路径，因此其时间复杂度为$O( | V | + | E | )$，其中 $ | V | $ 是节点的数目，而 $ | E | $ 是图中边的数目。 |
完全性
广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则 $BFS$ 一定会找到。然而，若目标不存在，且图为无限大，则 $BFS$ 将不收敛（不会结束）。
最佳解
若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，$BFS$ 并不一定回传最佳解。这是因为当图形为加权图（亦即各边长度不同）时，$BFS$ 仍然回传从根节点开始，经过边数目最少的解；而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，$BFS$ 的改良算法成本一致搜索法来解决。然而，若非加权图形，则所有边的长度相等，$BFS$ 就能找到最近的最佳解。
深度优先搜索
深度优先搜索算法$（DFS）$，是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点 $v$ 的所在边都己被探寻过，搜索将回溯到发现节点 $v$ 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略。
实验代码
通过函数判断初始情况是否可解。
def is_solvable(): #判断初始情况是否有解
state = Starting_states
counts = 0
for i in range(0, 9, 1):
for j in range(0, 9, 1):
if i == j or state[i] == 0 :
continue
if j > i and state[j] < state[i]:
counts += 1
if counts % 2 == 0: #偶数
return True
else:
return False
若情况可行，则将下一步可行的走法加入列表中，最后返回 $results$ 列表。
def generateNextStates(states): #最多可以有4种情况
temp_arr = []
temp_arr = states.copy()
index = states.index(0)
index_i = index // 3
index_j = index % 3
print(index_i, index_j)
results = []
temp = 0
global temp_y
global temp_x
if index_i - 1 >= 0 and (index_i - 1 != temp_x and index_j != temp_y): #上
#temp_arr[index_i][index_j], temp_arr[index_i - 1][index_j] =temp_arr[index_i - 1][index_j], temp_arr[index_i][index_j] #交换0 和 X 的位置
#temp_arr[index_i * 3 + index_j], temp_arr[(index_i - 1) * 3 + index_j] = temp_arr[(index_i - 1) * 3 + index_j], temp_arr[index_i * 3 + index_j]
temp = temp_arr[index_i * 3 + index_j]
temp_arr[index_i * 3 + index_j] = temp_arr[(index_i - 1) * 3 + index_j]
temp_arr[(index_i - 1) * 3 + index_j] = temp
results.append(temp_arr)
temp_arr = states.copy()
if index_i + 1 < 3 and (index_i + 1 != temp_x and index_j != temp_y): #下
#temp_arr[index_i][index_j], temp_arr[index_i + 1][index_j] =temp_arr[index_i + 1][index_j], temp_arr[index_i][index_j]
temp_arr[index_i + index_j], temp_arr[(index_i + 1) * 3 + index_j] = temp_arr[(index_i + 1) * 3 + index_j], temp_arr[index_i + index_j]
results.append(temp_arr)
temp_arr = states.copy()
if index_j - 1 >= 0 and (index_i != temp_x and index_j - 1 != temp_y): #左
#temp_arr[index_i][index_j], temp_arr[index_i][index_j - 1] = temp_arr[index_i][index_j - 1], temp_arr[index_i][index_j]
temp_arr[index_i * 3 + index_j], temp_arr[index_i * 3 + index_j - 1] = temp_arr[index_i * 3 + index_j - 1], temp_arr[index_i * 3 + index_j]
results.append(temp_arr)
temp_arr = states.copy()
if index_j + 1 < 3 and (index_i != temp_x and index_j + 1 != temp_y): #右
#temp_arr[index_i][index_j], temp_arr[index_i][index_j - 1] = temp_arr[index_i][index_j - 1], temp_arr[index_i][index_j]
temp_arr[index_i * 3 + index_j], temp_arr[index_i * 3 + index_j + 1] = temp_arr[index_i * 3 + index_j + 1], temp_arr[index_i * 3 + index_j]
results.append(temp_arr)
temp_x = index_i
temp_y = index_j # 记录当前的位置， 避免重复
print()
return results
通过递归实现 $DFS$ 的搜索，生成所有合理的走法，并在每一次递归过程中判断是否达到目标状态。
def DFS_Search(states, depth = 0): #递归实现
global flag
#if isDestinationStates()
for each_state in states:
move_path.append(each_state)
printState(each_state)
if isDestinationStates(each_state):
print("目标状态为:")
#print(each_state)
printState(each_state)
print("搜索完成")
flag = 1
return
if depth == 10: #若超过一定深度若未找到， 截掉
return
next_states = generateNextStates1(each_state)
#print(next_states)
DFS_Search(next_states, depth + 1)
#move_path.pop(-1)
if flag == 1: # 已找到目标状态，不断进行跳出
return
通过栈来实现 $DFS$ 的搜索，每次从栈头取出一个元素，并判断其是否符合目标状态，若不符合，寻找下一步走法；当找到下一步可行的走法时，将状态压入栈中。
Stack = []
def DFS_search1(states): #栈实现
#for each_state in states: #通过列表来模拟栈的行为~
# for val in states:
# Stack.append(val) #初始状态压入栈中，此处顺序无关，可用 append
Stack.append(states)
while len(Stack) != 0:
#while True:
#print("栈为：",Stack)
each_state = Stack.pop(0) #出栈
#print(each_state)
printState(each_state)
if isDestinationStates(each_state): #找到目标状态
print("目标状态为:")
print(each_state)
return
next_states = generateNextStates1(each_state)
for val in next_states:
Stack.insert(0, val) #进行入栈， 实现先进后出(放在队头）
if Stack is None:
return "未查询到"
通过队列来实现 $BFS$ 搜索。
def BFS_Search(states): #队列实现
for each_state in states:
printState(each_state)
if isDestinationStates(each_state):
print("目标状态为：")
printState(each_state)
return
#next_states = generateNextStates(each_state)
next_states = generateNextStates1(each_state)
for each in next_states:
states.append(each) #添加到列表尾部， 实现先进先出
全部代码如下：
#-*-coding:UTF-8 -*-
Starting_states = [2, 8, 3,
1, 6, 4,
7, 0, 5]
ending_states = [1, 2, 3,
8, 0, 4,
7, 6, 5]
#ending_states = [2, 8, 3, 1, 0, 4, 6, 5, 7]
move_direction = ['up', 'down', 'left', 'right']
global temp_x
temp_x = -1
global temp_y
temp_y = -1 #避免重复重复重复
#DFS_states = []
#BFS_states = []
move_path = [] #将到达目标状态所经历的路径记录下来
def is_solvable(): #判断初始情况是否有解
state = Starting_states
counts = 0
for i in range(0, 9, 1):
for j in range(0, 9, 1):
if i == j or state[i] == 0 :
continue
if j > i and state[j] < state[i]:
counts += 1
if counts % 2 == 0: #偶数
return True
else:
return False
pass
def isDestinationStates(state):
for i in range(0, 3, 1):
for j in range(0, 3, 1):
if state[i * 3 + j] != ending_states[i * 3 + j]:
return False
return True
temp_x = -1
def generateNextStates(states): #最多可以有4种情况
temp_arr = []
temp_arr = states.copy()
index = states.index(0)
index_i = index // 3
index_j = index % 3
print(index_i, index_j)
results = []
temp = 0
global temp_y
global temp_x
if index_i - 1 >= 0 and (index_i - 1 != temp_x and index_j != temp_y): #上
#temp_arr[index_i][index_j], temp_arr[index_i - 1][index_j] =temp_arr[index_i - 1][index_j], temp_arr[index_i][index_j] #交换0 和 X 的位置
#temp_arr[index_i * 3 + index_j], temp_arr[(index_i - 1) * 3 + index_j] = temp_arr[(index_i - 1) * 3 + index_j], temp_arr[index_i * 3 + index_j]
temp = temp_arr[index_i * 3 + index_j]
temp_arr[index_i * 3 + index_j] = temp_arr[(index_i - 1) * 3 + index_j]
temp_arr[(index_i - 1) * 3 + index_j] = temp
results.append(temp_arr)
temp_arr = states.copy()
if index_i + 1 < 3 and (index_i + 1 != temp_x and index_j != temp_y): #下
#temp_arr[index_i][index_j], temp_arr[index_i + 1][index_j] =temp_arr[index_i + 1][index_j], temp_arr[index_i][index_j]
temp_arr[index_i + index_j], temp_arr[(index_i + 1) * 3 + index_j] = temp_arr[(index_i + 1) * 3 + index_j], temp_arr[index_i + index_j]
results.append(temp_arr)
temp_arr = states.copy()
if index_j - 1 >= 0 and (index_i != temp_x and index_j - 1 != temp_y): #左
#temp_arr[index_i][index_j], temp_arr[index_i][index_j - 1] = temp_arr[index_i][index_j - 1], temp_arr[index_i][index_j]
temp_arr[index_i * 3 + index_j], temp_arr[index_i * 3 + index_j - 1] = temp_arr[index_i * 3 + index_j - 1], temp_arr[index_i * 3 + index_j]
results.append(temp_arr)
temp_arr = states.copy()
if index_j + 1 < 3 and (index_i != temp_x and index_j + 1 != temp_y): #右
#temp_arr[index_i][index_j], temp_arr[index_i][index_j - 1] = temp_arr[index_i][index_j - 1], temp_arr[index_i][index_j]
temp_arr[index_i * 3 + index_j], temp_arr[index_i * 3 + index_j + 1] = temp_arr[index_i * 3 + index_j + 1], temp_arr[index_i * 3 + index_j]
results.append(temp_arr)
temp_x = index_i
temp_y = index_j # 记录当前的位置， 避免重复
print()
return results
old_states = []
def generateNextStates1(states):
temp_arr = []
temp_arr = states.copy()
index = states.index(0)
index_i = index // 3
index_j = index % 3
print(index_i, index_j)
results = []
temp = 0
global temp_y
global temp_x
if index_i - 1 >= 0 : # 上
temp = temp_arr[index_i * 3 + index_j]
temp_arr[index_i * 3 + index_j] = temp_arr[(index_i - 1) * 3 + index_j]
temp_arr[(index_i - 1) * 3 + index_j] = temp
if temp_arr in old_states:
pass
else:
results.append(temp_arr)
old_states.append(temp_arr)
#results.append(temp_arr)
temp_arr = states.copy()
if index_i + 1 < 3 : # 下
temp_arr[index_i + index_j], temp_arr[(index_i + 1) * 3 + index_j] = temp_arr[(index_i + 1) * 3 + index_j], \
temp_arr[index_i + index_j]
if temp_arr in old_states:
pass
else:
results.append(temp_arr)
old_states.append(temp_arr)
#results.append(temp_arr)
temp_arr = states.copy()
if index_j - 1 >= 0: # 左
temp_arr[index_i * 3 + index_j], temp_arr[index_i * 3 + index_j - 1] = temp_arr[index_i * 3 + index_j - 1], \
temp_arr[index_i * 3 + index_j]
if temp_arr in old_states:
pass
else:
results.append(temp_arr)
old_states.append(temp_arr)
#results.append(temp_arr)
temp_arr = states.copy()
if index_j + 1 < 3 : # 右
temp_arr[index_i * 3 + index_j], temp_arr[index_i * 3 + index_j + 1] = temp_arr[index_i * 3 + index_j + 1], \
temp_arr[index_i * 3 + index_j]
if temp_arr in old_states:
pass
else:
results.append(temp_arr)
old_states.append(temp_arr)
#results.append(temp_arr)
#temp_x = index_i
#temp_y = index_j # 记录当前的位置， 避免重复
#print()
return results
#return list(set(results).difference(set(old_states)))
# print(results)
# print(old_states)
# return (set(results) - set(old_states))
global flag
flag = 0
def DFS_Search(states, depth = 0): #递归实现
global flag
#if isDestinationStates()
for each_state in states:
move_path.append(each_state)
printState(each_state)
if isDestinationStates(each_state):
print("目标状态为:")
#print(each_state)
printState(each_state)
print("搜索完成")
flag = 1
return
if depth == 10: #若超过一定深度若未找到， 截掉
return
next_states = generateNextStates1(each_state)
#print(next_states)
DFS_Search(next_states, depth + 1)
#move_path.pop(-1)
if flag == 1: # 已找到目标状态，不断进行跳出
return
Stack = []
def DFS_search1(states): #栈实现
#for each_state in states: #通过列表来模拟栈的行为~
# for val in states:
# Stack.append(val) #初始状态压入栈中，此处顺序无关，可用 append
Stack.append(states)
while len(Stack) != 0:
#while True:
#print("栈为：",Stack)
each_state = Stack.pop(0) #出栈
#print(each_state)
printState(each_state)
if isDestinationStates(each_state): #找到目标状态
print("目标状态为:")
print(each_state)
return
next_states = generateNextStates1(each_state)
for val in next_states:
Stack.insert(0, val) #进行入栈， 实现先进后出(放在队头）
if Stack is None:
return "未查询到"
def BFS_Search(states): #队列实现
for each_state in states:
printState(each_state)
if isDestinationStates(each_state):
print("目标状态为：")
printState(each_state)
return
#next_states = generateNextStates(each_state)
next_states = generateNextStates1(each_state)
for each in next_states:
states.append(each) #添加到列表尾部， 实现先进先出
def printState(state):
for i in range(0, 3, 1):
print("[ ", end="")
for j in range(0, 3, 1):
print(state[i * 3 + j], end = " ")
print("]")
if __name__ == "__main__":
if is_solvable():
print("此状态有解")
DFS_Search([Starting_states]) #
#BFS_Search([Starting_states]) #√
#DFS_search1(Starting_states)
else:
print("无解")
pass
实验结果
如下图所示：
总结
通过这次实验，我认识了空间状态法和盲目式搜索，对深度优先搜索和广度优先搜索有了一个更加深度的了解，同时了解到了八数码难题的具体情况，包括其是否可解的判断条件，通过空位来进行判断更加方便等，收益颇丰。