2

我正在为 Usaco 问题“电栅栏”编写解决方案。在该问题中，您必须在大量线段中找到一个点的最佳位置，因此点-线段距离的总和尽可能小。

我有一个想法，也许可以进行爬山，并且它适用于所有测试用例。给定的分析使用了类似的方法，但没有解释为什么会这样。

因此，我仍然无法证明或反驳给定任务中局部最优的存在。我有一个想法，可以使用归纳法来完成，但我无法让它发挥作用。你能帮助我吗？

更新的定义

给定一组 (x1,y1,x2,y2) 线段，找到 (x,y) 点 P，使函数最小化：

def Val(x,y):
    d = 0
    for x1,y1,x2,y2 in LineSegments:
        if triangle (x1,y1,x2,y2,x,y) is not obtuse in (x1,y1) or (x2,y2):
            d += DistPointToLine(x,y,x1,y1,x2,y2)
        else:
            d += min(DistPointToPoint(x,y,x1,y1), DistPointToPoint(x,y,x2,y2))
    return d

由于某种原因，该问题仅包含一个局部最优值，因此可以使用以下过程来解决它：

precision = ((-0.1,0), (0.1,0), (0,-0.1), (0,0.1))
def Solve(precision=0.1):
    x = 0; y = 0
    best = Val(x,y)
    while True:
        for dx,dy in precision:
            if Val(x+dx, y+dy) > best:
                x += dx; y += dy
                best = Val(x,y)
                break
        else:
            break
    return (x,y)

问题是：为什么这不会在通往全局最优的道路上卡在某个地方？为什么没有当地的山顶可以让这种幼稚的程序屈服？

4

1 回答 1

3

如果我们注意到单个线段的距离函数是一个凸函数，就很容易证明算法的正确性。在这种情况下，凸意味着如果我们将距离函数视为曲面 z=f(x,y)，那么如果我们填充曲面上方的体积，我们将得到一个凸实体。在距单个线段的距离的情况下，实体看起来像一个带有锥形末端的三角形楔形。

由于凸函数之和也是凸函数，因此到多个线段的距离之和也将是凸函数。因此，由于函数是凸的，您找到的任何局部最小值也必须是全局最小值。

于 2010-02-24T20:01:34.047 回答