Traveling Salesman Problem(Traveling Sales-Person Problem)
minimization optimization
조합 최적화 문제
택배 배달 시스템. 1,000개 boxes -> 가장 먼저 퇴근경로?
h-value estimation in TSP
Minimization Optimization: h = under-estimate
-> TSP : under-estimation ==> 실수 X. incorrect prune X.
-> 0 < h < h* < infinite -> h = h* - alpha(smaller)
#include <iostream>
using namespace std;
const int N = 4; // 노드 수
int final_path[N + 1]; // 경로 저장 배열
bool visited[N]; // 경로 방문 여부 체크
int final_res = INT_MAX; // 최종 값 == 모든 노드를 방문하고 시작 노드로 돌아왔을 때 값 <- 주기적 update
void copyToFinal(int curr_path[])
{
for (int i = 0; i < N; i++) final_path[i] = curr_path[i];
final_path[N] = curr_path[0];
}
int firstMin(int adj[N][N], int i)
{
int min = INT_MAX;
for (int k = 0; k < N; k++)
if (adj[i][k] < min && i != k) min = adj[i][k]; // i 에서 출발하는 경로 중 제일 작은 값 (본인 노드 제외)
return min;
}
int secondMin(int adj[N][N], int i) // i 에서 출발하는 경로 중 두번째로 작은 값 (본인 노드 제외)
{
int first = INT_MAX, second = INT_MAX;
for (int j = 0; j < N; j++)
{
if (i == j)
continue;
if (adj[i][j] <= first)
{
second = first;
first = adj[i][j];
}
else if (adj[i][j] <= second && adj[i][j] != first) second = adj[i][j];
}
return second;
}
// curr_bound -> h, curr_weight-> g
void TSPRec(int adj[N][N], int curr_bound, int curr_weight, int level, int curr_path[])
{
if (level == N) // 모든 노드 방문 했다
{
if (adj[curr_path[level - 1]][curr_path[0]] != 0) // 마지막 노드에서 시작 노드(0) 으로 돌아갈 수 있는 경로 있는지 체크
{
int curr_res = curr_weight + adj[curr_path[level - 1]][curr_path[0]];
if (curr_res < final_res)
{
copyToFinal(curr_path);
final_res = curr_res;
}
}
return;
}
for (int i = 0; i < N; i++)
{
if (adj[curr_path[level - 1]][i] != 0 && visited[i] == false) // 자신 노드x || 이미 방문한 노드 x
{
int temp = curr_bound;
curr_weight += adj[curr_path[level - 1]][i];
if (level == 1)
curr_bound -= ((firstMin(adj, curr_path[level - 1]) + firstMin(adj, i)) / 2);
else
curr_bound -= ((secondMin(adj, curr_path[level - 1]) + firstMin(adj, i)) / 2);
if (curr_bound + curr_weight < final_res) // f = g(curr_weight) + h(curr_bound) 가 final_res보다 작으면 더 탐색 필요하다.
{
curr_path[level] = i;
visited[i] = true;
TSPRec(adj, curr_bound, curr_weight, level + 1, curr_path);
}
// 위로 올라가는 것
curr_weight -= adj[curr_path[level - 1]][i];
curr_bound = temp;
memset(visited, false, sizeof(visited));
for (int j = 0; j <= level - 1; j++)
visited[curr_path[j]] = true;
}
}
}
void TSP(int adj[N][N])
{
int curr_path[N + 1];
int curr_bound = 0;
memset(curr_path, -1, sizeof(curr_path));
memset(visited, 0, sizeof(curr_path));
for (int i = 0; i < N; i++)
curr_bound += (firstMin(adj, i) + secondMin(adj, i));
curr_bound = (curr_bound & 1) ? curr_bound / 2 + 1 : curr_bound / 2;
visited[0] = true; // 시작노드 0 으로 fix
curr_path[0] = 0;
TSPRec(adj, curr_bound, 0, 1, curr_path);
}
Example: 5-cityp TSP(비대칭, fully connected)
B&B (f=g+h)
g: actual edge costs (exact)
h: h* - alpha.
B&B (BFS) for 5-city TSP and Bound function
h-value: not fixed.
1. TSP >= min. outgoing edges of node A
2. TSP >= min. incoming edges of node B
--> 가장 min.edge로 나가고, 가장 min.edge로 들어온다.
==> h < h*. 연결이 안되었어도 최저면 되기 때문에 예측
h1: 무조건 제일 작은 outgoing edges로 연결되는 것을 추정
h2: h1을 활용하되, 이미 지나온 노드는 배제하여 추정.
V1: starting node (fixed)
h3: "in general, bound function is NOT unique"
1) min. cost of entering v2 = min of 2nd column.
2) min. cost of exiting v2 = min of 2nd row
==> avg: min cost of v2 = [(1) + (2)] / 2
Further issues (advanced issues) for B&B
-----------------------------------------------------------------
1. Branch factor and DFS/BFS
: A(branch factor가 넓음) B(branch factor가 좁고 depth가 깊다()
- A+Backtracking and B+B&B
- A+B&B and B+Backtracking
Q: Branch factor는 큰 것이 or 작은 것이 좋은가?
== Tree visit type과 관계있다.
== Branch factor는 알고리즘 설계와 관련있음 (DFS, BFS)
==> Root에서 가까이 어떤 아이템을 먼저 배치할 것인가.
2. h-value estimation: h = h* +/- alpha.
: 그렇지만 매우 구체적인 가이드라인이 없는가?
: (인공지능) Relaxation Technique.
Relaxation == Simplification : Constraint 제거.
==> Ex. 0/1 KS: h-value 유도.
--> (relax) 제약조건: sack에 item을 (0 or 1)로 담는다.
---------> item을 나누어 담을 수 있다.
============> h-value = fractional KS == h*. h*을 실제 문제의 h값으로 가져옴.
3. What if |V|=n is HUGE in TSP?
: ex. n=number of cities of in US
==> NEW design approach is required.
==> 왜 문제가 어렵고, 어떻게 다른 접근?
NP class problems ==> Approximation algorithms.
Questions:
1. h2와 h3의 비교우위를 논하시오.
2. search tree를 그리면서 답변하시오.
3. 각 incoming/outgoing edges ==> 1/2 계산 이슈?