算法分析与设计-2012-2.ppt

算法分析与设计 第2讲 2012山东大学计算机学院 上一讲的主要内容 1 算法分析技术 问题 算法 程序 时间复杂性 空间复杂性 2 递归算法分析 递推方程解法 猜测法 其他解法 3 算法设计技术 分而治之 合并排序 merge sort 应用难 看什么具体问题 不要去机械地强硬地应用 顺着问题的特点去设计算法 4 问题 xn 冒泡排序 合并排序 比赛日程表 分治算法 2 2贪心技术 greedy 策略 计算机解决问题的策略 并非人解决问题的方法 有很多贪心策略算法 人们在设计算法是最先考虑的思想就应该是贪心思想 例子 硬币类型 25分 10分 5分 1分 将63分钱兑换成硬币问 最少兑换几枚硬币 贪心算法 25 25 10 1 1 1 先换大的后换小的 实际上以上解是最优的 与类型有关 25 25 10 1 1 1 11 5 1分三种硬币 兑换15分钱 贪心算法解为 11 1 1 1 1实际上 5 5 5是最优解 贪心解并不是最优解 贪心技术可以找到可行解 未必能找到最优解 如同现实生活中的局部利益与整体利益 寻求当前最好 未必全局最好 当前收益最大为目标 当前损失最小为目标 解决具体问题就要考虑以哪个参数来判断收益 11 1 1 1 1 人用来解决问题的思想 用于计算机解决问题 组装一个解 解有很多零件 先选那个零件 有个顺序 先选当前最有利的 就是所谓贪心 大学里的内容 Dijkstra最短路算法 Kruskal最小生成树算法 都是贪心算法 有时可以从多个参数中选择一个进行贪心优化求解 有时怎样选择需要精巧设计 有时虽然简单选择可达到目标 但需要复杂的证明 日常生活中也有很多例子 例2 1货郎问题 现在是非常有名的问题 以后会不断讨论旅游 经过所有城市 每个城市经过一次 仅一次 用城市排列表示 实例 城市集合C c1 c2 cn 距离d ci cj 1 i j n询问 求最短旅游回路 求一个城市排列 使排列对应的旅游长度最短 1 2 3 4 5 排列 4 1 3 2 5 开始 18 4 15 3 7 贪心算法也要有先有后 也有规则 通常是选择解 一点一点选 问题的解由很多部分组成 选择无其中一部分时采用贪心策略 由各部分组装成 把货郎旅游看作边得集合 贪心策略选择边 算法思想 优先选择可能导致货郎旅游的最短的边 逐渐形成回路 算法步骤 选择第一条边 选择第二条边 选择第3条边 先选一条最短的边 作为旅游第一条边 再选第二条边 在不破坏旅游情况下选择最短的 一直到最后一条边 选择一些边 形成旅游 最后要形成圈才行 先选 c4 c5 下一步选 c1 c2 c2 c3 c5 c6 三条边长相同 下一步选 c1 c3 不允许 只能选 c3 c4 最后只能选 c1 c6 得到货郎旅游为 C1 C2 C3 C4 C5 C6 C1长度为 50最短的货郎旅游是 C1 C3 C4 C5 C6 C2 C1长度为 先选 c4 c5 下一步选 c1 c2 c2 c3 c5 c6 三条边长相同 下一步选 c1 c3 不允许 只能选 c3 c4 最后只能选 c1 c6 得到货郎旅游为 C1 C2 C3 C4 C5 C6 C1长度为 50最短的货郎旅游是 C1 C3 C4 C5 C6 C2 C1长度为 先选 c4 c5 下一步选 c1 c2 c2 c3 c5 c6 三条边长相同 下一步选 c1 c3 不允许 只能选 c3 c4 最后只能选 c1 c6 得到货郎旅游为 C1 C2 C3 C4 C5 C6 C1长度为 50最短的货郎旅游是 C1 C3 C4 C5 C6 C2 C1长度为 先选 c4 c5 下一步选 c1 c2 c2 c3 c5 c6 三条边长相同 下一步选 c1 c3 不允许 只能选 c3 c4 最后只能选 c1 c6 得到货郎旅游为 C1 C2 C3 C4 C5 C6 C1长度为 50最短的货郎旅游是 C1 C3 C4 C5 C6 C2 C1长度为 先选 c4 c5 下一步选 c1 c2 c2 c3 c5 c6 三条边长相同 下一步选 c1 c3 不允许 只能选 c3 c4 最后只能选 c1 c6 得到货郎旅游为 C1 C2 C3 C4 C5 C6 C1长度为 50最短的货郎旅游是 C1 C3 C4 C5 C6 C2 C1长度为 48 39 2 3动态规划技术 DYNAMICprogramming 动态规划技术应用广泛 有许多问题需要设计动态规划算法 动态规划是为了寻求最优解 能寻找到最优解 遍历解空间中的所有解 从而找到所需要的或最优的解 开始很难理解 把所有解一点一点构造出来 构造所有可能的解 其中包含最优解 是一种找到最优解的方法 通过规划方法把所有可能是最优解的解规划出来 实际上要把问题实例的解一点一点组装起来 先组装规模小的实例的解 再逐渐增大实例规模 得到其解 要给出一种用小规模解组装大规模解的方法 例2 2 A B两组进行比赛 对于确定的n 哪组先胜n局则哪组获胜 A B能力相当 一局取胜概率都为1 2 P A胜 P B胜 1 2P i j A组需要取胜i局才能获胜 B组需要取胜j局才能获胜 在这种情况下 最终导致A取胜的概率 A还要取胜i局才行 B还要取胜j局才行 P i j 如 n 4 A已经胜2局 B已经胜1局 则i 2 j 3 此时A取胜的概率为P 2 3 某年某省的高考试题 有点类似 特殊情况 P i j 怎么计算 P 0 j 0 1 P i 0 0 0 P i 1 j A取胜一局后A最终取胜的概率 P i j 1 B取胜一局而A最终取胜的概率 概率计算公式 P i j 时间复杂度是多少 列出递推关系 编递归程序实现的话可能比较危险 时间复杂度可能是指数的 用下面方法分析 下面的递归算法容易给出 Probability i j 1 Ifi 0andj 0return1 2 Ifi 0andj 0return0 3 Ifi 0andj 0return i j n 求T n 时间复杂度 T 1 CT n 2T n 1 d i j n 因为要计算P i j 1 和P i 1 j 可以得到T n O 2n 但是可以设计另一个算法 下面的表就是一个算法 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 i j n T n Cn2 T n O n2 只需要算i j个方格的概率就可以了 动态规划的含义在哪里 后面的计算要用到前面的计算结果 必须存储中间结果 用到中间结果 一点一点算 从右下角往左上角依次计算 问题 货郎问题怎样设计动态规划算法 2 4回溯技术 Backtracking一棵树 从根开始 走遍所有节点 怎么走 要用到回溯技术 每个问题都是树搜索 数据库删除记录就要用到回溯算法 实现该程序较难 需要回溯 例子 两人x和o下棋的例子 分别以次往方格里面加入棋子 谁先站满一行一列或一斜行 列 则取胜 博弈树 PK树目标是为了讲搜索和回溯 为了决定下一步怎么走 必须搜索以后的多种可能性 所以搜索每一种下法 为了让计算机知道什么叫好什么叫坏 给每个搜索节点设置一个估价函数 原则是对一方有利则数值越大 另一方有利则数值越小 一个布局 布局的得分 得分函数 f 1 得分 1 胜0负 0 平 1 0胜 负 2 最大最小 选择对自己最有利的策略X会选择得分较大的分支 0会选择得分较小的分支 3 深度优先搜索 基本假设 每一方都选择对自己最有利的走法 3个相同符号形成一条线 就胜利了 最小节点 最大节点 最小节点 最大节点 1分 0分 0分 1分 1分 0分 0分 0分 1分 1分 X动作节点 得分取其子节点得分的最大值0动作节点 得分取其子节点得分的最小值考虑最坏情况所以最小最大计算 删除 上面搜索中 绿色圆圈节点的右子树不用搜索了 对一方有利一定对另一方不利 什么是 删除 什么是 删除 H G F E D C B K J I A 背景 人工智能土搜索中应用 图搜索的关键技术 删除 说明什么是与或树 规则 1 n的所有子节点均被赋值或删除 则节点n的暂时值变为最终值 2 n有暂时值s1 其子节点得到最终值s2 则n的暂时值变为 Max s1 s2 或min s1 s2 2分支定界还是以解答TSP问题的算法为例 以货郎问题tsp为例讲解什么是分支定界 首先要建立数学模型描述怎样搜索 然后考虑怎样搜索的节点少 搜索节点多了 就当问题大时就求不到解了 这种问题不再最小最大了 只求最小值 或最大值 什么是货郎问题 前面讲过了 求货郎旅游 最短的货郎旅游有多么短 建立一颗搜索树 设置一个启发函数 每个节点根据启发算法计算启发函数值 启发函数值比最优解值还优 启发函数设计并不容易 需要在实践中探索 关于顶点u邻接的两条最小长度边的长度之和 2 最小解值考虑两种情况 考虑两种情况 根节点的启发值 5 6 8 7 9 2 17 5 告诉我们的启发信息就是这个数值不会比最短的货郎旅游大 限制圈含有 a e 不含有 b c 则启发函数值为 9 6 9 7 10 2 20 5启发函数计算的时间复杂性是多少 满足条件的 a c a d a d b c b c c e d e b e 估计值小了 就不用搜索新节点了 目的是尽量减少搜索节点个数 从而加快找到最优解 当启发值超过现有解值时带有当前启发值的节点就不用继续搜索了 显然 BranchandBound a c a d a d b c b c c e d e b e a c a d a d b c b c c e d e b e 2 5局部搜索localsearch 遗传算法 演化算法 蚁群算法 本质上都带有局部搜索的含义 实际上前面自然演化算法真正计算时效果并不如局部搜索好 很多实验 大部分的实例局部搜索可以找到最优解 最小生成树的局部搜索方法 1 2 3 4 5 问题 证明这种方法能求得最小生成树 用 a d b c 代替 a b c d 看看解值是否比原来的小 小就替换 大就不替换了 总是看眼前利益 找到局部最优解 当前好就是好 有点像贪心算法 第三章 P类 NP类 NPC类 3 1问题与算法背景 计算机发明以后 人们想用计算机干所有事情 最重要的是用计算机模拟人的智能 即人工智能 人工智能中有许多问题 人们找不到很好的求解算法 困惑 想解释这个问题 从什么地方入手呢 需要说明 3 1问题与算法货郎问题优化形式 枚举法 没有讲实例 城市集合 C c1 c2 cm 距离 d ci cj Z ci cj C询问 求城市排列 c 1 c 2 c m 使得Min d c 1 c 2