作者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