algorithm - 我如何想象 Primal-Dual Hill 攀登？

Question

在 Jeff Edmonds 的 How to Think About Algorithms 一文中，网络流和线性规划一章中有一节解释了 Primal-Dual Hill Climbing。我无法想象屋顶的指数数量以及为什么“最低且因此最佳的屋顶高于最高且因此最佳的站立位置”

Answer 1

我不是 100% 确定这是对的，但这是我的看法：给定您正在导航的特定丘陵拓扑，想象它的镜像漂浮在您上方的天空中。最高的山丘的顶部将向上延伸并与镜子最底部的山谷底部接触，该底部是从天空向下延伸的。相反，如果您向下导航到最低的山谷，您将最大化您与镜像中您正上方的点之间的距离。书中没有很好地解释，但这个镜像就是书中提到的“指数屋顶”。

无论如何，这个镜像被用作证明你已经达到全局最大值的基础。直观地说，证明是说，首先，镜像是原始问题的另一个实例，只是颠倒了。但是，天空中您上方镜像的存在使您可以区分局部最大值或全局最大值。如果你已经达到了一个特定的峰值，但你的头没有碰到它在天空中的“镜峰”，那么你已经达到了一个局部最大值。另一方面，如果由于峰顶撞到它的镜像而没有站立的空间，那么您知道您已经达到了全局最大值。

回到书中最初的描述，我认为这是有问题的，因为作者所描述的“指数屋顶”对我来说听起来像是一系列带有一堆凉亭的山丘，这是不对的。一个更好的描述将是一个完全相互镜像的石笋和钟乳石洞穴。