Notes for Lecture 9
Recursive Backtracking
Maze
Permute
简要
对于给定vector(v1)中的元素进行全排列 eg:{“a”,”b”,”c”}
解决方案
1.寻找自相似 对于给定数目元素的全排列问题,观察结果可见排列结果为各元素与其余元素全排列结果的全连接,类比骰子(每次骰子结果与其余骰子结果的全连接),但是骰子元素有重复,例如{1,1,1}。
2.采用另一vector(v2)来存储当前选择的元素,追踪连接结果
Recursion
- base case
v1为空时输出v2的全排列结果 - choice
遍历v1的各元素,将当前元素存储到v2中,记录连接结果 - explore
求其余元素的全排列结果 (注意是其余元素,因此需要先将当前选择的元素从v1中弹出) - unchoice backtracking
continue时需要恢复v1,v2原始状态
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 YunDid's Blog!
评论