AI를 위한 필수 수학

424

AI

를 위한 필수 수학

변분법에 관한 입문용 예제

변분법에 관한 다른 입문용 예제들로 적절한 (변분 원리를 통해 ) 에너지 함수를 최소화하여 해

결할 수 있는 문제에는 최소 면적 문제와 등방성

isoperimetric

문제가 있다.

10.5

네트워크상에서의 최적화

사실 선형 최적화를 위한 단체법보다 네트워크 최적화 설명부터 시작하고 싶었다. 왜냐하면 운

영 연구 애플리케이션에서 네트워크 구조가 많이 등장함에도 불구하고 이를 그래프나 네트워

크 구조보다 대수적 형태 (방정식 및 함수로 )로 생각하는 데 익숙한 사람들이 많기 때문이다.

그래프 모델 그 자체에 매우 익숙해질 필요가 있다. 네트워크 구조의 최적화 문제는 본질적으

로

O

(

n

!)

의 시간 복잡도를 가지고 조합적인 성격을 띈다. 결국 이를 우회하여 검색 공간을 효

율적으로 탐색할 수 있는 알고리즘이 필요하다 (문제의 차수는 대개 최악의 경우를 가정한 것

이며, 이 최악의 경우에는 대략적인 해결책으로도 충분하다는 점을 기억하자 ).

다양한 실제 애플리케이션에서 발생하는 일반적인 네트워크 문제에 대해 논의하려고 한다. 외

판원 문제는 가장 오래되고 유명한 문제이므로 여기서부터 시작해보겠다. 우리는 앞서 언급한

모든 문제를 해결할 수 있는 강력한 알고리즘과 오픈 소스 소프트웨어 패키지, 클라우드 컴퓨

팅 자원을 가진 시대에 살고 있다. 따라서 여기서는 해당 문제를 해결하기 위해 고안된 알고리

즘보다는 네트워크 문제의 유형과 그 응용에 중점을 둘 것이다.

10.5.1

외판원 문제

외판원 문제

traveling ...