作者rifiz (萨哈拉雅)
看板Prob_Solve
标题Re: [问题] ACM UVa10160 Servicing Station
时间Sat Oct 16 02:33:32 2010
※ 引述《DJWS (...)》之铭言：
: （这个不是A*喔...就是branch and bound的bound！）
: 我用的方法大致上是这样
: 如果有需要我再寄程式码给你，不用客气！
感谢各位先进的鼎力相助 我已经AC了 虽然还是需要1.3秒 ORZ
解法大概上就是跟各位讲述的差不多 那来个quantitive的乱分析好了
我之前的解法:
Backtrack的顺序是跟 graph search接近, 先从city1出发, 当作第一个服务站, 找跟
city1相连的的city设成已服务, 接着再从这些被服务的city的相连city找出下个服务站
的候选者, 不断的Backtracking. 这个方法有个很大的缺点, 若是没有把服务站的分布
状况每次都纪录下来并检查, 根本剪不了枝! 考虑如下状况, 把设成服务站的city编号
照搜寻顺序排列:
1 3 5 7 9 11.....(状况A)
3 5 11 1 7 9.....(状况B)
这两种状况其实是同一解..但是很难判断.... 所以可能最大有 N! 状况
若是用Bleed/DJWS的Backtracking顺序 最大就是 2^N 需要检查
光是未剪枝 数量级一整个差很多 @_@ ,( 35! ~ 10^40 , 2^35 ~ 3*10^10 )
然後我用的剪枝在我的方法中几乎没有用 呵呵 所以这是我这次学到的东西....
真是感谢各位的帮忙 虽然是写程式但是其实是学思考!!! 感谢!!!
P.S. A* 还是不会 XD 找个时间再来学好了.......
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.43.200.133