首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >理解获得多项式时间算法的几何改进方法

问理解获得多项式时间算法的几何改进方法
EN

Stack Overflow用户
提问于 2020-09-11 08:38:47
回答 1查看 76关注 0票数 1

我正在阅读网络流-理论,算法和应用,并且我被困在证明以下定理(Ch。第3页,67页):

定理。假设在算法的??ℎ迭代中,?^?是最小化问题某解的目标函数值,?^∗是最小目标函数值。此外,假设该算法保证对于每个迭代?,

(1) (?^?−?^(?+1))≥?(?^?−?^∗)

(即,对于0<?<1(与问题数据无关)的某个常数?,迭代?+1的改进至少是总可能改进的?倍)。然后,该算法在/?)迭代中终止,其中?是最大和最小目标函数值之间的差。

证据。数量(?^?−?^∗)表示在??ℎ迭代之后目标函数值的总可能改进。考虑从迭代?开始的2/?迭代的连续序列。如果算法的每次迭代都将目标函数值提高至少?(?^?−?^∗(/2)个单位,则算法将在这些2/?迭代中确定最优解。相反,假设在某个迭代/2+ 1处,该算法将目标函数值改进了小于?(?^?−?^∗)个单位。换句话说,

(2) /2(?^?−?^(?+1)≤?(?^?−?^∗)。

不等式(1)意味着

(3)?+1(?(?^?−?^∗)≤?^?−?^)

不等式(2)和(3)意味着

(?^?−?^∗)≤(?^?−?^∗)/2,

因此,该算法将总可能改进(?^?−?^∗)减少了至少2倍。因此,我们已经证明,在2/?连续迭代内,该算法要么获得最优解,要么将总可能改进减少至少2倍。由于?是最大可能的改进,并且每个目标函数值都是整数,因此该算法必须在?((????)迭代内终止。

为什么作者关注2/a迭代?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-09-11 09:03:09

我认为这样写是为了让计算机科学家更容易理解,我们每2/α轮将整数减半,因此2/α轮超级轮次的数量将是O(对数)。没有特别的理由我们不能更直接地做数学计算:

代码语言:javascript
复制
T(n) is the gap between the nth solution and an optimal solution.

T(n) ≤ (1 - α) T(n-1) [assumption]


                   n
T(n) ≤ T(0) (1 - α)   [by induction]

              -α n                 x
     < T(0) (e  )     [by 1 + x < e  for x ≠ 0]


                       -α (ln T(0))/α
T((ln T(0))/α) < T(0) e

               = 1,

所以(ln T(0))/α循环就足够了。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/63839341

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档