posts - 12,  comments - 40,  trackbacks - 0

把最近遇到的搜索好题列一下(推荐做做)。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2286
The Rotation Game
迭代深搜,中等难度。
一开始用广搜做,结果MLE(当然有可能程序写错),改成迭代深搜后,因为不用考虑判重,不用写状态压缩,程序变的特别简单,再加上一个剪枝后就过了。
剪枝:(8 - 中间8个格最多的数字的个数)> 剩余步数,则剪枝

POJ 2286


http://acm.pku.edu.cn/JudgeOnline/problem?id=1184
聪明的打字员
称之为广搜,可这题真的是不那么好做啊。

一开始,广搜,TLE;然后双广,TLE;然后A*,TLE,当然有可能启发函数太次了。
最后请教oyjpArt,才明白有那么猛的的算法。

大概思路是把所有操作分两类,一类是置换类,就是只是交换数字位置、移动光标位置,二类是加减类,就是对每个数字加1减1。
然后广搜也是分两步,先搜所有的置换,再“搜”所有的加减。
1、先说第二步,“搜”加减,很简单,每个数字相差几就是几步,加起来就是最小步数。
2、第一个搜,要记录置换的当前状态,光标状态,还有光标曾经过的数字的初始位置(用6位2进制存储,记录这个意思就是说只要经过的数字,以后就允许加减,一气呵成)
。。。写不明白
POJ 1184


http://acm.pku.edu.cn/JudgeOnline/problem?id=1376
Robot
广搜,容易。
后来加一个启发函数进去,是这样定义的:H(n) = 到目标横向距离 / 3 + 到目标纵向距离 / 3 ,除以3是因为一步可以走3个格子,结果比原来的还要慢。

 

POJ 1376


http://acm.pku.edu.cn/JudgeOnline/problem?id=2449
Remmarguts' Date
求S到T的K短路,数据量N=1000,M=100000,K=1000。较难

1、用优先队列做广搜,当然跟一般广搜不一样,每个点允许k次出列,第k次出列的T点即是解。(理论上可行,但是实际确MLE超内存)
2、加入启发式函数H——到T的最短距离,传说中的A*就是这样来的。显然 这个最短距离 < i 短距离,满足条件,重要的是事实证明效果很不错。
参考:http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144
POJ 2449


http://acm.pku.edu.cn/JudgeOnline/problem?id=1011

Sticks
剪枝好题,中等难度

两个强剪枝
1、如果长度为5的木棍刚好能满足当前块,就没必要尝试用2+3的木棍
2、如果当前块为空,则可指定任意一根木棍放入其内,也没必要尝试其他木棍
POJ 1011


http://acm.pku.edu.cn/JudgeOnline/problem?id=1190
生日蛋糕
深搜剪枝,难,《算法艺术与信息学竞赛》P.181

上下界剪枝:
 1、由层数导致的体积上界、下界
最优性剪枝:
1、面积下界 与 当前最优解比较
2、由体积和当前半径导致的最小表面积 S <= 2*V/R (超强)
POJ 1190


http://acm.pku.edu.cn/JudgeOnline/problem?id=1324
Holedox Moving
广搜,A*搜会快一些,中等难度

关键点在于怎么判重、怎么存储蛇:蛇头 + 后面每个点相对于前一点的方向(即0、1、2、3四元值),因此状态空间 20*20*4^(8-1) = 6553600,因此可以用数组判重。
POJ 1324


http://acm.pku.edu.cn/JudgeOnline/problem?id=2044
Weather Forecast
用深搜做的,搜到一个解即可退出,中等难度

像上个题一样,关键点还是在于怎么判重、怎么存储状态(当前天是第几天 以及 前6天的天气状况):最后1天云的位置(0、1、2……8) + 云的变化方向(0、1、2、3、4),状态空间5^5 * 9 * 365 = 10265625,开数组还是非常不错的。
POJ 2044

 

posted on 2007-08-11 12:27 LSM 阅读(2826) 评论(8)  编辑 收藏 引用 所属分类: 搜索

FeedBack:
# re: 搜索题集锦(无限更新中……)
2007-08-11 14:51 | XTSHMF
你都做了阿,好厉害哟  回复  更多评论
  
# re: 搜索题集锦(无限更新中……)
2007-08-12 17:31 | LSM
@XTSHMF
还有不少好题正在弄,尤其A*启发函数要怎么设计还不太明白  回复  更多评论
  
# re: 搜索题集锦(无限更新中……)
2007-08-19 23:24 | zhangbin
真是个热心的高手,教了我一道题,谢谢!  回复  更多评论
  
# re: 搜索题集锦(无限更新中……)
2007-08-22 20:54 | haozi
可以发我你poj上2044的代码我看看吗?
我是刚刚开始搞这个的,集中在练习搜索,
借你代码学习一下!
haozixx@126.com  回复  更多评论
  
# re: 搜索题集锦(无限更新中……)
2007-08-27 21:10 | ruiqi
好强!不过我也在成长哦。  回复  更多评论
  
# re: 搜索题集锦(无限更新中……)
2008-06-10 17:20 | Lup
老兄poj-3333怎么做,往回跳怎么处理
发代码我看看,无限感激
jichong22@sina.com  回复  更多评论
  
# re: 搜索题集锦(无限更新中……)
2008-09-11 13:47 | doxi
给我个代码 pku 2044 谢谢
fanxicai2000@163.com  回复  更多评论
  
# re: 搜索题集锦(无限更新中……)
2010-03-22 16:44 | LostCanvas
你好 能给我发个PKU 2044代码吗? 谢谢
vipzomagic@gmail.com  回复  更多评论
  

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


<2010年3月>
28123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(4)

随笔分类

随笔档案

牛牛 ACM/ICPC

最新随笔

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