贪心算法与正确性归纳证明

2021-11-16 From 忘归 By 江五渣

主要思想

贪心算法就是让计算机模拟一个「贪心的人」来做出决策。这个贪心的人是目光短浅的,他每次总是:

  • 只做出当前看来最好的选择
  • 只看眼前的利益,而不考虑做出选择后对未来造成的影响

并且他一旦做出了选择,就没有办法反悔(不可回溯),所以为了利益最大化,他需要保证绝不能做出错误的选择。

贪心算法不是从整体最优的角度上考虑问题,而是只在意某种意义上的局部最优解。因此,贪心算法并不能保证在所有情况下都能获得最优解。所以在使用贪心算法时,我们需要确保自己能证明最优解的正确性。

贪心性质

可以用贪心算法解决的题目需要满足以下性质:

  • 最优子结构:一个问题的最优解包含其子问题的最优解
  • 贪心选择性:所求问题的整体最优解可以通过一系列局部最优的选择来到达,即通过贪心选择来达到

证明方法

贪心算法最难的部分从不在于问题的求解,而在于正确性的证明,常用的证明方法有归纳法和交换论证法。

  • 归纳法:对算法进行步数归纳或问题规模归纳
  • 交换论证法:从最优解出发,在保证最优性不变的前提下,从一个最优解进行逐步替换,从而得到贪心策略的解

因篇幅有限,本篇我们主要说说归纳证明。归纳证明的本质其实就是数学归纳法,我们先来复习下数学归纳法吧。

数学归纳法

数学归纳法(Mathematical Induction)是一种数学证明方法,通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立。

证明步骤

最简单和常见的数学归纳法是证明当 n 等于任意一个自然数时某命题成立。证明分下面两步:

  1. 证明当 n = 1 时,命题成立
  2. 证明如果在 n = m(m 为任意自然数)时命题成立,那么可以推导出 n = m + 1 时命题也成立

1 为归纳基础,2 为归纳步骤。

原理

该方法的原理在于:一旦我们证明了在某个起点值(例如 n = 1)时命题成立,且证明出从一个值到下一个值的过程有效(即 n = m 到 n = m + 1),那么任意值都可以通过反复使用这个方法推导出来。即:

P(1)为真,P(1)为真,

且∀n,P(n)为真→P(n+1)为真且∀n,P(n)为真→P(n+1)为真

那么:

n=1,P(1)为真→P(2)为真n=1,P(1)为真→P(2)为真

n=2,P(2)为真→P(3)为真n=2,P(2)为真→P(3)为真

…………

举个例子

如果我们要证明对于任意自然数,都满足:

1+2+…+n=n×(1+n)21+2+…+n=n×(1+n)2

归纳基础

找到起始点,即 n = 1 时,此时等式左侧等于 1,右侧等于:

1×(1+1)2=22=11×(1+1)2=22=1

左右两侧相等,因此在 n = 1 时,命题成立。

归纳步骤

先假设:对于任意自然数 n 命题均成立。

那么,当 n = n + 1 时:

1+2+…+(n+1)1+2+…+(n+1)

=(1+2+…+n)+(n+1)=(1+2+…+n)+(n+1)

=n×(1+n)2+(n+1)=n×(1+n)2+(n+1)

=n×(1+n)2+2×(n+1)2=n×(1+n)2+2×(n+1)2

=(n+1)×(n+2)2=(n+1)×(n+2)2

因此,在 n = n + 1 时,命题也成立。证毕。

算法正确性归纳证明

归纳证明的证明步骤如下:

  1. 叙述一个有关自然数 n 的命题,该命题断定贪心策略的执行最终将导致最优解,其中自然数 n 可以代表算法步数或者问题规模。
  2. 证明该问题对所有自然数为真

其中,步骤二使用数学归纳法证明,即践行归纳基础与归纳步骤。

下面我们就来看下如何使用归纳法来证明 Kruskal 算法的正确性。

Kruskal 最小生成树

Kruskal 算法是一种常见并且好写的最小生成树算法,由 Kruskal 发明。该算法基于贪心思想,基本思想是从小到大加入边。

主要思想

  1. 将图的边按权值大小从小到大依次选取
  2. 选取权值最小的边 edge,假设构成该边的两个点为 (point1, point2),如果 point1 和 point2 已在一个连通图中,则舍弃该边;否则讲该边加入最小生成树中
  3. 重复步骤 2,直到构成最小生成树为止

正确性证明

叙述命题

首先,给出命题:对于任意 n,该算法对 n 阶图都能得到一棵最小生成树。

归纳基础

当 n = 2 时,此时只有一条边,命题显然为真。

归纳步骤

假设对于 n 个顶点的图,该算法正确,考虑 n + 1 个定点的图 GG,假设 GG 中最小边权为 e=i,je=i,j。

此时,在图 GG 中连接点 ii 与点 jj,得到图 G′G′。

根据归纳假设,由算法可推出:存在 G′G′ 的最小生成树 T′T′。令 T=T′⋃eT=T′⋃e,则 TT 是关于 GG 的最小生成树。

反证:若 TT 不是 GG 的最小生成树,那么必然存在某包含 ee 边的最小生成树 $T^,使得,使得W(T^) < W(T)(即(即T^*的边权小于的边权小于T$)。

此时,在 $T^中删除中删除e边,可得到G′的最小生成树边,可得到G′的最小生成树T^ - {e}$,且有:

$$
W(T^* - {e}) =

W(T^*) - w(e) <

W(T) - w(e) =

W(T’)
$$

该表达式与 T′T′ 是最优解相互矛盾,所以 TT 必然是 GG 的最小生成树,证毕。

总结

  • 贪心算法不是从整体最优的角度上考虑问题,而是只考虑某种意义上的局部最优解,不可回溯,不考虑后果
  • 可以用贪心解答的题目需要满足最优子结构与贪心选择性
  • 贪心算法并不能保证在所有情况下都能获得最优解,所以在使用贪心算法时需要证明算法的正确性,常见的证明方法有归纳法与交换论证法
  • 数学归纳法通常被用于证明某个给定命题在整个(或者局部)自然数范围内成立,证明过程为归纳基础+归纳步骤
  • 归纳证明需先给出命题,再用数学归纳法证明该命题对所有自然数为真

本文来源:忘归,转载请注明出处!

来源地址:http://jalan.space/2019/12/11/2019/greedy/

君子曰:学不可以已。
《知识图谱:方法、实践与应用》

知识图谱是较为典型的多学科交叉领域,涉及知识工程、自然语言处理、机器学习、图数据库等多个领域。《知识图谱:方法、实践与应用》系统地介绍知识图谱涉及的关键技术,如知识建模、关系抽取、图存储、自动推理、图谱表示学习、语义搜索、知识问答、图挖掘分析等。此外,本书还尝试将学术前沿和实战结合。

发表感想

© 2016 - 2022 chengxuzhixin.com All Rights Reserved.

浙ICP备2021034854号-1    浙公网安备 33011002016107号