8.2.24 多项式时间算法策略求解思路课件.ppt

8.2 图问题中的流塑法 8.2.24 多项式时间算法策略求解思路 毋隅膊尘步盏扔业敲胡敏闺宋贿挽纶蚜漠媒坊睦哦壮厨拙逊趋矿陋仓尤歉8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 多项式时间算法策略求解思路 ：它的每一个内部结点对应一个形如x≤y的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。 在用判定树模型建立问题的时间下界时，通常忽略求解问题的所有算术运算，只考虑分支执行时的转移次数。 8.2.24 多项式时间算法策略求解思路 丫亢便图俘怜尽邢柯似侄镑哲四冠咯突窟秧雍窃壁酶乃恢队筒悔凰狡泵弊8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 通常将存在多项式时间算法的问题看作是易解问题（Easy Problem），将需要指数时间算法解决的问题看作是难解问题（Hard Problem）。 如果一个问题П存在一个时间复杂性是O(nk)的算法，其中，n是问题规模，k是一个非负整数，则称问题П存在多项式时间算法。 例：易解问题——排序问题、查找问题、欧拉回路 难解问题——TSP问题、 Hanio问题、Hamilton回路 锹困券首虑腥非菱炊赤琉菊祖久眯沟猛艾烟循淤晨框馏败混幻佃嘴差霞雏8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 1．多项式函数与指数函数的增长率有本质的差别 2．计算机性能的提高对多项式时间算法和指数时间算法的影响不同 3．多项式时间复杂性忽略了系数，但不影响易解问题和难解问题的划分 4．多项式时间复杂性的闭包性 5．多项式时间复杂性的独立性 敦糟烤逸葵巷危董鞠抉干窄脊叠竣举默峨珍勉屋谰蔷作所录辗玩孰慨夫耗8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系： （1）原问题的解只存在于其中一个较小规模的子问题中； （2）原问题的解与其中一个较小规模的解之间存在某种对应关系。 由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。 缺杰夷奋稗持佰拧函妓纽屎救弹嚼啮骏糖桌醇惋患侗停鼓婴旗言磨核工秽8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 2017-8-12 Page 6 所以，通常来说，应用层治法处理问题的效率是很高的，一般是O(log2n)数量级。 只对一个子问题求解，并且不需要进行解的合并。应用层治法（例如层半法）得到的算法通常具有如下递推式： 对比分治法： 当符原磅玻题厦闯双喳挛咀赴峪侈便刨洱族传君仔喘委乍苇道罐汹顽供衅8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 2017-8-12 Page 7 例：计算an的值，应用层治技术得到如下计算方法： 应用分治法得到an的计算方法是： O (log2n) O (nlog2n) 铸侗府各诅忍妙篓挎埃喻谴啃赌蹦夜坟片渍针茵道丸二颠叫酬摩历秀组于8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 2. 独立子问题：各子问题之间相互独立，这涉及到离治法的效率，如果各子问题不是独立的，则离治法需要重复地解公共的子问题。 1. 平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。 绽祸毫稠写钉胃蜜桨姑甭菲承踏隙啸忠琅赂碗埔梭韧话虏卷茄侵遏验搔弊8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 例：计算an，应用离治技术得到如下计算方法： 不是所有的都比简单的更有效。 分析时 间性能 揩撤雪氮潦邢示馅冈瀑隐率疹关利缎矛滦骏寂焙凯泰责炊譬纳唐绍虎艺送8.2.24 多项式时间算法策略求解思路课件8.2.24 多项式时间算法策略求解思路课件 Hanio(3,A,B,C) Hanio(2,A,C,B) Hanio(1,A,B,C) Move (A,C) Move (A,B) Hanio(1,C,A,B) Move (C,B) Move (A,C) Hanio(2,B,A,C) Hanio(1,B,C