用A算法解决十五数码问题

（3）性能指标

空格不计，则16宫图的某状态为数1到15的一个排列，记为

n0nln2n3n4n5n6n7n8n9n10n11n12n13n14n15。两个状态之间是否可达可以通过计算两者的逆序数来判断，若两者逆序数的奇偶性相同则可达，否则不可达。也即对于任一个目标状态节点，有(1/2)×16 !=10461394944000个状态可达该节点。据统计，单纯用A*算法要花费几个小时时间才能判断出不能达到目标状态，这时CLOSED表长度为10461394944000。但由于本程序缺陷甚多，所以算法的时间复杂度会更高。

四、个人体会

初学人工智能时，最先联想到的便是机器人，一直感觉机器人是非常智能且非常神秘的，这也令人工智能在我的思想里笼罩了一层非同寻常的面纱，非常迫切的想要了解它的内涵。经过十几学时的学习，我对人工智能已有了初步了解，也深深的被它吸引，尤其通过本次程序设计，对人工智能的学习兴趣更加浓厚了！

15数码问题是人工智能的一个经典的问题。本文中通过设计一个基于A*算法的状态空间搜索程序，对于给定的初始状态，采用f(n)=h(n)+g(n)表示以当前节点与其目标节点相应位置不相同元素的个数与搜索深度之和作为启发函数的度量，并用可视化编程语言C#来实现该问题。

在程序的设计与实现过程中，遇到了很多的问题。首先由于初学人工智能，理解上有一定的困难，对A*算法的深入学习是一个曲折的过程。其次，在程序真正的设计及实现过程中，的确需要花费大量的精力来思考，反复试验。所设计的程序能够运行，但缺陷还是非常之大的，如其中重排OPEN表时，没有进行真正意义上的重新排列，只是选出代价最小的放在最先的位置，这实际上对程序的运行效率有很大的影响。

同时通过输入大量的初始状态和目标状态发现，在一般情况下都可以找到最优的动作序列。但对某些稍微复杂的初始状态虽能得到正确解却不能完全得到最短的搜索路径，对于某些极其复杂的状态，甚至得不到解。这是有待进一步学习并改进的地方。

但本程序还是有些值得肯定之处。界面设计比较友好，容易操作。而且在程序开始时，就判断目标状态是否可达，这样可节约大量的时间。虽然很多地方设计的不尽如意，但这是针对十五数码这个具体问题的一点优化。

附录：

//Program using System;

using System.Collections.Generic; using System.Windows.Forms; namespace _15Digital {

static class Program {

///

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false); Application.Run(new Form1()); } } }

//Form1

using System;

using System.Collections;

using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text;

using System.Windows.Forms;

using System.Windows.Forms.ComponentModel; using System.Reflection; namespace _15Digital {

public partial class Form1 : Form {

public Form1() {

InitializeComponent(); }

private ArrayList result;//存储初始状态到目标状态的各个变换过程的状态 private static int currentIndex = 0;//记录初始状态到目标状态共需要的步数 ///

private void initialize() {

//定义初始态和目标态矩阵

int[][] Start_Matrix = new int[4][]; int[][] End_Matrix = new int[4][]; for (int i = 0; i < 4; i++) {

Start_Matrix[i] = new int[4]; End_Matrix[i] = new int[4]; }

//目标状态矩阵的赋值 for (int i = 0; i < 4; i++) {

for (int j = 0; j < 4; j++) {

End_Matrix[i][j] = 4 * i + j + 1; } }

End_Matrix[3][3] = 0; //获取初始状态矩阵 for (int i = 0; i < 4; i++) {

for (int j = 0; j < 4; j++) {

int k = 4 * i + j + 1;

TextBox tbox = (TextBox)this.findTextbox(\ int k2 = 16 + 4 * i + j + 1;

((TextBox)this.findTextbox(\tbox.Text.ToString ();

if (tbox.Text == \ {

MessageBox.Show(\请将所有空格填写完整！\ return; }

Start_Matrix[i][j] = Convert.ToInt32(tbox.Text); } }

//计算能否在50飞、步之内搜索到目标状态

_15Digital fifteen = new _15Digital(Start_Matrix, End_Matrix); if (fifteen.searchObject() == true) {

MessageBox.Show(\成功找到目标状态!\