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

《算法分析与设计-2012-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计第2讲-2012山东大学计算机学院上一讲的主要内容(1)算法分析技术，问题，算法，程序，时间复杂性，空间复杂性。(2)递归算法分析，递推方程解法。猜测法，其他解法。(3)算法设计技术，分而治之。合并排序，merge-sort。应用难，看什么具体问题，不要去机械地强硬地应用，顺着问题的特点去设计算法。(4)问题：xn，冒泡排序，合并排序，比赛日程表。分治算法。§2.2贪心技术(greedy)策略：计算机解决问题的策略，并非人解决问题的方法，有很多贪心策略算法。人们在设计算法是最先考虑

2、的思想就应该是贪心思想。例子：硬币类型，25分，10分，5分，1分。将63分钱兑换成硬币问：最少兑换几枚硬币？贪心算法：25，25，10，1，1，1，先换大的后换小的。实际上以上解是最优的，与类型有关。25105125251011111，5，1分三种硬币，兑换15分钱，贪心算法解为：11，1，1，1，1实际上，5，5，5是最优解。贪心解并不是最优解。贪心技术可以找到可行解，未必能找到最优解。如同现实生活中的局部利益与整体利益。寻求当前最好，未必全局最好。当前收益最大为目标/当前损失最小为目标。解

3、决具体问题就要考虑以哪个参数来判断收益。1151111111555人用来解决问题的思想,用于计算机解决问题。组装一个解，解有很多零件，先选那个零件，有个顺序，先选当前最有利的，就是所谓贪心。大学里的内容，Dijkstra最短路算法，Kruskal最小生成树算法，都是贪心算法。有时可以从多个参数中选择一个进行贪心优化求解，有时怎样选择需要精巧设计，有时虽然简单选择可达到目标，但需要复杂的证明。日常生活中也有很多例子。例2.1货郎问题，现在是非常有名的问题，以后会不断讨论旅游：经过所有城市，每个城市

4、经过一次，仅一次。用城市排列表示。实例：城市集合C={c1,c2,…,cn}，距离d(ci,cj)，1i

5、一条边；选择第二条边；选择第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

6、)，下一步选(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,

7、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)

8、,不允许。只能选(c3,c4)，最后只能选(c1,c6)。得到货郎旅游为：C1,C2,C3,C4,C5,C6,C1长度为：50最短的货郎旅游是：C1,C3,C4,C5,C6,C2,C1长度为：48.39§2.3动态规划技术(DYNAMICprogramming)动态规划技术应用广泛，有许多问题需要设计动态规划算法。动态规划是为了寻求最优解，能寻找到最优解。遍历解空间中的所有解，从而找到所需要的或最优的解。开始很难理解。把所有解一点一点构造出来，构造所有可能的解，其中包含最优解。是一种找到最优解的