【人工智能】八数码问题：广度搜索、深度搜索

应用广度搜索BFS和深度搜索DFS解决八数码问题，广度搜索和深度搜索都是盲目搜索，相关理论知识，算法过程：问题求解：状态空间图和盲目搜索。 参考：7种方法求解八数码问题 Python实现A*算法解决N数码问题

1.八数码问题描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中（空格上下左右移动）。要求解的问题是：给出一种初始布局（初始状态设为283104765）和目标布局（目标状态设为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

2.Python实现

首先明确初始状态，目标状态，操作集合，定义OPEN表用于存放待扩展节点：

# Initialization # Initial State and Goal State InitS0 = [[2, 8, 3], [1, 0, 4], [7, 6, 5]] GoalS = [[1, 2, 3], [8, 0, 4], [7, 6, 5]] # Set of Operations Operations = [[-1, 0], [0, -1], [1, 0], [0, 1]] # Operations = [[0, 1], [0, -1], [1, 0], [-1, 0]] # Open List Open = [] # Total Number of Nodes NodeNum = 0

定义一个节点类：

# Class of Node State class Node(object): def __init__(self, state, parent, hashval, gn): self.state = state self.parent = parent self.child = [] self.hashval = hashval self.gn = gn def __eq__(self, another): return self.hashval == another.hashval

定义的类中包括节点的状态，节点的父节点，节点的子节点，当前状态的哈希值，当前状态的代价（也就是所处的层数，每走一步代价为1）。

1.广度优先搜索

# Generate Children Node BFS def gen_child_bfs(current, goal, hashtable, openlist): N = len(current.state) for i in range(0, N): for j in range(0, N): if current.state[i][j] != 0: continue for op in Operations: x = i + op[0] if x < 0 or x >= N: continue y = j + op[1] if y < 0 or y >= N: continue childstate = copy.deepcopy(current.state) childstate[i][j], childstate[x][y] = childstate[x][y], childstate[i][j] h = hash(str(childstate)) if h in hashtable: continue hashtable.add(h) global NodeNum NodeNum += 1 gn = current.gn + 1 childnode = Node(childstate, current, h, gn) current.child.append(childnode) openlist.append(childnode)

2.深度优先搜索

深度搜索只是在生成子节点后，Open表的排序部分不同。

gn = current.gn + 1 childnode = Node(childstate, current, h, gn) current.child.append(childnode) openlist.insert(0, childnode)

3.运行结果

BFS+hash

[[2 0 3] [1 8 4] [7 6 5]] ------------------- [[0 2 3] [1 8 4] [7 6 5]] ------------------- [[1 2 3] [0 8 4] [7 6 5]] ------------------- [[1 2 3] [8 0 4] [7 6 5]] ------------------- Deepth: 4 NodeNum: 37 Runtime: 0.000997 s

DFS+hash：找到的并不是最优解

Deepth: 52718 NodeNum: 96215 Runtime: 2.317832 s