贪心算法tspc语言代码
时间: 2024-05-31 10:05:39 浏览: 16
贪心算法是一种常用的解决最优化问题的算法,其基本思想是在每一步选择中都采取当前状态下最优的选择,以期最终达到全局最优解。TSP问题是一个著名的旅行商问题,即求解一条路径使得旅行商依次经过所有城市且回到起点的最短距离。下面给出一个简单的TSP问题的贪心算法的C语言代码实现:
```
#include<stdio.h>
#define INF 0x7fffffff
#define N 10
int graph[N][N] = {{0,10,20,30,40,50,60,70,80,90},
{10,0,15,25,35,45,55,65,75,85},
{20,15,0,45,55,60,75,80,85,90},
{30,25,45,0,65,75,85,90,95,100},
{40,35,55,65,0,25,35,45,55,65},
{50,45,60,75,25,0,30,40,50,60},
{60,55,75,85,35,30,0,15,25,35},
{70,65,80,90,45,40,15,0,20,30},
{80,75,85,95,55,50,25,20,0,10},
{90,85,90,100,65,60,35,30,10,0}}; // 代表城市之间的距离
int visited[N] = {0}; // 记录每个城市是否已经被访问
int main()
{
int start = 0; // 从第0个城市开始
int sum = 0; // 记录总距离
int cur = start; // 当前所在城市
visited[start] = 1; // 标记第一个城市已经被访问
printf("%d->", start); // 打印出发城市编号
for(int i=0;i<N-1;i++)
{
int min_dist = INF;
int next_city = -1;
for(int j=0;j<N;j++)
{
if(!visited[j] && graph[cur][j]<min_dist)
{
min_dist = graph[cur][j];
next_city = j;
}
}
sum += min_dist;
cur = next_city;
visited[cur] = 1;
printf("%d->", cur); // 打印下一个城市编号
}
sum += graph[cur][start]; // 加上回到起点的距离
printf("%d\n", start); // 打印回到起点的编号
printf("Total distance: %d\n", sum); // 打印总距离
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)