About TSP

TSP(Traveling Salesman Problem)

minimization optimization problem

The most widely-used combinational optimization problem in Computer Science.

ex) 택배 배달 시스템,1000개의 박스들. → 가장 먼저 퇴근하는 경로?

h-value 가 역시 중요!

Minimization Optimization

h = under-estimate

→ 실수하지 않는다. 잘못된 pruning을 하지 않는다.

→ 0 < h < h* < infinite : h = h* - alpha(the smaller the great)

(h: optimal한 h value)*

h-value for TSP

For under estimation,

when move node A → B,

• A에서는 가장 cost가 작은 edge로 나가고, B에서는 가장 cost가 작은 edge로 들어오는 것을 가정.
• 새로운 state에서 h값을 계산할 때는 이미 지나온 edge를 고려하여 이는 배제하고 계산한다.

위 2가지를 기본으로 하여 h function을 설계한다.

일반적으로 h-function은 unique하지 않다.

Vertex 하나의 out-going edge와 in-coming edge를 고려하여(방향 그래프의 경우) average를 구하는 것이 좋은 h-value가 될 수도 있다.

B&B에서 더 생각해 볼만한 문제

Branch factor and DFS/BFS

다수의 branch factor를 가지면서 DFS를 진행하는 것과,

소수의 branch factor를 가지면서 BFS를 진행하는 것 중

어느 것이 더 좋은가? → 생각해 봐야할 문제.

Q: Branch factor는 큰 것이 좋은가, 작은 것이 좋은가?

• 트리를 어떻게 방문하는 가 와 관련있다.
• 트리가 어떤 구조를 가지는가 와 관련있다.
• Root 가까이 어떤 아이템을 먼저 배치할 것인가(정렬)와 관련있다.

h-value에 대한 더 구체적인 가이드라인은 없는가?

인공지능에 Relaxation Technique 라는 것이 있다.

Relaxation == Simplification: constraint 제거.

예) 0/1 KS 문제에서 제약 조건을 제거하면, fractional하게 아이템을 담을 수 있다.

바로 이 optimal value 를 constraint 가 있는 상황에서의 h-value 로 사용하는 것!!

만약 탐색할 정점의 개수가 매우 많아진다면?

새로운 접근 방법이 필요하다!!