第5章：回朔法 Backtracking Algorithm)
第5章：回朔法 （ Backtracking Algorithm）
知识要点 3掌握用回溯法解题的算法框架 Φ子集树算法框架 Φ排列树算法框架 ?了解NP完全问题 ΦNP完全问题的定义和研究意义 ?通过应用范例学习回溯法的设计策略 Φ0/1背包问题；旅行商问题(TSP);最优装载问题 Φ批收处理作业调度；连续邮资问题；圆排列问题 ΦN-皇后问题；最大团问题；图的m着色问题
知识要点 掌握用回溯法解题的算法框架 子集树算法框架 排列树算法框架 了解NP完全问题 NP完全问题的定义和研究意义 通过应用范例学习回溯法的设计策略 0/1背包问题；旅行商问题（TSP）；最优装载问题 批处理作业调度；连续邮资问题；圆排列问题 N-皇后问题；最大团问题；图的m着色问题
5.1回溯法算法框架 Backtracking Algorithm Paradigm
5.1 回溯法算法框架 （ Backtracking Algorithm Paradigm ）
·迷宫游戏 入口回溯 与 回溯 出口
回溯 回溯 入口 出口 回溯 ▪迷宫游戏 回溯
搜索算法 >对某些问题建立数学模型时，即使有一定的数学 模型，但采用数学方法解决有一定的困难。对于这 一 类试题，我们用模拟或搜索求解。 >在缺乏解决问题的有效模型时，搜索却是一种行 之有效的解决问题的基本方法。 枚举法（穷举法） 深度优先搜索（回溯法） 广度优先搜索
搜索算法 ➢对某些问题建立数学模型时，即使有一定的数学 模型，但采用数学方法解决有一定的困难。对于这 一类试题，我们用模拟或搜索求解。 ➢在缺乏解决问题的有效模型时，搜索却是一种行 之有效的解决问题的基本方法。 枚举法（穷举法） 深度优先搜索（回溯法） 广度优先搜索