■ 巡回セールスマン問題（平成18年秋午後2問1）
/*
* ソフトウェア開発技術者
* 平成18年度秋午後2問1
*
* 巡回セールスマン問題
*
*/
#include <stdio.h>
#define SETSUMON 1 /* 0:設問3, 1:設問2(2) */
#define mod(k,n) ((k)%(n))
#define floor(k,n) ((k)/(n))
#define true 1
#define false 0
#define X 32767 /* 十分大きな値 */
#if SETSUMON==0
#define n 4 /* ノードの数 */
int D[n][n] = {
{ X, 55, 50, 70 },
{ 55, X, 60, 120 },
{ 50, 60, X, 65 },
{ 70, 120, 65, X },
};
#else
#define n 5 /* ノードの数 */
int D[n][n] = {
{ X, 5, 4, 8, 7 },
{ 5, X, 7, 5, 7 },
{ 4, 7, X, 8, 2 },
{ 8, 5, 8, X, 4 },
{ 7, 7, 2, 4, X },
};
#endif
int tour[n], length;
/* Nearest Neighbor 法 */
void Nearest_Neighbor(void)
{
int visited[n], min, min_j, current;
int i, j;
for (i = 0; i <= n - 1; i++)
visited[i] = false; /* 初期化 */
current = 0;
for (i = 0; i <= n - 1; i++) {
tour[i] = current;
visited[current] = true;
min = X;
for (j = 0; j <= n - 1; j++) {
if (visited[j] == false && D[current][j] < min) {
min = D[current][j];
min_j = j;
}
}
current = min_j;
}
length = 0;
for (i = 0; i <= n - 1; i++) /* 巡回路の重みの算出 */
length = length + D[tour[i]][tour[mod(i+1,n)]];
}
/* 2-opt による改良 */
void step_two(int start)
{
int i, j, k, diff, temp;
for (i = start; i <= start + n - 1; i++) {
for (k = i + 2; k <= i + n - 2; k++) {
diff = (D[tour[mod(i,n)]][tour[mod(i+1,n)]]
+ D[tour[mod(k,n)]][tour[mod(k+1,n)]])
- (D[tour[mod(i,n)]][tour[mod(k,n)]]
+ D[tour[mod(i+1,n)]][tour[mod(k+1,n)]]);
if (diff > 0) { /* より重みの小さい巡回路が見出された */
length = length - diff;
for (j = 0; j <= floor(k-i,2) - 1; j++) {
/* 巡回路の一部分を反転する */
temp = tour[mod(i+1+j,n)];
tour[mod(i+1+j,n)] = tour[mod(k-j,n)];
tour[mod(k-j,n)] = temp;
}
return;
}
}
}
}
/* 表示 */
void print(void)
{
int i;
printf("巡回路の重み:%d [", length);
for (i = 0; i < n; i++)
printf("%d->", tour[i]);
printf("%d]\n", tour[0]);
}
/* テスト */
int main()
{
Nearest_Neighbor();
print();
step_two(1);
print();
return 0;
}