问题：TSP问题（旅行售货员问题）
旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
方法:回溯法
#include<stdio.h> #define M 1000 int best_path = M; int best_path_x[] = { 0, 1, 2, 3 }; void swap(int*best_path_x, int i, int j)//交换函数 { int temp; temp = best_path_x[i]; best_path_x[i] = best_path_x[j]; best_path_x[j] = temp; } //参数说明：搜索的深度，当前路径权值，当前路径，邻接矩阵，层数 void TSP(int i, int path, int* path_x,int (*city)[4],int n) { if (i == n)//搜索完成。 { if (path + city[path_x[n - 1]][path_x[0]] < best_path) { best_path = path + city[path_x[i - 1]][path_x[0]]; for (int j = 0; j < n; j++) { best_path_x[j] = path_x[j]; } } } else//没搜索完成 { for (int j = i; j < n; j++) { if (path + city[path_x[i - 1]][path_x[j]]<best_path) {//满足条件，继续搜索。 swap(path_x, i, j); path += city[path_x[i - 1]][path_x[i]]; TSP(i + 1, path, path_x, city, n); path -= city[path_x[i - 1]][path_x[i]]; swap(path_x, i, j); } } } } int main() { int Adjacency[][4] = { { 0, 35, 6, 4 }, { 35, 0, 5, 10 }, { 6, 5, 0, 20 }, { 4, 10, 20, 0 }, }; int len1 = sizeof(Adjacency) / sizeof(Adjacency[0]); int len2 = sizeof(Adjacency[0]) / sizeof(Adjacency[0][0]); int source = 'A', path = 0, path_x[] = { 0, 1, 2, 3 }; printf("请输入起始节点："); scanf("%c", &source); source -= 'A'; swap(path_x, 0, source);//把起始节点作为第一个 printf("图的邻接矩阵：\n"); for (int i = 0; i <len1; i++) { for (int j = 0; j <len2; j++) { printf("%-3d", Adjacency[i][j]); } puts(""); } TSP(1,path,path_x,Adjacency,len1); printf("规划的最优路径的费用为：%d\n", best_path); printf("规划的最优路径为："); for (int i = 0; i < len1; i++) { printf("%c———>", 'A'+best_path_x[i]); } printf("%c", 'A'+source); return 0; }