程序的灵魂——算法PPT课件.pptx

程序的灵魂 算法 2017 3 20张俊杰Csdnblog 3 24 2020 1 1 算法的概念 1 从2个问题开始1题目描述 农夫需要把狼 羊 菜和自己运到河对岸去 只有农夫能够划船 而且船比较小 除农夫之外每次只能运一种东西 还有一个棘手问题 就是如果没有农夫看着 羊会偷吃菜 狼会吃羊 请考虑一种方法 让农夫能够安全地安排这些东西和他自己过河 方法二农夫带羊过河农夫返回农夫带菜过河农夫带羊返回农夫带狼过河农夫返回农夫带羊过河 方法一农夫带羊过河农夫返回农夫带狼过河农夫带羊返回农夫带菜过河农夫返回农夫带羊过河 3 24 2020 2 2 鸡兔同笼问题问题描述 一群鸡兔在一个笼子 上数共有35个头 下有94只脚 问鸡 兔各有几只 解题步骤 1 设未知数 鸡x只 兔y只2 列方程组 352 4y 943 解得 23y 124 得到答案鸡23只 兔12只 算法是什么 3 24 2020 3 算法 按照一定规则解决一类问题的明确和有限的步骤 你能写出这个方程么 352 4y 94 能写出它的求解步骤么 1 1 1 2 2y 2 3 24 2020 4 2 如何设计算法 理解问题 1 确认算法类型 串行 并行 异构2 确认解法 精确 近似3 确定数据结构 选择算法设计策略设计算法 正确性证明 时间空间效率 可实现性验证 根据算法写出程序代码 3 24 2020 5 3 算法设计策略 贪心算法分治策略动态规划局部搜索其它 3 24 2020 6 3 1贪心算法 所谓贪心算法是指 在对问题求解时 总是做出在当前看来是最好的选择 也就是说 不从整体最优上加以考虑 他所做出的仅是在某种意义上的局部最优解 贪心算法没有固定的算法框架 算法设计的关键是贪心策略的选择 必须注意的是 贪心算法不是对所有问题都能得到整体最优解 选择的贪心策略必须具备无后效性 即某个状态以后的过程不会影响以前的状态 只与当前状态有关 所以对所采用的贪心策略一定要仔细分析其是否满足无后效性 普里姆算法 Prim算法 Dijkstra算法 典型应用 3 24 2020 7 典型应用 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题 这些子问题相互独立且与原问题性质相同 求出子问题的解 就可得到原问题的解 即一种分目标完成程序算法 3 2分治策略 归并排序 快速傅立叶变换 3 24 2020 8 动态规划算法通常用于求解具有某种最优性质的问题 在这类问题中 可能会有许多可行解 每一个解都对应于一个值 我们希望找到具有最优值的解 动态规划算法与分治法类似 其基本思想也是将待求解问题分解成若干个子问题 先求解子问题 然后从这些子问题的解得到原问题的解 与分治法不同的是 适合于用动态规划求解的问题 经分解得到子问题往往不是互相独立的 若用分治法来解这类问题 则分解得到的子问题数目太多 有些子问题被重复计算了很多次 如果我们能够保存已解决的子问题的答案 而在需要时再找出已求得的答案 这样就可以避免大量的重复计算 节省时间 我们可以用一个表来记录所有已解的子问题的答案 不管该子问题以后是否被用到 只要它被计算过 就将其结果填入表中 这就是动态规划法的基本思路 具体的动态规划算法多种多样 但它们具有相同的填表格式 与分治法最大的差别是 适合于用动态规划法求解的问题 经分解后得到的子问题往往不是互相独立的 即下一个子阶段的求解是建立在上一个子阶段的解的基础上 进行进一步的求解 3 3动态规划 典型应用 背包问题 全路径最短路径的Floyd算法 3 24 2020 9 典型应用 也叫回溯算法 试探法分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题 这些子问题相互独立且与原问题性质相同 求出子问题的解 就可得到原问题的解 即一种分目标完成程序算法 3 4局部搜索 A 算法 3 24 2020 10 3 5其它 随机算法分界界定网络流近似算