回溯法

发布于2021-04-15

上次编辑2021-04-15

Introduction

回溯法有 “通用解题法” 之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索过才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可以结束。

---

1. 《算法设计与分析》，王晓东，第五章《回溯法》 ↩

返回顶部

在手机上阅读