algo_lec18

 

Example 5: Traveling Salesman Problem (TSP)

문제 설명

• 목표: 각 도시를 정확히 한 번 방문하고 출발 도시로 돌아오는 최단 경로를 찾는 것
• 도시 집합: V={v1,v2,v3,v4,v5}
• 입력: 인접 행렬 (도시 간 거리)
• 제약: 도시 중복 방문 금지, 시작점과 종점은 동일

상태 공간 트리 구성 방식

• 루트 노드: 시작 도시 (예: 1)
• 각 수준(level)은 다음 방문 도시를 의미
• 경로 예시:
  • [1,2] = 1 → 2
  • [1,2,3] = 1 → 2 → 3
  • 리프 노드: 모든 도시 방문 + 다시 시작점 복귀 → 경로 길이 평가 대상

LC B&B 적용

• Compute the bound for each node
  • bound means the lower bound path length by expanding the node 
  • If bound > best sol., the node is NOT promising
• Bound 계산 방식:
  • 경로 길이 [1,...,k]까지의 총 거리에 대하여

 

 

 

 

예시: 노드 [1,2]의 bound

• 현재까지 경로가 v₁ → v₂일 때, 앞으로 남은 경로를 고려한 최소 가능한 전체 비용의 추정값(bound)을 계산.

(c) v₂는 제외 + 본인 제외 → min값 계산

[이미 결정된 이동]
v₁ → v₂ = 14 ; 고정된 실제 이동 경로이므로 반드시 포함됨 → (a)

[남은 도시들(v₃, v₄, v₅)에 대한 예측 비용]
v₂: 아직 다음 이동이 미정이므로,
→ v₂ → 나머지 중 최소 거리 = min(7, 8, 7) = 7 → (b)

v₃: 아직 방문하지 않음.
→ v₃ → 나머지 도시 중 최소 거리 = min(4, 7, 16) = 4 → (c)

v₄: min(11, 9, 2) = 2 → (c)
v₅: min(18, 17, 4) = 4 → (c)

 

예시: 노드 [1,2,3]의 bound

(c): v2 와 v3 제외 + 본인 제외 → min값 계산

 

Example 5: TSP with LC B&B

• Set the root node using v1 (Bound = 21, minLen = ∞ )
  • Node [1,2] (Bound = 31)
  • Node [1,3] (Bound = 22)
  • Node [1,4] (Bound = 30)
  • Node [1,5] (Bound = ?)
• Visit the node with the lowest bound (i.e., [1,3])

 

• Node [1,3,2] (Bound = 22)
• Node [1,3,4] (Bound = 37)
• Node [1,3,5] (Bound = 39)
• Node [1,3,2] with the lowest bound

 

• Node [1,3,2,4]
  • As we reach the leaf node, compare the path length
  • Since 37 < ∞, minLen = 37
  • Prune [1,3,8], [1,5] as 39>37
• Node [1,3,2,5]
  • Since 31<37, minLen = 31
  • Prune [1,2] as 31 = 31
• For the next, Node [1,3,4]
• Repeat these and get the min path which is 30

 

Efficiency

• The total count of state space tree: 1 + 4 + 4 × 3 + 4 × 3 × 2 = 41

단계	설명	노드 수
레벨 0	시작 노드 [1]	1
레벨 1	[1, x] → 도시 2~5 중 1개 선택	4
레벨 2	[1, x, y] → 남은 3개 중 선택	4×3 = 12
레벨 3	[1, x, y, z] → 남은 2개 중 선택	4×3×2 = 24
총합		1 + 4 + 12 + 24 = 41

 

• The total count of pruned state space tree: 17

 

Changes in bound

• Start with ∞ (i.e., minLen = ∞ )

• All the nodes before getting the first complete route should be promising

• After getting the first complete traveling route, the bound is increasing, leading to more pruning

남은 노드들은 점점 bound가 높아지는 경향이 있음
→ pruning이 더 자주 발생하게 되며,
→ 전체 탐색 노드를 크게 줄이는 효과