외판원 문제 알고리즘, 분기 한정법 (Branch and Bound) 해결 예제

외판원 문제 알고리즘, 분기 한정법 (Branch and Bound) 해결 예제

외판원 문제 알고리즘 해결 예제는 글 아래에 있고, 먼저 분기 한정법이란 무엇이며 어떻게 사용하는 것인지를 다룹니다.

[Branch and Bound] 분기 한정

이산이나 조합 최적화에서 최적의 해를 찾으려는 방법

- 인수 x에 대한 함수 f(x)의 최소 값을 찾는 것

  : 이때, f와 x는 임의의 값

분기를 위한 트리를 구성(Branch)한 뒤, 각 경로의 한계(Bound)를 구해 유망한 경로를 찾아냄 (Branch and Bound)

- 유망하다(Promising) = 최소 값을 보유한 경로

유망한 경로들의 값을 비교해 그 자식 경로로 방문해 최적의 해를 구함

- 이런 방법을 "분기 한정 가지치기 최고 우선 검색"이라고 함

- Best-first search with branch and bound pruning

[외판원 문제 알고리즘]

[Branch and Bound] 운용 비용 구하기

각각의 기계는 하나의 작업만 수행

4개의 기계와 4개의 작업 과정이 있다면,

- A는 넷, B는 셋, C는 둘, D는 한 가지 할당 방법이 존재

- 문제 해결을 위한 가능한 방법의 수(N),

  : N = 4 x 3 x 2 x 1 = 24가지 방법

  : 그러나, 작업의 수와 기계가 10개씩이라면, N = 3,6,28,800가지 방법이 존재

[분기한정법과 외판원 문제 알고리즘] 운용 비용 구하기

[Branch and Bound] 수행 단계

Branch (두 가지 방법을 사용)

- A 기계에 작업을 할당하는 방법.

- 작업 과정에서 A를 배제하는 방법.

Bound (한계 값 구하기)

- 경로를 비교한 뒤,

- 가장 낮은 비용이 드는 경로(최상의 경로)를 찾음

  : 높은 비용이 드는 경로를 Lower Bound(LB),

  : 낮은 비용이 드는 경로를 Upper Bound(UP)로 설정

Cut (버리기)

- 높은 비용이 드는 경로를 버림

  : 즉, Feasible이 아닌 경로를 버림

[Branch and Bound] 최소 운용비 문제

- Row의 최소 값의 합

- 기계와 작업을 위한 최소 비용

1. A, 1

[분기한정법] 최소 운용비 문제 1

[분기한정법] 최소 운용비 문제 1 테이블

2. B, 2

[분기한정법] 최소 운용비 문제 2

[분기한정법] 최소 운용비 문제 2 테이블

3. C, 3

[분기한정법] 최소 운용비 문제 3

[분기한정법] 최소 운용비 문제 3 테이블

[Branch and Bound] 최소 운용비 결과

[분기한정법] 최소 운용비 결과

[Branch and Bound] 외판원 문제

외판원은 여러 도시로 판매 출장을 계획

- 각 도시는 도로 등으로 연결이 되어 있음

- 출장 시간을 최소화하기 위한 경로를 찾아야 함

- 한 도시에서 다른 도시로 가는 거리는 각기 다름

  : A 도시에서 B 도시로 갔을 때와, B에서 A로 돌아오는 거리가 다를 수도 있음

최적의 해밀토니안 순환 경로를 찾는 문제와 같음

- 각각 연결된 무방향 그래프에서 모든 정점을 정확하게 한 번씩 방문하고 출발한 정점으로 되돌아 오는 경로를 말함

- 최적의 일 주 여행 경로(optimal tour)

판매를 위한 최적의 경로 탐색

- 경로의 길이에 대한 한계 값(하한)을 미리 구함

- 한계 값이 탐색 된 최적의 경로보다 크면 그 노드는 유망하지 않다

[분기한정법] 외판원 문제

[Branch and Bound] 외판원 문제 - 예

[외판원 문제 알고리즘]

[분기한정법] 외판원 문제 테이블

[분기한정법] 경로의 합

[분기한정법] 외판원 문제 결과

외판원 문제 알고리즘, 분기 한정법 (Branch and Bound) 해결 예제