Q
回溯算法
1
A
回答
1
有時在回溯算法中,當你知道某個分支不是答案 - 你可以修剪它。這在遊戲代理商中非常常見,被稱爲Alpha Beta Prunning。
因此 - 當您對訪問節點重新排序時,您可以提高您的訪問速度,從而減少您訪問的實際節點數量,而不會影響答案的正確性。
還有一種可能性 - 如果沒有任何遺漏就是緩存性能。有時候樹被存儲爲數組[特別是complete trees]。數組迭代時效率最高,而不是「隨機跳躍」。重新排序可能會改變這種行爲,導致更好/更糟糕的緩存行爲。
+0
它使用python列表實現,並且還沒有修剪(可能的下一步) – user1225640 2012-02-22 11:51:38
0
回溯的本質恰恰是沒有看所有的可能性或節點(在這種情況下),但是,如果節點沒有下令是不可能的算法「修剪」一個可能的分支因爲如果元素實際上位於該分支上,則不確定。
不同於當它是一個有序樹,因爲如果所搜索的元素是更大/更小的該子樹的根,搜索到的元素是對向右或向左分別。這就是爲什麼如果樹不是有序的,那麼計算順序就等於暴力,但是,如果樹在最壞情況下是有序的,就等於暴力,但是執行的次序更小。
相關問題
- 1. Sodoku回溯算法
- 2. 學習回溯算法
- 3. 數獨,回溯算法
- 4. 複雜的回溯算法
- 5. AC3算法和回溯
- 6. 使用回溯算法
- 7. 填字回溯算法
- 8. 數獨回溯算法
- 9. 如何應用回溯算法?
- 10. dijkstra的最短路徑算法回溯?
- 11. 組合生成使用回溯算法
- 12. 數獨算法不能正確回溯
- 13. 實現回溯N皇后算法
- 14. 回溯算法的黃金序列
- 15. 回溯算法設計技術定義
- 16. 數獨解算器回溯
- 17. 算法回溯。在圖中計算完美匹配
- 18. 回溯迷宮算法似乎不會一直回退
- 19. Sudoku算法與回溯不返回任何解決方案
- 20. 整理Java迴歸代碼用於回溯圖着色算法
- 21. ANTLR語法不是回溯
- 22. Needleman-Wunsch算法的動態編程實現中的回溯
- 23. 如何找到dfs +回溯算法的時間複雜度?
- 24. 回溯深度第一搜索算法僞代碼
- 25. Python的算法來解決triomines帶回溯
- 26. 通過回溯算法設置Java功能
- 27. 回溯算法是否被認爲是啓發式的?
- 28. 在smlnj中打開騎士的遊覽(回溯)算法
- 29. 四色地圖定理遞歸回溯算法
- 30. F#中的回溯算法:不變性如何工作?
如何挑選算法的下一個節點? – Alexander 2012-02-22 11:21:25
這是一個二叉樹,其中包含/排除元素,並嘗試每種可能的組合 – user1225640 2012-02-22 11:33:22