汉诺塔算法：动态可视化实现与解析

  人工智能实验要求：利用状态空间法，实现汉诺塔求解过程的动画(将n个盘子，从A柱移到C柱上)。

  这里是一个C语言实现控制台绘制的实例，笔者将程序的思想写了个详细的注释，方便大家学习。

  同时利用这种方法，笔者改写了一个Java的用户界面效果演示程序，在Java相关文章中，大家可以看看。

程序效果图及思路：

这里的思路是：以三进制数据表示3个盘子的状态：比如0,1,2分别表示在A,B,C柱子上，一种状态值为220，就表示：最小盘在A柱，其他在C柱上

这里如果是n个盘子，还是用0,1,2三进制数表示盘子所在柱子，数字的组合就是一个整体的状态，就是三进制数序列，转化为10进制，就是一个整型值

这个数值就是整个盘子摆放的一种状态，状态的取值有3^n种，这里显示的是最短可行的状态路径(状态之间是相关联的，0.....0是起点,2.....2是要到达的状态)，算法就是要在这些状态中选择一条最佳路径，到达目的地！

详细解答请看程序注释:

#include
#include
#include
#include
#include


#define FALSE 0
#define TRUE 1


char graph[10][43]={
{"                                         \n"},
{"                                         \n"},
{"       |            |            |       \n"},
{"       |            |            |       \n"},
{"       |            |            |       \n"},
{"       |            |            |       \n"},
{"       |            |            |       \n"},
{"       |            |            |       \n"},
{"       |            |            |       \n"},
{"-----------------------------------------\n"},
};

typedef struct QNode { 
int    data;//存放数据
struct QNode *next;//存放直接后继的指针
} QNode, *QueuePtr;

typedef struct {   //辅助队列  广度优先扩展时用到
QueuePtr front;
QueuePtr rear;
} LinkQueue;

/* 初始化队列 */
int InitQueue(LinkQueue *Q)
{
/* 申请头结点空间，赋值给头/尾指针 */
Q->rear = Q->frOnt= (QueuePtr)malloc(sizeof(QNode));
if (Q->frOnt== NULL)
exit(-1);
Q->front->next = NULL;//头结点的next域
return TRUE;
}

/* 销毁队列 */
int DestroyQueue(LinkQueue *Q)
{
/* 整个链表(含头结点)依次释放
没有像链表、栈等借助 QNode *p, *q; 而直接借用了front和rear */
while (Q->front) {    //若链表为空，则循环不执行
Q->rear = Q->front->next; //抓住链表的下一个结点
free(Q->front);
Q->frOnt= Q->rear;
}

Q->rear = Q->frOnt= NULL;
return TRUE;
}

/* 判断是否为空队列 */
int QueueEmpty(LinkQueue Q)
{
/* 判断front和rear指针是否相等 */
if (Q.frOnt== Q.rear)
return TRUE;
else
return FALSE;
}

/* 元素入队列 */
int EnQueue(LinkQueue *Q, int e)
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if (p == NULL)
return FALSE;

p->data = e;
p->next = NULL;//新结点的next必为NULL
Q->rear->next = p;//接在当前队尾的后面
Q->rear = p;//指向新的队尾

return TRUE;
}

/* 元素出队列 */
int DeQueue(LinkQueue *Q, int *e)
{
QueuePtr p;
/* 空队列则返回 */
if (Q->frOnt== Q->rear) //用Q->front->next==NULL也可以
return FALSE;

p = Q->front->next;//指向首元
Q->front->next = p->next;//front指向新首元，可能为NULL
/* 如果只有一个结点，则必须修改尾指针 */
if (Q->rear == p)
Q->rear = Q->front;
/* 返回数据并释放结点 */
*e = p->data;
free(p);
return TRUE;
}


void IsExist(int *state,int tnum,int num,LinkQueue &Q)
{  // 四个参数的意义: 状态记录数组，下一个状态值，当前状态值，状态值队列
if (state[tnum] == -1) // 如果下一个状态值未被分配:未取得(对应状态标记为-1:初始化标记),将该状态入队列
   {
state[tnum] = num;// 修改下一个状态值为下标对应状态值数组的值(从-1变为上一状态值) (这里就包含了所求可行状态值之间的关系)
EnQueue(&Q, tnum);  //元素入队列
   }
}
/* --------- 图像输出函数集 ------------ */

void PrintGraph()
{
system("cls");
printf("过程演示：\n");
int i;
printf("\n");
for (i=0; i<10; i++)
 printf("%s", graph[i]);
}

