德国开元华人社区开元周游

标题: 类华容道问题，谁会编程解决？（小学计算机奥赛题） [打印本页]

作者: 三岛由纪夫 时间: 26.9.2009 11:34
标题: 类华容道问题，谁会编程解决？（小学计算机奥赛题）
本帖最后由三岛由纪夫于 26.9.2009 14:24 编辑

在3*3的方格内，任给打乱的8个数字1-8的一种布局，按照华容道那种走法上下左右，使之排列成顺序的，编程求解，输入数字1-8任意一种布局，输出每一步的走法。

这是我小学计算机奥赛时候的一道练习题

扩展：nXn的方给内任给数字1到n*n-1的一种布局，输出每一步走法

作者: jh2009 时间: 26.9.2009 12:45
本帖最后由 jh2009 于 26.9.2009 13:57 编辑

设计一个N x N的matrix, 把0-N随机放进去，只有0和临近（0位置P的P－N，P+N，P－1，P+1）的数字可以交换位置。接下来就是枚举，直到0位置（或者1位置）往后的数字都比前一个数字大1为止。记录下成功排序的执行步骤。

程序也许会写得很复杂所以不写代码了，思路就是这样。

作者: 三岛由纪夫 时间: 26.9.2009 13:21
本帖最后由三岛由纪夫于 26.9.2009 14:41 编辑

设计一个N x N的matrix, 把0-N随机放进去，只有0和临近（0位置P的P－N，P+N，P－1，P+1）的数字可以交换位置。接下来就是枚举，直到0位置（或者1位置）往后的数字都比前一个数字大1为止。记录下成功排序的执行步骤。 ...
jh2009 发表于 26.9.2009 13:45

（sorry，原题我有笔误，就是在3X3的方阵内放打乱的8个连续数字（3X3-1），或在n*n方阵内放打乱n*n-1个连续数字）

不用写代码，请写个伪代码，谢谢先

顺便给个计算复杂度的度量

顺便说一下：你这思路里面没有判敛函数，恐怕计算机得算一辈子。如果真这么简单也不用奥赛了，直接当作小学入学考试题得了。

作者: GoodOldBilly 时间: 26.9.2009 15:01
本帖最后由 GoodOldBilly 于 26.9.2009 16:07 编辑

《人工智能》那门课里面的，楼主在中国学CS的话，应该知道的算法

清华计算机系马少平讲的

作者: jh2009 时间: 26.9.2009 15:10
你说得没错，3x3可以枚举，NxN枚举就死了。

老规矩，自己拉的屎自己擦

，大家围观一下就行了。

作者: 三岛由纪夫 时间: 26.9.2009 15:20

《人工智能》那门课里面的，楼主在中国学CS的话，应该知道的算法

清华计算机系马少平讲的
GoodOldBilly 发表于 26.9.2009 16:01

弄道小学题目给大家玩玩儿，免得有了孩子后，孩子上了小学，问你题目你都不会算。

只会枚举的自己枚举玩儿去吧。3*3就能枚举了？不懂装懂的人还真是有。

作者: jh2009 时间: 26.9.2009 15:38
本帖最后由 jh2009 于 6.10.2009 17:22 编辑

你NB也没给个结论嘛，只知道拉屎不懂擦屁股。

作者: shannon 时间: 27.9.2009 22:34
A* + using alpha-beta-pruning to optimize the searching process.

作者: Vesper_Lynd 时间: 29.9.2009 09:33
需要解决:
搜索的解空间巨大，如何存储和编码棋盘棋局
如何快速在已存棋盘格局中搜索新产生的棋局在以前是否已经产生

作者: Eros 时间: 30.9.2009 00:39
本帖最后由 Eros 于 30.9.2009 00:40 编辑

A* + using alpha-beta-pruning to optimize the searching process.
shannon 发表于 27/9/2009 22:34

说的对呵

重要的不是广度优先搜索，重要的是快速查询和剪枝，提高效率

网上kiang来的华容道算法，不是lz这道题的：

