算法训练营 - 学习笔记 - 第七周

时间过得真快，算法训练营已经过了一半了，感觉自己还是学了就忘、什么都不会，时常会想起覃超老师的那些鸡血话：“三分听课、七分练习、五毒神掌、坚持、再坚持”。

不要死磕，要过遍数！

第 13 课 高级搜索

剪枝的实现和特性

简单搜索的进阶。

优化方式：不重复（Fibonacci）、剪枝（生成括号问题）

要把状态树结合起来，就好像每个人在人生的某个阶段都会面对不同的命运，不同的选择会有不同的人生轨迹。

剪枝

缓存已计算的结果或者剪掉差的分支。

国际象棋 - Deep Blue(深蓝) vs 卡斯特罗夫

三子棋、五子棋，棋感

深度学习（alpha go）https://nikcheerla.github.io/deeplearningschool/2018/01/01/AlphaZero-Explained/

回溯法： 分步 + 试错

剪枝实战题目解析：数独

• 爬楼梯问题

• 括号生成： 递归、DP（动态规划）

• N-Queens：剪枝+搜索

• if row == n

• append result

• for (col 0..n)

• if is valid

• drill down

• restore

• 有效的数独：检查数独棋盘是否合法

• 解数独：搜索 + 剪枝

• 3 个 set 分别来记录，行、列、块

• 方块索引 = （行 / 3 * 3）+ 列 / 3

双向 BFS 的实现、特性和题解

从起点到终点分别做 BFS(Breadth First Search) 搜索，然后在中间相遇。

实战题目

• word-ladder

启发式搜索(A*)的实现、特性和题解

Heuristic Search(A*)

优先级搜索

1. 估价函数，选择更优的路径

2. 与 BSP 相比，BFS 为傻扩散

Sliding Puzzle(8 Puzzles) 拼图游戏

• define moves, 方向变换向量

• DFS

• A*

• 曼哈顿距离