[Python] 19171번 Euclid

https://www.acmicpc.net/problem/19171

---

 

24/07/29

 

 

어제부터 잡았던 문제인데, 사실 개뻘짓을 하고 있음을 깨달아서 그냥 어이 없어서 적어본다.

---

 

문제 접근 방식:

 

 

문제에서 요구하는 것은, 세 점 $p_1, p_2, p_3$가 주어지고 어떤 점 $p$에 대하여, $p$와 세 점 사이의 거리의 합이 최소가 될 때, 그 거리의 합을 구하는 것이다.

 

$p_1, p_2, p_3 = (x_1, y_1, z_1), (x_2, y_2, z_2), (x_3, y_3, z_3)$라고 둔다면 다음과 같은 함수를 최소화하는 문제로 바뀐다.

 

$$\begin{align} f(x, y, z) &= \sqrt{(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2} \\ &+ \sqrt{(x-x_2)^2 + (y-y_2)^2 + (z-z_2)^2} \\ &+ \sqrt{(x-x_3)^2 + (y-y_3)^2 + (z-z_3)^2}\end{align}$$

 

$f$는 convex하고 differentiable하기 때문에 gradient descent method를 사용할 수 있다.

 

따라서, $\nabla f$를 구해보자. 편의 상 $f(x, y, z)$의 첫 번째 줄의 값을 $P$, 두 번째 줄의 값을 $Q$, 세 번째 줄의 값을 $R$이라고 해보자.

 

$$\begin{align} \nabla f &= \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}, \frac{\partial f}{\partial z} \right) \\ &= \left( \frac{x-x_1}{P} + \frac{x-x_2}{Q} + \frac{x-x_3}{R}, \frac{y-y_1}{P} + \frac{y-y_2}{Q} + \frac{y-y_3}{R}, \frac{z-z_1}{P} + \frac{z-z_2}{Q} + \frac{z-z_3}{R} \right) \end{align}$$

 

이때, $P, Q, R$중 하나의 값이 $0$이 된다면 $\nabla f$는 정의되지 않는다.

 

즉, 우리가 잡은 $x, y, z$의 값이 문제에서 주어진 $p_1, p_2, p_3$의 좌표 중 하나라도 일치한다면 경사 하강법의 반복을 멈추면 된다.

 

여기서 개뻘짓을 했는데, 그것은 learning rate, 즉, $\nabla f$에 곱하는 일정한 상수 $\gamma$를 1보다 항상 작도록 조정한 것이었다.

 

ML이나 DL을 공부하다보면 learning rate가 그리 크지 않은 경우가 많은데, 나의 경우도 learning rate가 1보다 작도록 해서 틀린 것이었다.

 

learning rate 크기를 범위에 맞도록 크게 설정해준다면 충분히 빠르게 수렴할 수 있을 것이다.

 

참고로 경사 하강법을 사용하지 않아도 위의 문제는 삼각형의 페르마 포인트를 구하는 문제이므로, 순수한 계산으로 Closed form을 구할 수 있다.

 

근데 나는 경사 하강법으로 푸는 것이 더 쉬운 풀이라고 생각하긴 한다...

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 19171번 Euclid
# 경사 하강법
import sys
input = sys.stdin.readline

x1, y1, z1 = map(int, input().split())
x2, y2, z2 = map(int, input().split())
x3, y3, z3 = map(int, input().split())

a, b, c = (x1+x2+x3)/3, (y1+y2+y3)/3, (z1+z2+z3)/3

def f(x, y, z):
    p = ((x-x1)**2+(y-y1)**2+(z-z1)**2)**.5
    q = ((x-x2)**2+(y-y2)**2+(z-z2)**2)**.5
    r = ((x-x3)**2+(y-y3)**2+(z-z3)**2)**.5
    return p+q+r

def grad_f(x, y, z):
    p = ((x-x1)**2+(y-y1)**2+(z-z1)**2)**.5
    q = ((x-x2)**2+(y-y2)**2+(z-z2)**2)**.5
    r = ((x-x3)**2+(y-y3)**2+(z-z3)**2)**.5
    rfrx = (x-x1)/p + (x-x2)/q + (x-x3)/r
    rfry = (y-y1)/p + (y-y2)/q + (y-y3)/r
    rfrz = (z-z1)/p + (z-z2)/q + (z-z3)/r
    return (rfrx, rfry, rfrz)

def gradient_descent(p, decay_rate, weight, max_iter):
    x, y, z = p
    try:
        for _ in range(max_iter):
            dx, dy, dz = grad_f(x, y, z)
            x, y, z = x - weight*dx, y - weight*dy, z - weight*dz
            weight *= decay_rate
    except:
        pass
    return f(x, y, z)

print(gradient_descent((a, b, c), 0.999, 1000000, 20000))