/************************************************************************/
/* 华容道初稿
/* GPL,大家可以任意修改,但是需要保留原作者,谢谢
/* Author: L.T.Dreamy
/* 2007-10-5 完成于西安电子科技大学
/*
/************************************************************************/

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#include "string.h"
#include "time.h"

struct GridNode{
unsigned char grid[5][4]; //棋盘
GridNode *next_queue; //队列中的下一个节点
GridNode *parent; //其父亲节点
GridNode *next_hash; //hash 表中的下一节点
};

//这样复制速度快
#define g_copy(g1,g2){/*复制棋盘 g2->g1*/\
unsigned int *t1,*t2;\
t1=(unsigned int*)(g1);\
t2=(unsigned int*)(g2);\
t1[0]=t2[0];\
t1[1]=t2[1];\
t1[2]=t2[2];\
t1[3]=t2[3];\
t1[4]=t2[4];\
}

#define Width 4 //
#define Height 5

//出口
#define X 3
#define Y 1

//棋盘边界
struct Bound {
int top;
int bottom;
int left;
int right;
};

//边界
Bound bound={0,4,0,3};

//哈希表结构
struct hashlink{
unsigned char len; //此桶中数据大小
GridNode *next;
};

//队列结构
struct queuelink{
GridNode *first;
GridNode *iterater;
GridNode *tail;
};

#define MAX_CON 65536 //设最大为2^16
//哈希表
hashlink hlink[MAX_CON]={0};
//队头
queuelink queue;

FILE *f;

//获得hash表的hash值
unsigned short GetHashValue(unsigned int *grid)
{
unsigned int mask1 = 524287; //19个1
unsigned int mask2 = 8191; //13个1
unsigned short len = 65535;

unsigned int result =0;
result += ((grid[0] & (mask1<<13))>>13)|((grid[0] & mask2)<<19);
result ^= grid[1];
result += ((grid[2] & (mask1<<13))>>13)|((grid[2] & mask2)<<19);
result ^= grid[3];
result ^= ((grid[4] & (mask1<<13))>>13)|((grid[4] & mask2)<<19);
result += grid[5];

return result%len;
}

void print(unsigned char* grid)
{
int i;
/*
fprintf(f,"\n--------------\n");
for(int i=0;i<Height;i++)
{
for(int j=0;j<Width;j++)
fprintf(f,"%c",*(grid+Width*i+j));
fprintf(f,"\n");
}
fprintf(f,"--------------\n\n");
*/
fprintf(f,"\n");
for(i=0;i<=Height*2;i++)
{
for(int j=0;j<=Width*4;j++)
{

if(i%2==0) //奇数行画--
{
if(j%4!=0)
{
if(i/2-1>=0 && (*(grid+Width*(i/2-1)+(j/4))=='V'||\
*(grid+Width*(i/2-1)+(j/4))=='C'||\
*(grid+Width*(i/2-1)+(j/4-1))=='C'))
fprintf(f," ");
else
fprintf(f,"-");
}
else
fprintf(f,"+");
}else{ //偶数行画 | 和字母
if(j%4==0)
{
if(j/4+1<=Height && (*(grid+Width*(i/2)+(j/4-1)) == 'H' ||\
*(grid+Width*(i/2)+(j/4-1)) == 'C' ||\
*(grid+Width*(i/2-1)+(j/4-1)) == 'C'))
fprintf(f," ");
else
fprintf(f,"|");
}
else if(j%4==2)
{
if(*(grid+Width*(i/2)+(j/4))!='0')
fprintf(f,"%c",*(grid+Width*(i/2)+(j/4)));
else
fprintf(f," ");
}else
fprintf(f," ");
}
}
fprintf(f,"\n");
}
}

