a tutorial on computer science

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 0 文章 :: 17 评论 :: 0 Trackbacks
   这几天在做搜索,看到一篇比较好玩的论文,估价函数在信息学竞赛中的应用。发现有点难懂。好了,第一道就是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;
}
posted on 2012-04-06 22:56 bigrabbit 阅读(1662) 评论(1)  编辑 收藏 引用

评论

# re: 乱乱的想法---不是题解---uva10605 2012-04-10 09:17 tb
不错的 学习了   回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理