我正在为 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)
问题是:为什么这不会在实现全局最优的过程中陷入困境?为什么没有本地的山顶来让这个幼稚的过程屈服?
最佳答案
如果我们注意到单个线段的距离函数是convex function,那么很容易证明算法的正确性。 。在这种情况下,凸意味着如果我们将距离函数视为表面 z=f(x,y),那么如果我们填充表面上方的体积,我们就会得到一个凸实体。在距单线段距离的情况下,实体看起来像一个带有圆锥形末端的三角形楔子。
自 sum of convex functions is also convex ,那么多条线段的距离之和也将是凸函数。因此,由于函数是凸函数,您找到的任何局部最小值也必定是全局最小值。
关于math - 电子围栏的局部最优,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2255889/