//将新的棋盘格局加入到hash表中,并且将此新生成的节点加入到队列链表中,并将其与其父亲节点关联起来
char * InsertNode(unsigned *grid,GridNode *parent)
{
//检测是否有相同的棋盘格局
unsigned short index= GetHashValue(grid);
GridNode *p = hlink[index].next;
GridNode *q = NULL;

if(hlink[index].len == 0)
{
GridNode *g = new GridNode;
//复制棋盘
g_copy(g->grid,grid);
g->next_queue = NULL;
g->next_hash = NULL;
g->parent = parent;
queue.tail->next_queue = g;
queue.tail=g;

hlink[index].next = g;

//此hash链数据值++
hlink[index].len ++ ;

return (char*)g; //返回此节点的指针
}

if(hlink[index].len > 0)
{
while(p!=NULL)
{
//如果相同,则返回NULL,表示不用再插入相同的棋盘格局了
if(grid[0] == *((unsigned int*)(p->grid[0]))&&\
grid[1] == *((unsigned int*)(p->grid[1]))&&\
grid[2] == *((unsigned int*)(p->grid[2]))&&\
grid[3] == *((unsigned int*)(p->grid[3]))&&\
grid[4] == *((unsigned int*)(p->grid[4])))
{
//fprintf(f,"Same Node\n");
return NULL;
}
q = p;
p = p->next_hash;
}
GridNode *g = new GridNode;
//复制棋盘
g_copy(g->grid,grid);
g->next_queue = NULL;
g->next_hash = NULL;
g->parent = parent;
queue.tail->next_queue = g;
queue.tail=g;

q->next_hash = g;

//此hash链数据值++
hlink[index].len ++ ;

return (char*)g; //返回此节点的指针
}

return NULL; //返回此节点的指针
}

//检测是否可以走动
//00H-不能移动,01H-上,10H-左,100H - 右,1000H -下 [返回值]
int Detect(unsigned char* grid,int row,int col,int w,int h)
{
int result= 0;
//检测上边,如果上边还有一层
if(row-1>=0)
{
for(int j=0;j<w;j++)
{
if(*(grid+(row-1)*Width+(col+j))!='B')
{
break;
}
}
if(j==w)
result += 1<<0;
}

//左边
if(col-1>=0)
{
for(int j=0;j<h;j++)
{
if(*(grid+(row+j)*Width+(col-1))!='B')
{
break;
}
}
if(j==h)
result += 1<<1;
}

//下边
if(row+h<Height)
{
for(int j=0;j<w;j++)
{
if(*(grid+(row+h)*Width+(col+j))!='B')
{
break;
}
}
if(j==w)
result += 1<<2;
}

//右边
if(col+w<Width)
{
for(int j=0;j<h;j++)
{
if(*(grid+(row+j)*Width+(col+w))!='B')
{
break;
}
}
if(j==h)
result += 1<<3;
}

return result; //
}

#define ggrid(x,y) (*((unsigned char*)cur_q->grid+Width*(x)+(y)))

bool test(GridNode *cur_q)
{
for(int i=0;i<Height;i++)
{
for(int j=0;j<Width;j++)
{
switch(ggrid(i,j)) {
case 'C':
if(ggrid(i+1,j)!='0' || \
ggrid(i,j+1)!='0' ||\
ggrid(i+1,j+1)!='0')
goto error;
break;
case 'V':
if(ggrid(i+1,j)!='0')
goto error;
break;
case 'H':
if(ggrid(i,j+1)!='0')
goto error;
break;
default:
break;
}
}
}
return false;
error:
print((unsigned char*)cur_q->grid);
fprintf(f,"Parent \n");
print((unsigned char*)cur_q->parent->grid);

return false;
}

bool IsResoluted(unsigned char* grid)
{
if(*(grid+X*Width+Y)=='C')
return true;
return false;
}

