AI를 위한 필수 수학

426

AI

를 위한 필수 수학

그림

10-2

동일한 그래프에서 최소 스패닝 트리와 외판원 문제

없다. 여기서 휴리스틱한 방법은 훌륭한 근사 방법을 제공할 수 있다. 또한 분기 및 절단

cut

접

근법을 기반으로 하는 훌륭한 알고리즘은 매우 많은 수의 도시에 대해 이 문제를 최적으로 해

결했다.

10.5.2

최소 스패닝 트리

가끔 이 두 가지를 혼동하는 경우가 있기 때문에 최소 신장 트리 문제를 외판원 문제 바로 뒤에

배치했다. 여기서 둘 간의 혼동을 없애보자. 우리는 각 엣지에 양수의 가중치가 있는 완전 연결

네트워크를 활용하는데 이는 다시 거리, 시간, 사용량 또는 수도, 전기, 전화선과 같은 인프라

구조의 연결 비용을 나타낼 수 있다. 외판원 문제와 마찬가지로 그래프의 모든 노드를 포함하

면서 총 가중치의 합을 최소화하는 엣지 집합을 찾고자 한다. 두 쌍의 노드 사이에 경로를 제공

하는 방식으로 엣지 집합을 선택해야 하는데, 이는 다른 노드에서 그래프의 모든 노드에 도달

할 수 있어야 한다는 의미다. 외판원 문제에서는 모든 도시를 한 번만 방문한 다음 시작 도시로

돌아가야 하므로 각 노드가 두 개 이상의 엣지를 가질 수 없다. 반면 스패닝 트리에서는 이러한

조건이 없다. 외판원 문제에서 마지막 도시로 돌아간다는 사실은 스패닝 트리에선 회로에 필요

없는 폐쇄 ...