第五讲---搜索和动态规划ppt课件.ppt

搜索与动态规划基础 深度优先搜索深度优先搜索属于图算法的一种, 英文缩写为DFS 即Depth First Search. 其过程简要来说是对每一个可能的分支路径深入到不能再深入为止, 而且每个节点只能访问一次.l 递归，回溯，暴力。l 就像走迷宫，走遍任何一条路径，碰到死路。l 走不了了，就回头找到最近的分叉路，走另一条。以此类推，直到找到出口。所以相当暴力，基本上比赛不会出太赤裸裸的暴力搜索。l 用暴力搜索的要小心的估算复杂度，不轻易写。