共有回帖数 0 个
-
不知道为什么，昨天发的帖子，今天还没“审批”。 也许楼主们觉得，太过于简单当作“废铁”了；否则的话，就该告他们个“不恪尽职守”了。
废话不多说，还是继续贴贴子。
帖子关于是八数码的，是前段时间写的，为了给别人一些搜索的样例。 现在，事差不多完了，代码还留着，觉着放着浪费，又想自己水平过于欠缺，再加上看在C吧的初学者还是占主要，就觉得发在此处共他们学习还是不错的，仅此而已。
如果有不知道八数码的问题的， 可以上网一搜，就什么都明白了。 在这里我只用了几种算法实现，其实还有其他方法，我并没有写（如果有人需要，可能我会重新完成）。
首先分析下八数码的一些算法吧。
1： 深度优先（DFS）：
这个方法起始对八数码非常不好，问题在于搜索过于盲目，搜索深度如果没有限制，有些是根本没必要的（因为八数码的解，大部分集中在20~30步之间）。而且即使搜索到一个解，很可能不是最优解。 所以用DFS解决这个问题并不明智，不过为了显示其不好，我仍然实现，不过在程序中设置最大深度限制为100。
2： 宽度优先搜索（BFS）
宽度优先搜索，解决的还不错，经过对hash函数的优化，能使一个20~30步的解在200~300MS内解决（不过其还可以做进一步的优化）。
3： 迭代加深搜索
迭代加深搜索，可以说是吸取了宽搜和深搜的优点，同时避免了深搜搜到第一个解的不最优性，和宽搜的使用较大的内存空间。
在这里我也用迭代加深搜索， 仔细一看的人就发现，起使他只是在深搜上稍微做点“手脚”就完毕，但是其思想，虽然显而易见，可我觉得并不容易想到（指当初提出这个算法的时候）。
4： 爬山法
爬山法，经常在人工只能里面见得到，由于其高效，实现简单，所以其有时也是很有用的。但是爬山法，也有缺点，就是搜到的解只是局部最优解，而且有陷入“无解”的风险。 爬山法，顾名思意就是一直沿着“最好的方向走”直到“山顶”，就找到解。 爬山法，不像回溯， 在遍历节点时不保存其他非当前最优节点，也就是说，一旦走错了，就不能再后头搜索其他方向。
所以在我写的爬山法中，对于一个解，虽然很多100多步，但是所需的时间确实0MS左右。
5： 双向搜索
双向搜索，前后来搜，碰到头，然后一拼接就出了路径。其搜索的节点数要明显必宽搜少许多，所以在程序中，我并未对其做任何优化，他搜索一个解的时间基本上是0MS。
6：A*算法
A*算法，不用说，解决这个问题很简单。速度也快，都是0MS。具体的可以参考网上的解释。
7：DIA算法
DIA算法可以说是 A* 与 迭代搜索的结合，思想来源于迭代搜索，其实简单的说就是，迭代搜索添加了估价函数。由于时间，当初我并未用该方法实现。
第一个贴的代码是宽搜，由于在hash上做了优化，所以对hash部分做下解释：
******************************************
对于一个状态，转换为 1 2 3 4 0 5 6 7 8 这样的序列，然后分别对应权值：
0 : 8! , 1 :7! 2 : 6! , .... , 8:0 !
然后用每个数的逆序数乘上权值的和即为改状态的hash表对应的下标。
对于上序列对应的hash下标为： 4 * 8! + 0 * 7! + 0 * 6! + 0 * 5! + 0 * 4! + 0 * 3! + 0 * 2! + 0 * 1! + 0 * 0! = 161280
----------------------------------------------------------------------
另外对于这种hash值计算外，还有一个由上一个状态来推到下一个状态的hash值的规律：
假设，移动是有从空格的移动方向来看，并且设空格在序列中的位置为 i，并且是index为上一个状态的hash值，则下一个状态的hash值为：
上移：index - 3*8! + a[i-3]! * ( a[i-1] a[i-3] + a[i-2] a[i-3] ) - a[i-2]! * ( a[i-2] a[i-3] ) - a[i-1]! * ( a[i-1] a[i-3] );
下移：index + 3*8! - a[i+3]! * ( a[i+1] a[i+3] + a[i+2] a[i+3] ) + a[i+2]! * ( a[i+2] a[i+3] ) + a[i+1]! * ( a[i+1] a[i+3] );
newindex =
左移：index - 8!
右移：index + 8!
上移newindex值的计算程序如下计算(假设，Factorial[9]，分别记录了(8-i)!的值)：
newindex -= 3*40320 ;
newindex += ( p[ i - 2 ] p[ i - 3 ]) ? ( Factorial[ p[ i - 3 ] ] ) : ( - Factorial[ p[ i - 2 ] ] );
newindex += ( p[ i - 1 ] p[ i - 3 ]) ? ( Factorial[ p[ i - 3 ] ] ) : ( - Factorial[ p[ i - 1 ] ] );
下移：
newindex += 3*40320 ;
newindex -= ( p[ i + 2 ] p[ i + 3 ]) ? ( Factorial[ p[ i + 3 ] ] ) : ( - Factorial[ p[ i + 2 ] ] );
newindex -= ( p[ i + 1 ] p[ i + 3 ]) ? ( Factorial[ p[ i + 3 ] ] ) : ( - Factorial[ p[ i + 1 ] ] );
因此，对于此种hash值的计算，最多只需要3次加减法，2次比较（平均约2次加减法，3.5次比较运算）运算即可完成hash值的计算，而且这种计算出来的hash值不存在冲突。
********************************************
宽搜代码如下：
#include stdio.h
#include stdlib.h
#include windows.h
#include queue
#include stack
using namespace std;
#define HashTableSize 362880
#define NOT !
typedef struct maps
{
int detail[3][3];
int parent; // 记录父节点在hash表中的位置
int myindex; // 记录自己节点在hash表中的位置
int x, y; // 记录 空格（0）的坐标
}Map,*PMap;
Map org; // 初始状态
Map end; // 目标状态
PMap HashTable[HashTableSize]={NULL}; //hash表
char Rpath[150]; //最终的路径
int const derection[4][2] ={ { -1 , 0 } , {1, 0 }, { 0 , -1 } , { 0, 1 } } ; // 可移动的四个方向
bool FlageNew;
/**
*
* 八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）
*
**/
void input()
{
int i,j;
int sum;
for(i = 0 ; i 9 ; i ++ )
{
scanf("%1d", *org.detail + i );
if(0 == *(*org.detail + i) )
{
org.x = i / 3;
org.y = i % 3;
}
}
org.parent = -1 ;
for(i = 0 ; i 9 ; i ++ ) //计算逆序
{
if( 0 == *(*org.detail + i) )
continue;
for(j = 0 ; j i; j ++ )
if( 0 != *(*org.detail+j) && *(*org.detail + j) *(*org.detail + i) )
{
sum ++;
}
}
if( sum%2 == 0 ) // 目标状态各个数字对应的坐标位置
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3 ;
end.detail[1][0] = 4 , end.detail[1][1] = 5 , end.detail[1][2] = 6 ;
end.detail[2][0] = 7 , end.detail[2][1] = 8 , end.detail[2][2] = 0 ;
}
else
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3 ;
end.detail[1][0] = 8 , end.detail[1][1] = 0 , end.detail[1][2] = 4 ;
end.detail[2][0] = 7 , end.detail[2][1] = 6 , end.detail[2][2] = 5 ;
}
return;
}
/**
*
*检测两个状态是否一样
*
**/
inline bool IsEqual(Map a , Map b)
{
return 0 == memcmp((const void *)(*a.detail),(const void *)(*b.detail),36);
}
/**
*
* hash值的计算
*
**/
int HashValue(Map a)
{
int count ;
int i , j ;
int value =0 ;
static int pv[9]={1,1,2,6,24,120,720,5040,40320};
for(i = 0 ; i 9 ; i ++ )
{
for(j = 0, count =0 ; j i ; j ++ )
{
if( *(*a.detail+i) *(*a.detail+j) )
{
count ++;
}
}
value += pv*count;
}
return value;
}
/**
*
*状态插入到hash表中。返回的是插入到的hash表中对应的下标值
*
**/
int InsertHashTable(Map a , int parent)
{
int index = HashValue( a );
if(NULL == HashTable[index]) //如果为TURE，那么说明hash表中不存在该状态，应该插入到hash表中
{
a.parent = parent;
HashTable[index] = new Map;
*HashTable[index] = a;
FlageNew = true;
}
else
{
FlageNew = false;
}
return index;
}
/**
*
* 宽度优先搜索
*
**/
void Bfs()
{
queueMap Queue;
bool Finish = false;
org.myindex = InsertHashTable( org , -1 );
Queue.push(org);
while( false == Queue.empty() && NOT Finish )
{
Map node = Queue.front();
Queue.pop();
// printf("%dn",Queue.size());
if( true == IsEqual(node , end ) )
{
Finish = true;
end.parent = node.parent;
end.myindex = node.myindex;
continue;
}
for(int k =0 ; k 4; k ++ )
{
Map tmp = node;
tmp.x = node.x + derection[k][0],
tmp.y = node.y + derection[k][1];
if(tmp.x 0 || tmp.x 2 || tmp.y 0 || tmp.y 2 )
{
continue;
}
tmp.detail[ node.x ][ node.y ] = tmp.detail[ tmp.x ][ tmp.y ]; //移动空格
tmp.detail[ tmp.x ][ tmp.y ] = 0 ;
int tmpindex = InsertHashTable( tmp , node.myindex );
if( false == FlageNew ) //如果不是新状态的,即以前访问过改节点，不再加入队列中
{
continue;
}
tmp.parent = node.myindex;
tmp.myindex = tmpindex;
Queue.push(tmp);
}
}
return ;
}
/**
*
* 通过hash表中记录的进行查找路径
*
**/
void FindPath()
{
Map now;
stackMap Stack;
Stack.push(end);
now = end;
int count=0;
while(now.parent != -1 )
{
Stack.push(*HashTable[now.parent]);
now = Stack.top();
}
printf("共需： %d 步n",Stack.size()-1);
getchar();
while( NOT Stack.empty())
{
now = Stack.top();
Stack.pop();
for(int i =0 ; i 3; i ++ )
{
for(int j =0 ; j 3; j ++)
{
printf("%3d",now.detail[j]);
}
printf("n");
}
if(0 != Stack.size() )
{
printf("n ↓ 第%d步n",++count);
getchar();
}
}
printf("nThe End!n");
return ;
}
int main()
{
input();
long time =GetTickCount();
Bfs();
printf("计算用时：%dMSn",GetTickCount()-time);
FindPath();
return 0;
接下来的第二个代码是：
深度优先搜索（限制了他的深度为50）
#include stdio.h
#include stdlib.h
#include windows.h
#include queue
#include stack
using namespace std;
#define HashTableSize 362880
#define NOT !
#define MaxDeep 50
typedef struct maps
{
int detail[3][3];
int x, y; // 记录 空格（0）的坐标
}Map,*PMap;
Map org; // 初始状态
Map end; // 目标状态
bool HashTable[HashTableSize]={false}; //hash表
int const derection[4][2] ={ { -1 , 0 } , {1, 0 }, { 0 , -1 } , { 0, 1 } } ; // 可移动的四个方向
int Path[ MaxDeep + 1 ];
int Step;
bool Finish;
/**
*
* 八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）
*
**/
void input()
{
int i,j;
int sum;
for(i = 0 ; i 9 ; i ++ )
{
scanf("%1d", *org.detail + i );
if(0 == *(*org.detail + i) )
{
org.x = i / 3;
org.y = i % 3;
}
}
for(i = 0 ; i 9 ; i ++ ) //计算逆序
{
if( 0 == *(*org.detail + i) )
continue;
for(j = 0 ; j i; j ++ )
if( 0 != *(*org.detail+j) && *(*org.detail + j) *(*org.detail + i) )
{
sum ++;
}
}
if( sum%2 == 0 ) // 目标状态各个数字对应的坐标位置
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3 ;
end.detail[1][0] = 4 , end.detail[1][1] = 5 , end.detail[1][2] = 6 ;
end.detail[2][0] = 7 , end.detail[2][1] = 8 , end.detail[2][2] = 0 ;
}
else
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3 ;
end.detail[1][0] = 8 , end.detail[1][1] = 0 , end.detail[1][2] = 4 ;
end.detail[2][0] = 7 , end.detail[2][1] = 6 , end.detail[2][2] = 5 ;
}
return;
}
/**
*
*检测两个状态是否一样
*
**/
inline bool IsEqual(Map a , Map b)
{
return 0 == memcmp((const void *)(*a.detail),(const void *)(*b.detail),36);
}
/**
*
* hash值的计算
*
**/
int HashValue(Map a)
{
int count ;
int i , j ;
int value =0 ;
static int pv[9]={1,1,2,6,24,120,720,5040,40320};
for(i = 0 ; i 9 ; i ++ )
{
for(j = 0, count =0 ; j i ; j ++ )
{
if( *(*a.detail+i) *(*a.detail+j) )
{
count ++;
}
}
value += pv*count;
}
return value;
}
/**
*
* 深度优先搜索
*
**/
void Dfs(Map& node , int deep )
{
if(deep MaxDeep )
return ;
if( true == IsEqual( node , end) )
{
Finish = true;
Step = deep;
return ;
}
for(int k =0 ;k 4 && NOT Finish ; k ++ )
{
Map tmp = node ;
tmp.x = node.x + derection[k][0],
tmp.y = node.y + derection[k][1];
if(tmp.x 0 || tmp.x 2 || tmp.y 0 || tmp.y 2 )
{
continue;
}
tmp.detail[ node.x ][ node.y ] = tmp.detail[ tmp.x ][ tmp.y ]; //移动空格
tmp.detail[ tmp.x ][ tmp.y ] = 0 ;
int tmpindex = HashValue( tmp );
if(HashTable[ tmpindex ] == true )
continue;
HashTable[ tmpindex ] = true;
Path[ deep ] = k ;
Dfs( tmp , deep + 1) ;
HashTable[ tmpindex ] = false;
}
return ;
}
/**
*
* 输出 结果
*
**/
void output()
{
Map now = org ;
int oldx,oldy;
int count =0 ;
printf("共需要 %d 步.n", Step);
for(int i =0 ; i 3; i ++ )
{
for(int j =0 ; j 3; j ++)
{
printf("%3d",org.detail[ i ][ j ]);
}
printf("n");
}
for( int k =0 ; k Step ; k ++ )
{
oldx = now.x , oldy = now.y ;
now.x += derection[ Path[ k ] ][ 0 ], now.y += derection[ Path[ k ] ][ 1 ];
now.detail[ oldx ][ oldy ] = now.detail[ now.x ][ now.y ]; //移动空格
now.detail[ now.x ][ now.y ] = 0 ;
printf("n ↓ 第%d步n",++count);
getchar();
for(int i =0 ; i 3; i ++ )
{
for(int j =0 ; j 3; j ++)
{
printf("%3d",now.detail[ i ][ j ]);
}
printf("n");
}
}
printf("nThe End!n");
return ;
}
int main()
{
input();
long time =GetTickCount();
HashTable[ HashValue( org ) ] = true;
Dfs( org , 0 );
printf("计算用时：%dMSn",GetTickCount()-time);
output();
return 0;
}
今天贴的最后一个代码是：
迭代加深搜索
#include stdio.h
#include stdlib.h
#include windows.h
#include queue
#include stack
using namespace std;
#define HashTableSize 362880
#define NOT !
typedef struct maps
{
int detail[3][3];
int x, y; // 记录 空格（0）的坐标
}Map,*PMap;
Map org; // 初始状态
Map end; // 目标状态
bool HashTable[HashTableSize]={false}; //hash表
int const derection[4][2] ={ { -1 , 0 } , {1, 0 }, { 0 , -1 } , { 0, 1 } } ; // 可移动的四个方向
int Path[ 100 ];
int Step;
bool Finish;
int MaxDeep ;
/**
*
* 八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）
*
**/
void input()
{
int i,j;
int sum;
for(i = 0 ; i 9 ; i ++ )
{
scanf("%1d", *org.detail + i );
if(0 == *(*org.detail + i) )
{
org.x = i / 3;
org.y = i % 3;
}
}
for(i = 0 ; i 9 ; i ++ ) //计算逆序
{
if( 0 == *(*org.detail + i) )
continue;
for(j = 0 ; j i; j ++ )
if( 0 != *(*org.detail+j) && *(*org.detail + j) *(*org.detail + i) )
{
sum ++;
}
}
if( sum%2 == 0 ) // 目标状态各个数字对应的坐标位置
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3 ;
end.detail[1][0] = 4 , end.detail[1][1] = 5 , end.detail[1][2] = 6 ;
end.detail[2][0] = 7 , end.detail[2][1] = 8 , end.detail[2][2] = 0 ;
}
else
{
end.detail[0][0] = 1 , end.detail[0][1] = 2 , end.detail[0][2] = 3 ;
end.detail[1][0] = 8 , end.detail[1][1] = 0 , end.detail[1][2] = 4 ;
end.detail[2][0] = 7 , end.detail[2][1] = 6 , end.detail[2][2] = 5 ;
}
return;
}
/**
*
*检测两个状态是否一样
*
**/
inline bool IsEqual(Map a , Map b)
{
return 0 == memcmp((const void *)(*a.detail),(const void *)(*b.detail),36);
}
/**
*
* hash值的计算
*
**/
int HashValue(Map a)
{
int count ;
int i , j ;
int value =0 ;
static int pv[9]={1,1,2,6,24,120,720,5040,40320};
for(i = 0 ; i 9 ; i ++ )
{
for(j = 0, count =0 ; j i ; j ++ )
{
if( *(*a.detail+i) *(*a.detail+j) )
{
count ++;
}
}
value += pv*count;
}
return value;
}
/**
*
* 深度优先搜索
*
**/
void Dfs(Map& node , int deep )
{
if(deep MaxDeep )
return ;
if( true == IsEqual( node , end) )
{
Finish = true;
Step = deep;
return ;
}
for(int k =0 ;k 4 && NOT Finish ; k ++ )
{
Map tmp = node ;
tmp.x = node.x + derection[k][0],
tmp.y = node.y + derection[k][1];
if(tmp.x 0 || tmp.x 2 || tmp.y 0 || tmp.y 2 )
{
continue;
}
tmp.detail[ node.x ][ node.y ] = tmp.detail[ tmp.x ][ tmp.y ]; //移动空格
tmp.detail[ tmp.x ][ tmp.y ] = 0 ;
int tmpindex = HashValue( tmp );
if(HashTable[ tmpindex ] == true )
continue;
HashTable[ tmpindex ] = true;
Path[ deep ] = k ;
Dfs( tmp , deep + 1) ;
HashTable[ tmpindex ] = false;
}
return ;
}
/**
*
* 输出 结果
*
**/
void output()
{
Map now = org ;
int oldx,oldy;
int count =0 ;
printf("共需要 %d 步.n", Step);
for(int i =0 ; i 3; i ++ )
{
for(int j =0 ; j 3; j ++)
{
printf("%3d",org.detail[ i ][ j ]);
}
printf("n");
}
for( int k =0 ; k Step ; k ++ )
{
oldx = now.x , oldy = now.y ;
now.x += derection[ Path[ k ] ][ 0 ], now.y += derection[ Path[ k ] ][ 1 ];
now.detail[ oldx ][ oldy ] = now.detail[ now.x ][ now.y ]; //移动空格
now.detail[ now.x ][ now.y ] = 0 ;
printf("n ↓ 第%d步n",++count);
getchar();
for(int i =0 ; i 3; i ++ )
{
for(int j =0 ; j 3; j ++)
{
printf("%3d",now.detail[ i ][ j ]);
}
printf("n");
}
}
printf("nThe End!n");
return ;
}
int main()
{
input();
long time =GetTickCount();
HashTable[ HashValue( org ) ] = true;
for( MaxDeep = 1 ; 0 == Step ; MaxDeep ++ )
{
Dfs( org , 0 );
}
printf("计算用时：%dMSn",GetTickCount()-time);
output();
return 0;
}
下面这个代码仍然是宽度优先搜索，不过其采用了我2楼提到的对hash优化的那种方法，这个代码和5楼宽搜，思想是一样的，但是做过优化后，我机子上跑的速度提高了接近一倍。
另外： 对于八数码还有另外一个优化方法：就是采用”棋盘压缩“（不过这个优化方法用到了，另外一个A*算法上---我后面将要贴的A*并未采用）。
代码如下：
#include stdio.h
#include stdlib.h
#include windows.h
#include queue
#include stack
using namespace std;
#define HashTableSize 362881
#define NOT !
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
#define Bit char
typedef struct maps
{
Bit detail[9];
int myindex; // 记录自己节点在hash表中的位置
Bit position; // 记录 空格（0）在序列中的位置
}Map,*PMap;
Map org; // 初始状态
int EndIndex; // 目标状态
//上移 ，下移 ， 左移 ，右移
int const derection[4] ={ -3 , 3 , -1 , 1 } ; // 可移动的四个方向
int const Factorial[9] = {40320 , 5040 , 720 , 120 , 24 , 6 , 2 , 1 , 1 };
int HashTable[HashTableSize]={0}; //hash表,其中记录的是上一个父节点对应的位置
/**
*
* 八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）
*
**/
void input()
{
int i,j;
int sum , count ,index ;
for(i = 0 ; i 9 ; i ++ )
{
scanf("%1d", &org.detail[ i ] );
org.detail[ i ] || (org.position = i) ;
}
for(i = 0 ; i 9 ; i ++ ) //计算逆序
{
if( 0 == org.detail[ i ] )
continue;
for(j = 0 ; j i; j ++ )
sum += ( 0 != org.detail[ j ] && org.detail[ j ] org.detail[ i ] );
}
for( i = 0 , index = 0 ; i 9 ; i ++ ) // 计算初始状态的hash值
{
for(j = 0 , count = 0 ; j i ; j ++)
count += org.detail[ j ] org.detail[ i ] ;
index += Factorial[ org.detail[ i ] ] * count;
}
org.myindex = index + 1 ;
EndIndex = sum%2 ? 161328:322561; // 目标状态的hash值
return;
}
/**
*
* hash值的计算
* Parent : 父状态的hash值
* direct : 移动的方向
**/
inline int HashValue(Map& Parent , int& direct )
{
int i = Parent.position ;
int newindex = Parent.myindex ;
Bit *p = Parent.detail;
switch(direct)
{
case UP :
{
newindex -= 3*40320 ;
newindex += ( p[ i - 2 ] p[ i - 3 ]) ? ( Factorial[ p[ i - 3 ] ] ) : ( - Factorial[ p[ i - 2 ] ] );
newindex += ( p[ i - 1 ] p[ i - 3 ]) ? ( Factorial[ p[ i - 3 ] ] ) : ( - Factorial[ p[ i - 1 ] ] );
break;
}
case DOWN :
{
newindex += 3*40320 ;
newindex -= ( p[ i + 2 ] p[ i + 3 ]) ? ( Factorial[ p[ i + 3 ] ] ) : ( - Factorial[ p[ i + 2 ] ] );
newindex -= ( p[ i + 1 ] p[ i + 3 ]) ? ( Factorial[ p[ i + 3 ] ] ) : ( - Factorial[ p[ i + 1 ] ] );
break;
}
case LEFT : return newindex - 40320; break;
case RIGHT : return newindex + 40320; break;
}
return newindex;
}
/**
*
* 宽度优先搜索
*
**/
void Bfs()
{
queueMap Queue;
Queue.push(org);
HashTable[ org.myindex ] = -1;
while( NOT Queue.empty() )
{
Map node = Queue.front();
Queue.pop();
for(int k =0 ; k 4; k ++ )
{
Map tmp = node;
tmp.position = node.position + derection[k];
if(tmp.position 0 || tmp.position 8 || ( k 1 && tmp.position / 3 != node.position /3 ) )
continue;
tmp.myindex = HashValue( node , k );
if(0 != HashTable[tmp.myindex] ) continue;
tmp.detail[ node.position ] = tmp.detail[ tmp.position ] ; // 移动空格
tmp.detail[ tmp.position ] = 0 ;
HashTable[tmp.myindex] = node.myindex; // 状态记录到hashtable中
if( node.myindex == EndIndex ) return ;
Queue.push( tmp );
}
}
return ;
}
/**
*
* 通过hash表中记录的进行查找路径
*
**/
void FindPath()
{
int nowindex;
int count =0 ;
int nixu[9], result[9];
int i, j , k ;
stackint Stack;
Stack.push(EndIndex);
nowindex = EndIndex;
while( -1 != HashTable[ nowindex ] )
{
Stack.push(HashTable[ nowindex ]);
nowindex = HashTable[ nowindex ];
}
printf("共需： %d 步n",Stack.size()-1);
getchar();
while( NOT Stack.empty())
{
nowindex = Stack.top() - 1 ;
Stack.pop();
for( i = 0 ; i 9; i ++ ) // 计算出逆序
{
nixu = nowindex / Factorial[ i ] ;
nowindex %= Factorial[ i ];
}
memset( result , -1 , 9 *sizeof(int));
for( i =0 ; i 9 ; i ++ ) // 根据逆序计算排列
{
for( j = 0 , k = nixu ; j 9 ; j ++ )
{
if(result[j] == -1 ) k --;
if( k 0 ) break;
}
result[j] = i ;
}
for( i =0 ; i 9 ; i ++ )
{
printf("%3d",result);
if( 2 == i % 3 ) printf("n");
}
if(0 != Stack.size() )
{
printf("n ↓ 第%d步n",++count);
getchar();
}
}
printf("nThe End!n");
return ;
}
int main()
{
input();
long time =GetTickCount();
Bfs();
printf("计算用时：%dMSn",GetTickCount()-time);
FindPath();
return 0;
}
另外在我的上面所用代码，测试样例一致如下，0表示空格：
输入
1 3 6
4 7 5
0 8 2
输出
计算用时：31MS
共需： 18 步
1 3 6
4 7 5
0 8 2
↓ 第1步
1 3 6
0 7 5
4 8 2
↓ 第2步
1 3 6
7 0 5
4 8 2
...
↓ 第17步
1 2 3
8 6 4
7 0 5
↓ 第18步
1 2 3
8 0 4
7 6 5
The End!
楼主 2016-01-08 11:05 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
