八数码问题

• • 1、问题描述
  • 算法介绍
  • 解题思路

1、问题描述

用有界深度优先搜索方法解决八数码难题。

初始状态为S0，目标状态是Sg，要求寻找从初始状态到目标状态的路径。

搜索顺序：左上右下（这里以空框为目标）

算法介绍

有界深度优先算法DFS

解题思路

定义一个Item类，如图：

由于深度遍历符合先进后出（FILO）数据结构，所以定义open表为堆栈结构（stack）

open表：得到所有待扩展结点。

close表：存储已扩展结点间的扩展关系，用于输出路径。