void InitGraph(int n)
{  // 形成n对应的盘子叠加图形
int i,j,k;
for (i=0,j=8; i{
for(k=7-n+i; k<=7+n-i; k++)
  graph[j][k]='@';
}
}

void Moveto(int from, int to, int size)//from to 只有0,1,2
{
//bool moved=false;//判断是否已移动
int i,j,k,m,slen;
int from1=from*13+7;
int to1=to*13+7; 
for (i=2; i<9; i++)//找到起始层
 if (graph[i][from1+1]=='@')//层数记录
  break;
 
for (j=2; j<=9; j++)//找到目标层数
 if (graph[j][to1+1]=='@'||graph[j][to1+1]=='-')//层数记录
  {
 j--;
 break;
 }
// i 为当前层, j 为目标层

for(k=i-1; k>=0; k--)//上移
{
for (m=from1-size; m<=from1+size; m++){
graph[k][m]='@';
if (m==from1&&k>=1)
graph[k+1][m]='|';
else
graph[k+1][m]=' ';
}
PrintGraph();
}

slen=size*2+1;
if (from1for(k=from1; k<=to1; k++)//右移
{
for(m=k-size; m graph[0][m]='@';
graph[0][k-size-1]=' ';
PrintGraph();
}
else//左移
for(k=from1; k>=to1; k--)
{
for(m=k+size; m>k+size-slen; m--)
 graph[0][m]='@';
graph[0][k+size+1]=' ';
PrintGraph();
}
//平移结束
/* 下移 */
for(k=1; k<=j; k++)
{
for (m=to1-size; m<=to1+size; m++){
graph[k][m]='@';
if (m==to1&&k>2)
graph[k-1][m]='|';
else
graph[k-1][m]=' ';
}
PrintGraph();
}

}

void Display(int **recd, int num, int len)//演示函数
{
int i,j,k=0;
int tmp[100][3];
//analysize recd
for(i=1; i<=num; i++)//compare with last one
 {
 for (j=0; j  if (recd[i][j]!=recd[i-1][j])
   {
  tmp[k][0]=len-j;//变化的盘号
  tmp[k][1]=recd[i-1][j];//变化的起始位置
   tmp[k][2]=recd[i][j];//变化的终止位置
   k++;
  }
 }
InitGraph(len);//根据层数进行初始化图像
PrintGraph();
i=0;
do
{
Moveto(tmp[i][1], tmp[i][2], tmp[i][0]);
i++;
}while(i
printf("Over...");
getchar();
getchar();
}

/* ------------------------------------- */

/* 起始状态为0.....0 终止状态为2......2 */
int main()
{
/* -------------- 变量定义 ------------ */
int BRICKNUM;   //圆盘数
printf("请输入汉诺塔层数：");
scanf("%d",&BRICKNUM);

LinkQueue Q;
int i, j, k;
int n;
int num;
int temp_of_num;
int temp_of_add;
int num_of_state=1;//总状态数

for (int count=0; count //计算总状态数
num_of_state *= 3; // 每个盘子有3种状态(状态之间关联，有些没有用会被筛除掉)
    // 状态值数组表示了状态值之间的单向羁绊！状态值数组下标与状态值元素值是上下(前后)关系，当前状态值是以下一状态值为下标的状态元素的值
// 当前状态数组元素值是其上一个状态值
int *record_of_state = (int*)malloc(num_of_state*sizeof(int));   //每种状态的记录,-1代表未分配，否则为其父节点的下标                                                                                                                                                                          (总状态数为:num_of_state,状态分配状态值在相应数组中记录)
int *temp = (int*)malloc(BRICKNUM*sizeof(int));  // 定义存放n个盘子数，整型大小的存储空间
int *order_of_state = (int *)malloc(num_of_state*sizeof(int));//记录状态变化顺序

//此次汉诺塔问题借助三进制表示方法，0代表的是存在a柱子，1代表放在b柱子上，2代表放在c柱子上，位高的代表大盘，位低代表小盘，如         0000代表               四个盘全部放在a柱子上


for (i = 0; i {
record_of_state[i] = -1; //-1状态表示未分配
}

InitQueue(&Q); // 初始化队列
num = 0;  // num记录的是所有盘子元素状态序列对应的整数，可转化为一串0,1,2数字序列。
EnQueue(&Q, num);//状态1入栈，即0000(此时所有的盘子的状态都是0)
record_of_state[num] = -2;  // 状态数的大小是根据n的取值来确定的(num代表一个状态的取值，num的最大值即为最大状态数)
   /*
       这里是在出队列状态值的基础上,获取每一个盘子的状态(由整数得到一个数字序列)，在逐位来判断，确定下一状态值
       这里的规律:确定最底盘后(序列下标相对最小)，该位就一直不变
   */

       /*  这里会筛选所需的状态值，以及他们的先后关系(每个状态值都进入了队列，有些被排除了，最后得到        关键的状态值路径)  */
while (QueueEmpty(Q) == FALSE) //状态空间的生成（如果队列不为空，扩展状态空间）
{
DeQueue(&Q, &num); // 元素出队列，出队元素的值记录到了num中

n = num;  //n获得的是当前盘子对应的状态序列整数(将整数整除3(三种摆放方式)得到序列：状态序列)

for (i = BRICKNUM - 1; i >= 0; i--)  // 分解成三进制形式(从后往前存储，大盘子的状态再最前面=>整数的高位，对应数组下标越小)
{  // 这里n个盘片，进行n次循环，temp对应是n个整型数据大小区间
temp[i] = n % 3; // 对应temp区间存储的是：n个盘子的状态序列
n /= 3;
}

if (temp[BRICKNUM - 1] == 0)   //最后一位是0=>最上层盘子状态(该状态下:最小的盘子在a柱子上)
{    // 一个状态可以有多个子状态(关系记录在状态值数组中)
temp_of_num = num + 1;  // 记录下一状态值(在当前出队列的状态值的基础上)
IsExist(record_of_state, temp_of_num,num, Q); //若下一状态值未被分配,将其入队列
temp_of_num = num + 2;
IsExist(record_of_state, temp_of_num,num, Q);


for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--)
{ //扫描当前状态值后续对应3进制的每一位
if (temp[i] == 1)
{
temp_of_num = num + temp_of_add;
IsExist(record_of_state, temp_of_num,num, Q);
break;
}
else if (temp[i] == 2)
{
temp_of_num = num - temp_of_add;
IsExist(record_of_state, temp_of_num,num, Q);
break;
}
temp_of_add *= 3;
}
}
else if (temp[BRICKNUM - 1] == 1)  //最后一位是1(该种状态下:最小的盘子在b柱子上)
{
temp_of_num = num - 1;
IsExist(record_of_state, temp_of_num,num, Q);

temp_of_num = num + 1;
IsExist(record_of_state, temp_of_num,num, Q);

for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--)
{
if (temp[i] == 0)
{
temp_of_num = num + temp_of_add * 2;
IsExist(record_of_state, temp_of_num,num, Q);
break;
}
else if (temp[i] == 2)
{
temp_of_num = num - temp_of_add * 2;
IsExist(record_of_state, temp_of_num,num, Q);
break;
}
temp_of_add *= 3;
}
}
else  // 该状态下:最小的盘子在c柱子上
{
temp_of_num = num - 2;
   IsExist(record_of_state, temp_of_num,num, Q);

temp_of_num = num - 1;
IsExist(record_of_state, temp_of_num,num, Q);

for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--)
{
if (temp[i] == 0)
{
temp_of_num = num + temp_of_add;
IsExist(record_of_state, temp_of_num,num, Q);
break;
}
else if (temp[i] == 1)
{
temp_of_num = num - temp_of_add;
IsExist(record_of_state, temp_of_num,num, Q);
break;
}
temp_of_add *= 3;
}
}
}

/*
1: 如何完成的所有状态值无序入队列
2: 前后结点（状态值之间联系）查找，筛选的算法
*/

    /*  order_of_state 数组装载的是筛选的路径中入队的状态值,虽然所有的状态值都入过对列，但从中选择出了最短需要路径*/
num = num_of_state - 1;  // 状态值数组最大下标
     // 初始record_of_state数组的值都被赋值为-1，如果要入队列就将其值赋值为上一状态值的大小
i = 0;  // 从后往前遍历状态值数组:如果当前状态值入过队列,则其值为上一状态值
while (record_of_state[num] != -2) // 跳出口为第一个状态值0...0，其对应状态值数组值为-2.它是作为起点单独处理的
{
order_of_state[i] = num; // 这里记录着入过队列:即为分配过的状态值元素下标 
num = record_of_state[num];// num记录上一状态值，也即上上状态值对应下标 (应该可以将值与下标转化为相差为1的关系)
i++;
}
order_of_state[i] = num; // 在num=0时并没有装入order_of_state就跳出了循环

int mycount=0;
int **recd = (int **)malloc((i+1)*sizeof(int *));//记录状态变化顺序
for (j=0; j<=i; j++)
 recd[j] = (int *)malloc(BRICKNUM*sizeof(int));
// int **recd= new int[i][BRICKNUM];//记录状态变化，以便图像演示使用
for (j=i; j>=0; j--)
{
n = order_of_state[j];
for (k = BRICKNUM - 1; k >= 0; k--)  //分解成三进制形式
{
temp[k] = n % 3;
n /= 3;
}
memcpy(recd[mycount], temp, BRICKNUM*sizeof(int));
mycount++;
for (k = 0; k printf("%d", temp[k]);
printf("\n");
}
getchar();
getchar();
//输出演示
if(BRICKNUM!=0)
    Display(recd, i, BRICKNUM);
//释放变量
free(temp);
free(record_of_state);
free(order_of_state);
for (k=0; k<=i; k++)
 free(recd[k]);
free(recd);
getchar();
return 0;
}

这个程序的关键是：从所有的状态值中，筛选出需要的状态值，并确定他们之间的先后关系，以便能正确按序挪动盘子，完成任务