//根据不同的man探测并生成新的格局,如果返回true表明找到结果了..false表示未移动
bool GenNewGrid(unsigned char* old_grid,int row,int col,GridNode *cur_q)
{
int w,h;
switch(*(old_grid+Width*row+col)) {
case 'C': //曹操
w=2;
h=2;
break;
case 'V': //竖着的五虎将
w=1;
h=2;
break;
case 'H': //横着的五虎将,关羽
w=2;
h=1;
break;
case 'S': //卒
w=1;
h=1;
break;
case 'B': //空格,nothing to do
break;;
default:
printf("error 士兵 %c \n",*(old_grid+Width*row+col));
return false;
}

//探知方向
int direct = Detect(old_grid,row,col,w,h);
//printf("Direct : ++++ %0x  \n",direct);

unsigned char new_grid[5][4];

//如果探知可以移动,则移动,并将新的格局加入到队列
if(direct!=0)
{
int i,j;
//向上
if((direct & 0x01) == 0x01)
{
//将旧的格局copy到新的格局,在新的格局中修改数据
g_copy(new_grid,old_grid);
for(i=0;i<h+1;i++)
{
for(j=0;j<w;j++)
{
if(i==h)
{
new_grid[row-1+i][col+j] = 'B';
continue;
}
new_grid[row-1+i][col+j]=new_grid[row+i][col+j];
}
}
//printf("上**********************\n");
//print((unsigned char*)new_grid);

InsertNode((unsigned *)new_grid,cur_q);
test(cur_q);
if(IsResoluted((unsigned char*)new_grid))
{
printf("@@@@@@@@@ Resolution is Gernated! @@@@@@@@@@@@\n");
return true;
}

}
//向左
if((direct & 0x02) == 0x02)
{
//将旧的格局copy到新的格局,在新的格局中修改数据
g_copy(new_grid,old_grid);
for(i=0;i<w+1;i++)
{
for(j=0;j<h;j++)
{
if(i==w)
{
new_grid[row+j][col-1+i] = 'B';
continue;
}
new_grid[row+j][col-1+i]=new_grid[row+j][col+i];
}
}
//printf("左**********************\n");
//print((unsigned char*)new_grid);

InsertNode((unsigned *)new_grid,cur_q);
test(cur_q);
if(IsResoluted((unsigned char*)new_grid))
{
printf("@@@@@@@@@ Resolution is Gernated! @@@@@@@@@@@@\n");
return true;
}
}
//向下
if((direct & 0x04) == 0x04)
{
//将旧的格局copy到新的格局,在新的格局中修改数据
g_copy(new_grid,old_grid);
for(i=h;i>=0;i--)
{
for(j=0;j<w;j++)
{
if(i==0)
{
new_grid[row+i][col+j] = 'B';
continue;
}
new_grid[row+i][col+j]=new_grid[row-1+i][col+j];
}
}
//printf("下**********************\n");
//print((unsigned char*)new_grid);

InsertNode((unsigned *)new_grid,cur_q);
test(cur_q);
if(IsResoluted((unsigned char*)new_grid))
{
printf("@@@@@@@@@ Resolution is Gernated! @@@@@@@@@@@@\n");
return true;
}
}
//向右
if((direct & 0x08) == 0x08)
{
//将旧的格局copy到新的格局,在新的格局中修改数据
g_copy(new_grid,old_grid);
for(i=w;i>=0;i--)
{
for(j=0;j<h;j++)
{
if(i==0)
{
new_grid[row+j][col+i] = 'B';
continue;
}
new_grid[row+j][col+i]=new_grid[row+j][col+i-1];
}
}
//printf("右**********************\n");
//print((unsigned char*)new_grid);

InsertNode((unsigned *)new_grid,cur_q);
test(cur_q);
if(IsResoluted((unsigned char*)new_grid))
{
printf("@@@@@@@@@ Resolution is Gernated! @@@@@@@@@@@@\n");
return true;
}
}

}

return false;
}

