Skip to content

Backtracking

"Backtracking"即"回溯法",除了本章,在下面章节中,也对它进行了论述:

一、Expert-labuladong\3.1-回溯算法(DFS算法)系列

TODO

https://www.geeksforgeeks.org/top-20-backtracking-algorithm-interview-questions/

Pattern Searching

在字符串(也叫主串)中的定位模式(pattern)问题可以使用回溯法进行解决,但是这种解法是naive的。优化方法是KMP算法,在下面两篇文章中对两种进行了比较分析:

1、cnblogs 详解KMP算法

eight queens puzzle

crosswords

verbal arithmetic

Sudoku

parsing

参见Compilers: Principles, Techniques, and Tools的4.4 Top-Down Parsing,其中介绍了使用backtrack来实现parsing。

在GitHub中,可以检索非常多的这种项目:

https://github.com/search?utf8=%E2%9C%93&q=backtrack+parse&type=