大多数时候,令人困惑的事实是,是否要进行详尽的搜索(动态编程或反向跟踪或蛮力)来解决问题或采用贪婪的方法.
我不是在谈论使用贪婪来确定最佳解决方案,我说的是使用贪婪算法来找到"解决方案".我试图找到一些标准的方法,我可以验证问题是否可以通过贪婪的方法解决.像Optimal子结构一样,用于动态编程的记忆.并没有任何具体问题.
有没有我可以做的归纳证明来决定贪婪方法是否总能产生最佳解决方案？
Hai*_*ile 28
为了证明使用贪婪算法可以解决优化问题,我们需要证明问题具有以下内容:
最优子结构属性:最优全局解包含所有子问题的最优解.
贪婪的选择属性:通过贪婪地选择局部最优选择可以获得全局最优解.
让我们考虑经典活动选择问题.我们拥有一套小号的ň活动,每一个与开始时间
s[i]和结束时间e[i].我们想要选择S的子集,使得选择最大化非重叠事件的数量.
使用贪婪算法可以解决这个问题,但我们怎样才能证明这一点？
我们需要展示它的展品:
考虑一般的活动一个包含在全局最优解S = {A', a, A''},其中S是全局最优解,一个是我们的小活动,并A'和A''有找到活动两个子问题之前和之后一个.
如果问题具有最优子属性,为子问题的最优解A'并且A''必须包含在全局最优解S.
这是真的,但为什么呢？
假设子问题的最优解A'不在S.然后我们可以用最优替代A',比如说S',A以获得一个更好的新的全局最优解S.但这S是全球最佳解决方案!矛盾.
我们需要证明我们贪婪的选择(选择先结束的活动)是正确的.
让我们B成为一个子问题.设b是B首先结束的子问题的活动,因此b是我们(第一个)贪婪的选择.我们需要证明b包含在一些最佳解决方案中B.
让我们X成为子问题的最佳解决方案B.让x成为X首先结束的活动.
如果b = x,那么b就是X最佳解B,我们已经证明贪婪的选择包含在最优解中.
如果b!= x,我们肯定有end_time[b] < end_time[x].
由于b是我们贪婪的选择(即首先在子问题中结束的活动B),因此我们可以x用b in 代替X以获得另一个最优解:X' = (X \ {x}) U {b}.X'是最优的,因为它具有相同数量的活动X,并且X是最佳的,并且在这种情况下,b是X'最佳解决方案B.
因此,我们贪婪的选择b包含B在一个案例或另一个案例的最佳解决方案中.
此外,还有一个强大的数学理论可以在某种情况下用于机械地证明特定问题可以通过贪婪的方法来解决.
简述:
可以定义名为matroid的特定组合结构.
一些聪明人在过去证明这些拟阵具有最优子结构属性和贪婪选择属性.
这意味着您可以对优化问题运行贪婪算法,它将找到最佳解决方案.您只需要验证您的问题是在类似matroid的结构上定义的.
有关这方面的更多信息,请点击此处.