这几天在做搜索,看到一篇比较好玩的论文,估价函数在信息学竞赛中的应用。发现有点难懂。好了,第一道就是uva10605。
题意就不废话了。这题我刚刚看到作者列举了下暴力时候深度为1-17的时候搜索的次数,我也很傻很天真的写了个暴力。我是枚举不定次数个边界,然后找最小值。程序就一直在那儿搜,还没用迭代加深搜索。。。傻傻写了半小时。结果这种暴力中的最暴力需要的节点数太惊人了。然后就。。卡住了。
果断搜。没人写这个题的结题报告。晕。偶然发现一个台湾的网站,全死繁体字。找到了UVA10605,发现就一句话,最小生成树变种云云,NPC问题。额,没任何信息。额,也不是没信息!最小生成树算法是从每个节点开始枚举,对,每个节点。。。额。。。。SB了,这个题直接暴力的写法应该是枚举N个金矿,然后搜。
又很傻很天真的写了一次。发现我写的和作者列举的生成结点个数差不多,列举了几个答案,也是对的。枚举总算没问题了。精彩的地方还在后面:如何用
启发函数和迭代加深搜索来解决这个有最优解问题。晚上做了另一件事,所以下次再细看这道题。
晚上突然想到去年十二月份月赛有一道题,链接在此,
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1223。这题的意思。。额。。不难懂。以前看这个题没思路,现在看了看,发现可以暴力一下。这个题应该不是传统意义上的搜索题,因为限制条件比较奇怪:两条线不能交叉。而且数据很大,有100个点。而且还有无解情况。无解现在看来是没办法预判的,那么就要搜索所有的可能了。4^100是个天文数字。好吧,我没有注意到任意两条线不能相交这个题目条件,所以写了个暴力,这个暴力也不是毫无价值,其实主要是想自己写一个启发函数试一试,看看能不能对这个问题进行优化的。这个题的启发函数很挫,就是所有的点到它最近的边的长度(
最乐观的估计)。然后就没有然后了。这个题描述不清,哎。。TLE,OLE,WA。。惨不忍睹。
只贴一下uva那个题的暴力吧,我觉得写的不算太丑,改天把他A掉。
另外,今天好像到了另外一个题:这个题可能比较有意思,也是这个文章能给别人点启发的地方:
去年TX来中南校招笔试的最后一个题。我先吐槽下那张卷子:选择题60分,全是各种操作系统网络细节,没啥意思。TX咋出这样的题目呢?填空题倒是比较简单,但是据说各种坑坑,无限坑。好吧。就最后一个比较有意思。题目大意如下:
给定一个NXM的矩阵,矩阵中三种点:第一种是墙壁,不可以走进去;第二种是路,可以走进去;第三种是豆豆。题目的问题是给定一个起始点,求吃掉所有豆豆最短的路。
首先的想法就是,暴力。题目中N,M的规模是1000X1000,还是非常大的。如果直接暴力,肯定挂掉。这个题LJJ跟我说过,他想把每两个豆豆的最短路求出来,这个不难,而且豆豆小于100,没什么问题。然后再搜。搜索的时候,也是A(100,100),非常大。转化成了一个求最短哈密顿路径问题。这里可以扩展出很多想法,额,还没想好。
这个题是不是能用启发函数做一下呢?首先,题目需要的是最短路径。接着上面的说,求出来任意两个豆豆的最短路之后,实在想不出啥玩意了。
明天要去实验室matlab毕设了。。。这纠结的搜索。求同行指教。
#include <cstdio>
#include <cstring>
char map[20][20];
int vis[20][20];
class node
{
public:
int x,y;
};
node point[23];
int pcount;
int res;
int N,M;
int val[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int testdata;
int bound(int x,int y)
{
if(x<0 || y<0 || x>=N || y>=M) return 0;
return 1;
}
int min(int x,int y)
{
if(x>y) return y; return x;
}
int getH()
{
int i,ret = 0;
for(i=0;i<pcount;i++)
{
int x = point[i].x;
int y = point[i].y;
if(!vis[x][y])
{
ret += min(min(x,N-x),min(y,M-y));
}
}
return ret;
}
void dfs(int step,int x,int y,int next,int F,int count,int maxstep)
{
testdata++;
if(step > maxstep)
return;
if(next == pcount)
{
if(count == pcount && res > step)
{
res = step;
}
return;
}
int i;
if(F == 1)
{
if(!vis[point[next].x][point[next].y])
{
vis[point[next].x][point[next].y] = 1;
dfs(step+1,point[next].x,point[next].y,next+1,0,count+1,maxstep);
vis[point[next].x][point[next].y] = 0;
}
dfs(step,0,0,next+1,1,count,maxstep);
return;
}
else
{
for(i=0;i<4;i++)
{
int nx = x + val[i][0];
int ny = y + val[i][1];
if(bound(nx,ny) && !vis[nx][ny])
{
if(map[nx][ny] != '#')
{
vis[nx][ny] = 1;
if(map[nx][ny] == '*')
dfs(step+1,nx,ny,next,0,count+1,maxstep);
else
dfs(step+1,nx,ny,next,0,count,maxstep);
vis[nx][ny] = 0;
}
else
dfs(step,0,0,next,1,count,maxstep);
}
}
}
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int i,j;
while(scanf("%d%d",&N,&M)!=EOF)
{
pcount = 0;
for(i=0;i<N;i++)
scanf("%s",map[i]);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
if(map[i][j] == '*')
{
node tmp ={i,j};
point[pcount++] = tmp;
}
memset(vis,0,sizeof(vis));
res = N*M;
testdata = 0;
for(i=1;i<=16;i++)
{
dfs(0,0,0,0,1,0,i);
if(res == i)
{
printf("%d %d\n",res,testdata);
break;
}
}
}
return 0;
}