假設已經知道起點和終點
而每個情況最大拓展的STATE數量是原本的R倍
則F(n) = R * F(n - 1) where F(0) = 1
那個走N步就可能會產生R^N種情形
如果說從兩邊走同樣步數 我們原本需要搜尋R^L種情況
現在只需要搜尋R^(L/2)種情況兩次
以下PKU例題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1198
我自己算過 因為只有四顆棋子
四顆為等價 則STATE狀態最多為64 * 63 * 62 * 61(擺放位置) = 15249024種組合
固除了用雙向BFS以外 還可以用HASH TABLE去判重 這樣又可以少搜尋更多情況
文章標籤
全站熱搜
