回溯法

1 minute read

回溯是一种算法技术,通过尝试增量地构建解决方案来递归地解决问题,一次一一片,删除那些在任何时间点都不能满足问题约束条件的解(这里的时间指的是指的是到达搜索树的任何级别所花费的时间)。

例如,考虑数独问题,我们尝试一个一个地填充数字。每当我们发现当前的数字不能导致一个解决方案,我们删除它(回溯),并尝试下一个数字。这比单纯的方法(生成所有可能的数字组合,然后一个接一个地尝试每个组合)要好,因为无论何时回溯,它都会抛出一组排列。

所以说我的理解是,回溯法的精髓就在与递归,如何优雅的递归,既保证能得到正确的答案又能在时间复杂度上有所优化。

数独问题

数独问题算是比较典型和比较难的回溯问题,但和其他的回溯法问题一样,我们要做的也是one by one的分配数字到空着的格子里,然后检查安全性,在检查安全性之后,我们分配这个数字,并递归地检查这个分配是否会产生一个解决方案。如果赋值没有得到解决方案,那么我们尝试对当前空单元格使用下一个数字。如果数字(1到9)中没有一个能得出答案,我们返回false。

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.