数学归纳法与解题之道.ppt

数学归纳法与解题之道,道,贪心,构造,优化,如此之多的算法，是怎样想到的？ 这些算法巧诚巧矣，可正确性怎么证明呢？,引言,道生一，一生二，二生三，三生万物。,老子：道德经,数学归纳法,概览,2.在证明算法正确性上的应用 贪心算法 其他算法,3.在构造性算法中的应用 数据结构的恢复性构造 策略与解决方案的构造,4.数学归纳法与算法优化 巧妙选择归纳对象 力求完善归纳基础 慎重选择归纳方向 适当加强归纳假设,5.启发作用与美学价值,6.问题与缺陷 理论上是否欠完备 应用上是否较繁琐 不适用的问题,1.关于数学归纳法 简短的回顾 基本的定理、概念与方法 是总结更是探索,例5（线性结构）Set Cover 例6（树状结构）Roman Roads,难,缺乏固定套路 依赖于具体的数据结构,通用灵活 适用于各种数据结构,易,构造性问题,数学归纳法,【例5】Set Cover 数据结构的恢复性构造,子集覆盖问题定义为选出尽量少的子集，使已知集合中的每个元素至少属于其中的一个。 线段覆盖问题定义为选出尽量少的整点，使给定的每条线段上都至少有其中的一个。 以整点为子集，所有包含这个整点的线段为子集中的元素，可以把一个线段覆盖问题归约到子集覆盖问题。如果给定一个由线段覆盖问题归约成的子集覆盖问题，该怎么解决呢？,线段覆盖问题,在数轴上选出尽量少的整点 给定的每条线段上必须至少有其中的一个 按左端点排序后有简单的贪心算法,转化成子集覆盖问题,整点作为集合（实际上只需每线段的右端点） 所有包含此整点的线段为其元素 一般的子集覆盖问题NP完全,1,2,3,4,5,1,2,2,3,3,4,4,5,5,怎么办？,恢复线性结构,直接搜索,Tips：只需要恢复线段的位置关系和每个线段的右端点,定义线段的位置,线段的位置即为其中点的位置 两线段距离即为其中点的距离 两线段距离可以使用对应集合运算求出,两线段必须相交！,到底是“”还是“”？,问题：如何拓展连通分量？,我们把问题分为连通分量来处理 两个连通分量之间线段距离可以任意，不影响结论 每个连通分量的第一条线段位置任意,调整归纳假设,只有一条线段时方向无关紧要 初始时刻选择不同的方向只会使最终的结果互为轴对称而已。 其他情形中为了判断方向，我们需要调整归纳假设,同侧？异侧？,X与B在A的同侧的充分必要条件是他们在A之内的部分存在包含关系,同侧？异侧？,X与B在A的同侧的充分必要条件是他们在A之内的部分存在包含关系,线段的右端点,所有与A相交、在A右侧的线段与A的公共点,问题解决,小结,以上解题过程用庖丁解牛的方法步步推进，将问题分为多个部分，逐一化解 数学归纳法灵活的归纳假设为主要问题的求解提供了不少便利 算法实现中我们不断克服困难的过程正是归纳假设不断完善的过程,解题之道,故弄玄虚 简单自然,神来之笔 直剖核心,数学归纳法,从简单情形做起 从不同角度观察,与,谢谢,欢迎大家提问,