An Algorithm OF Minimum Cost Hamiltonian Circle

1. 전 제

Cost를 갖는 edge들에 대한 state space tree의 graph가 hamiltonian cycle이라면,
그 추가된 edge들에 대한 cost를 node로 하는 graph 또한 hamiltonian cycle이다.

2. 기본 전략

㈀ 주어진 Graph에 대해서 가장 낮은 cost를 갖는 edge를 추가시킨다.
㈁ Edge가 추가된 후 Graph가 hamiltonian cycle인지를 체크한다. 더 이상의 edge의 추가가 없으면 exit한다.
㈂ Hamiltonian cycle이면 edge들의 cost의 합을 저장한다. 이 저장된 값을 bounding 값으로 설정하고, 새로운 edge들의 cost가 이보다 큰지를 확인하면서(backtracking) 추가한다. 만약, 새로운 hemiltonian cycle가 생성된다면 새로운 hemiltonian cycle가 가지고 있는 cost의 합 을 새로운 bounding의 값을 재설정한다.
㈃ ㈁을 반복한다.
㈄ 모든 edge들이 visited되었을 때, 저장된 graph가 hamiltonian cycle이 되고, 종료한다.

3. Algorithm

Graph G;
struct EDGE added_edge[N];
int CostSum = 0; /* Graph에 추가된 edge들의 cost의 합 */
struct EDGE Hemil_Cycle; /* Hemiltonian cycle에 대한 타입설정 * /
int n; /* edge들의 수 */
int m; /* vertices들의 수 */
…