Re: [問題] ACM UVa10160 Servicing Station
看板Prob_Solve (計算數學 Problem Solving)作者rifiz (薩哈拉雅)時間14年前 (2010/10/04 01:51)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/5 (看更多)
※ 引述《rifiz (薩哈拉雅)》之銘言：
: 小弟online judge在這題卡住了 : Problem D: Servicing stations
: 這題是給一群city 還有一堆city之間的connection. 然侯要找出能cover所有city的
: service station的最小數目. 一個station可以服務所在地的所有immediate city.
: 我使用的方法是 backtracking, 也就是暴力法的一種. 這種方法的精華應該是在
: 剪枝 但是我沒辦法減到足夠少的狀態數目 有誰可以給個建議要如何減少才行嗎?
: 目前我的剪枝只有: 比上一次的數目多的話就不搜尋了 XD
: 請先進給我一點想法跟意見阿.......感激不盡
: --------------------
: 已經TLE好幾百次了 @_@
還是TLE. @_@ vertex cover那個好難 現在看不是很懂.....XD
小弟我的做法大概是:
BackTrack
1. 檢查現在的station數目 比之前的所有解的最小數目還大的話 就return
2. 產生可能的candidate list:
A. 對所有還沒有被服務到的city, check:
這個city所連出去的的city是不是至少有一個還沒被服務到, 是的話才加入
candidate list.
3. For each candidate:
A. append到solution list的尾端
B. 把被他服務到的city mark起來
C. BackTracking.
有試過如下的剪枝:
每次選擇的點所造成的cover set每一步都要 > 上一次的每一步的cover set, 可是這樣
會錯(事實上也找的出反例 XD)
但是上面這樣的剪枝應該還是不夠, 看了各位大大的建議只能得出上面的做法.....
請幫忙再建議一下該如何在哪裡剪枝......
謝謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.199.110
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
