数码迷题求解算法的比较及A*算法的简单介绍

毕智超

摘 要：数码谜题源于一古老的智力游戏，是人工智能领域中的经典问题。本文着眼于8数码问题求解的具体实现。分析了数码迷题求解的搜索策略。对三种搜索算法进行了比较权衡，并对经典启发式搜索算法A*算法进行了简单介绍，介绍了该算法框架下的启发函数及Open表结构。

关键词：数码迷题；启发式搜索；A*算法；定理化判断

中图分类号：O14 文献标识码：A 文章编号：1009-0118（2011）-03-0018-01

一、引言

8数码迷题又称重排九宫，问题描述如下：用数字1~8标注的棋子摆放在一个3×3共9个格子的棋盘上，空出一个格子使棋子能在盘内水平滑动，8个符号在棋盘上的排列称为8数码的状态，游戏要求给定一个初始的状态和一个终止状态，且每次只能移动一个棋子，求从任一初始棋局变化到另一目标棋局是否有解，以及有解时的解法。

二、定理化判定可解性

按从左往右，从上到下的顺序将棋局状态表示为一个数列P=a1a2a3a4a5a6a7a8，ai为1,2…8八个数码中的一个，P是1,2…8的一个排列，称P是该棋局的状态数列。在序列P中对iaj，则称aj出现了一个逆序，元素aj的逆序数记为R(aj)。于是序列P的逆序数记为R(P)，定义为除元素0外所有元素的逆序个数之和。序列P的元素存放在数组S[1∽n×n]中。

三、搜索算法的分析比较

（一）三种搜索算法的数据结构分析。首先简单介绍下Open表和Closed的动态数据结构，前者记录当前未考察的结点，后者记录考察过的结点。扩展所得子结点按其估值的大小插入Open表中合适的位置，每次从中选出估值最小的加以扩展。……