//棋盘格局生成器,即走步器
void Traverse(unsigned int *grid)
{
//初始化队列
GridNode head;
queue.first = &head;
queue.tail = &head;

//加入初始棋盘格局
if((queue.first = (GridNode*)InsertNode(grid,NULL))==NULL)
{
printf("Init error!\n");
return;
}
queue.iterater = queue.first;

//如果队列不空,则继续广度搜索
while(queue.iterater!=NULL)
{
//对于棋盘中的每一个元素进行探测,看是否可以移动
unsigned char *c_grid = (unsigned char*)(queue.iterater->grid); //获取队列头的棋盘格局
//print((unsigned char*)c_grid);
for(int i=0;i<Height;i++)
{
for(int j=0;j<Width;j++)
{
//已经处理的或空格的情况
if(*(c_grid+Width*i+j)=='0' || *(c_grid+Width*i+j)=='B')
continue;

//表明此网格上有一个man
//printf("-----  %c  -----\n",*(c_grid+Width*i+j));
if(GenNewGrid((unsigned char*)c_grid,i,j,queue.iterater)==true)
{
//找到结果了..^_^
//打印结果
GridNode *p=queue.iterater;
fprintf(f,"^^^^^^^^^^^^^^^^^\n\n");
int n=0;

while(p!=NULL)
{
print((unsigned char*)p->grid);
p = p->parent;
n++;
}
fprintf(f,"\n-------------\n%d 步\n",n);

int sum=0;
for(int i=0;i<MAX_CON;i++)
{
fprintf(f,"%d  ",hlink.len);
if(hlink.len>10)
fprintf(f,"$$$$$$$$$$$$$$$$\n");
if(i%20==0)
fprintf(f,"\n");
sum += hlink.len;
}
printf("搜索节点数目：%d \n",sum);
return;

}
}
}
queue.iterater = queue.iterater->next_queue;
}

if (queue.iterater == NULL)
{
printf("*** No resultion! ***\n");
return ;
}

}

//主函数
int main(int argc, char* argv[])
{
f=fopen("a.txt","w+");

unsigned char init_grid[5][4]={
'V','C','0','V',\
'0','0','0','0',\
'V','H','0','V',\
'0','S','S','0',\
'S','B','B','S'
};

//char a[]={32,0,0,0x80};
//printf("%0x\n",GetHashValue((unsigned int*)a));

//初始化
memset((char*)hlink,0,sizeof(hashlink)*MAX_CON);
memset((char*)&queue,0,sizeof(queuelink));

clock_t start;
clock_t finish;
start = clock();

Traverse((unsigned int*)init_grid);
finish = clock();
double tt=(double)(finish-start)/CLOCKS_PER_SEC;
printf("Execute time is : %lf 秒\n",tt);
fclose(f);
return 0;
}
作者: abadebadu 时间: 1.10.2009 13:48
做个记号，回去想想。
作者: abadebadu 时间: 2.10.2009 13:55
尝试一下。
先定义一个简单的结构描述３X３的状态。
比如435612_78可以用来表示
435
612
_78

再写一个移动的可能性产生器
比如从435612_78有两种可能，4356127_8和43561_278

还需要一个评分器，也就是说，当前的状态离目的地还有多远。
比如可以定义
435
612
_78
中的４距目的的距离是１，３距目的的距离是１，５距目的的距离是２，６距目的的距离是２，１距目的的距离是２，７距目的的距离是１，８距目的的距离是１。
那么总和是１０。
具体的定义可以更细分。

最后需要一个有序链，每个节点有四部分组成，结构，节点是否试过，距目标的距离，父节点。

程序开始用随机数先初始化结构。
对其进行评分。
加入到有序链。

下面是一个循环

１。从有序链里选离目标最近而且还没有尝试过的节点
２。是否是目标，如是跳出循环，打印。
３。该节点在有序链中标记为尝试过。
４。计算移动可能性。
５。对每种移动可能性检查是否已在有序链中
６。对没在有序链中的移动可能性进行评分
７。将此移动可能性及其评分和父节点加入有序链
８。重复１

打印部分就不写了，就是按照父节点往回找。

欢迎光临德国开元华人社区开元周游 (https://forum.kaiyuan.de/) Powered by Discuz! X3.2

德国开元华人社区 开元周游

德国开元华人社区开元周游