A*算法 计算九宫格数字移动问题

今天进行程序的测试，发现运算速度相当缓慢，当使用876，543，210这个矩阵变换，运算了130k＋步骤，耗时有半个小时多。经过简单 计算，九个格子放入九个数，就有A99种排列组合，结果是360K＋,所以当程序运行到100K＋的时候，我还是在耐心等待，不过帮我测试的同学可没 有我的耐心，早早得都关了。-_-|| 所以在昨天晚上抱着尝试的心态，写了A*算法。该算法就是有序搜索，与盲目搜索的不同之处就是多了一个跟 据一定的策略，从open表中找一个最容易产生结果的结点进行扩展。在这个程序中，该策略就是找到与目标状态数字的排列最接近的结点进行扩展。 结果再输入 876,543,210 只有经过700＋,改进速度提升了几个数量级，结果还是另人满意的。

//this is main.cpp
// 九宫格 数字移动就是 将一个九个格子中初始填充1～8 然后经过移动 使之变成目标状态
/*
     初始状态          1 2 3             1 2 3 
	                   4   5      ->     4 5 6 
				       7 8 6             7 8 

*/
//~

//#include“data.h“
#include“search.h“

void main（）
{
	cout << “********************************************************************************“ << endl;
    cout << “this program is about the movement of number. In details the matrix‘length is 3“ << endl;
    cout << “and the width is 3.Now input 8 numbers from 1 to 8 （0 means blank）. The program“  << endl;
    cout << “will move these 8 numbers from initial state to final state automatically       “ << endl << endl;
    cout << “For example:“ << endl;
    cout << “1 2 3             1 2 3  “ << endl;
    cout << “4 0 5      ->     4 5 6  “ << endl;
    cout << “7 8 6             7 8 0  “ << endl;
	cout << “Now please the 8 numbers （0~8） and blank （the blank is zero） “ << endl;

	initial（head）;
	int i j;
	for（i = 0; i < 3; i++）
		for（j = 0; j < 3; j++）
		{
			cout << “（“ << i + 1 << ““ << j + 1 << “） =:   “;
			cin >> head.grid[i][j];
		}    
	findzore（head）;
    findweight（head）;

	pnode p = &head;	
	pnode r = search（p）;

	if（ r != NULL）
    {
		cout << “^_^ found！！“ << endl;
        output（r）;
    }
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       6706  2008-11-26 22:35  data.h

     文件       1360  2008-11-26 22:38  main.cpp

     文件       1874  2008-11-25 11:05  readme.txt

     文件       5067  2008-11-26 22:34  search.h

----------- ---------  ---------- -----  ----

                15007                    4