深度优先搜索，八数码问题怎么破？
上篇文章我们聊了宽度优先搜索解决八数码问题的方法，今天咱们换个思路，用深度优先搜索来试试。
深度优先的策略
深度优先搜索，就是一种一直向下的搜索策略。简单来说，就是从初始节点开始，按照生成规则生成下一级各子节点，然后检查是否出现目标节点。如果没找到，就按照最新产生的（也就是最深的）节点优先的原则，再用生成规则生成下一级子节点。
代码解析
import numpy as np
class State:
# 状态图类定义...
def getDirection(self):
return self.direction
def getNextOperation(self, operation_index):
# 获取下一个操作符...
def hasAvailableChild(self):
# 是否还有子节点未扩展...
def getChildLength(self):
# 获取子节点数量...
def showInfo(self):
# 显示状态信息...
def printState(self):
# 打印状态信息...
def getEmptyPos(self):
# 获取空格位置...
def generateNextChildNode(self, index):
# 生成下一个子节点...
def DFS_Search(self, target_state, deepthLimit):
# 深度优先搜索...
def DFS(init_node, target_state, deepthLimit = 6):
# 深度优先搜索...
if __name__ == '__main__':
symbolOfEmpty = 0 # 空格用0表示
State.symbol = symbolOfEmpty
originNode = State(np.array([[2, 8, 3], [1, 6, 4], [7, symbolOfEmpty, 5]]))
target_state = np.array([[1, 2, 3], [8, State.symbol, 4], [7, 6, 5]])
s1 = State(state=originNode.state)
searchSteps = 0
path, steps = DFS(originNode, target_state, deepthLimit = 6)
print(