Electric Fences의 로컬 최적 점

Question

Usaco 문제 "Electric Fences"에 대한 해결책을 쓰고 있습니다. 문제에서 많은 양의 선들 중에서 한 점에 대한 최적의 위치를 ​​찾아야하므로 점 선분 거리의 합은 가능한 한 작습니다.

나는 힐 클라이밍을 할 수 있다는 아이디어가 있었으며, 모든 테스트 케이스에서 효과가있었습니다. 주어진 분석은 비슷한 방법을 사용했으나 왜 이것이 효과가 있는지 설명하지 못했습니다.

따라서 주어진 작업에서 지역 최적 값의 존재를 입증하거나 반증 할 수 없습니다. 유도를 사용하여 수행 할 수 있다는 생각이 들었지만 작동시키지 못했습니다. 나 좀 도와 줄 수있어?

정의

이 (X1, Y1, X2, Y2) linesegments 함수 최소화 즉, 점 (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) 

질문입니다 : 왜 이것이 글로벌 최적으로가는 도중에 어딘가에 갇히지 않는 이유는 무엇입니까? 무릎에 순진한 절차를 가져 오는 지역 언덕 꼭대기가없는 이유는 무엇입니까?

Answer 1

단일 선분에 대한 거리 함수가 convex function 인 경우 알고리즘의 정확성을 쉽게 증명할 수 있습니다. 이 경우의 Convex는 거리 함수를 표면 z = f (x, y)로 생각하면 표면 위의 볼륨을 채우면 볼록한 솔리드가 있음을 의미합니다. 단일 선 세그먼트로부터의 거리의 경우, 솔리드는 원추형 끝이있는 삼각형의 쐐기처럼 보입니다.

sum of convex functions is also convex이므로 여러 선분의 거리의 합은 볼록 함수가됩니다. 그러므로 발견되는 모든 지역 최소값도 함수가 볼록 함으로 전역 적이어야합니다.