?? small_tsp.cpp
字號(hào):
#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <time.h>
#include <conio.h>
#define MAX_NUM 20
double s_citys[MAX_NUM][2];
double s_distances[MAX_NUM][MAX_NUM];
int s_num = 0;
double s_min = 1e200;
int s_indexMin[MAX_NUM];
int s_index[MAX_NUM];
bool s_mark[MAX_NUM];
bool ReadFile()
{
FILE * fp = fopen("citys.txt", "r");
if(fp)
{
s_num = 0;
while(!feof(fp) && s_num < MAX_NUM)
{
fscanf(fp, "%lf, %lf\n", &s_citys[s_num][0], &s_citys[s_num][1]);
s_num++;
}
fclose(fp);
return true;
}
return false;
}
void Search(int index)
{
int i, j;
double sum;
for(i = 1; i < s_num; i++)
{
if(s_mark[i])
{
s_index[index] = i;
s_mark[i] = false;
if(index == s_num - 1)
{
// 計(jì)算總距離
sum = 0.0;
for(j = 0;j < s_num - 1; j++)
{
sum += s_distances[s_index[j]][s_index[j + 1]];
}
sum += s_distances[s_index[s_num - 1]][s_index[0]];
if(sum < s_min)
{
memcpy(s_indexMin, s_index, sizeof(s_index));
s_min = sum;
}
}
else
{
Search(index + 1);
}
s_mark[i] = true;
}
}
}
void WriteFile()
{
FILE * fp = fopen("result.txt", "w");
if(fp)
{
for(int i = 0; i < s_num; i++)
{
fprintf(fp, "%d\n", s_indexMin[i]);
}
fclose(fp);
}
}
void main()
{
int i, j;
if(ReadFile())
{
time_t start, end;
double timeUsed;
time(&start);
printf("開始窮舉,請(qǐng)等待...");
for(i = 1; i < s_num; i++)
{
for(j = 0; j < i; j++)
{
s_distances[i][j] =
sqrt(
(s_citys[i][0] - s_citys[j][0]) * (s_citys[i][0] - s_citys[j][0]) +
(s_citys[i][1] - s_citys[j][1]) * (s_citys[i][1] - s_citys[j][1]));
s_distances[j][i] = s_distances[i][j];
}
}
s_min = 1e200;
s_index[0] = 0;
memset(s_mark, true, sizeof(s_mark));
s_mark[0] = false;
Search(1);
time(&end);
timeUsed = difftime(end, start);
if(timeUsed < 1.0)
{
printf("\n用時(shí)小于1秒!\n");
}
else
{
printf("\n用時(shí)%.0lf秒!\n", timeUsed);
}
printf("\n最短行程%lf\n", s_min);
printf("最佳訪問序列:\n");
for(int i = 0; i < s_num; i++)
{
printf("%02d\n", s_indexMin[i]);
}
WriteFile();
printf("按任意鍵繼續(xù)...");
getch();
}
else
{
printf("讀取文件失敗");
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -