79 lines
2.6 KiB
C
79 lines
2.6 KiB
C
#include <stdio.h>
|
|
#include <limits.h>
|
|
#define MAX_CITIES 4 // 设定城市数量为4
|
|
#define INF INT_MAX
|
|
int n = MAX_CITIES; // 城市数量
|
|
int dist[MAX_CITIES][MAX_CITIES] = { // 距离矩阵
|
|
{0, 30, 6, 4}, // 城市 0 到其他城市的距离
|
|
{30, 0, 5, 10}, // 城市 1 到其他城市的距离
|
|
{6, 5, 0, 20}, // 城市 2 到其他城市的距离
|
|
{4, 10, 20, 0} // 城市 3 到其他城市的距离
|
|
};
|
|
int bestPath[MAX_CITIES]; // 最优路径
|
|
int bestCost = INF; // 最优路径的总成本
|
|
// 计算从节点current到下一个节点的界限
|
|
int calculateLowerBound(int path[], int current) {
|
|
int lowerBound = 0;
|
|
int visited[MAX_CITIES] = {0};
|
|
// 计算已访问的路径的距离
|
|
for (int i = 0; i < current; i++) {
|
|
lowerBound += dist[path[i]][path[i + 1]];
|
|
visited[path[i]] = 1;
|
|
}
|
|
// 计算当前节点到其他未访问节点的最短距离
|
|
for (int i = 0; i < n; i++) {
|
|
if (!visited[i]) {
|
|
int minDist = INF;
|
|
for (int j = 0; j < n; j++) {
|
|
if (!visited[j] && dist[i][j] < minDist) {
|
|
minDist = dist[i][j];
|
|
}
|
|
}
|
|
lowerBound += minDist;
|
|
}
|
|
}
|
|
return lowerBound;
|
|
}
|
|
// 分支限界法求解TSP
|
|
void branchAndBound(int path[], int current, int cost) {
|
|
if (current == n) {
|
|
// 所有城市都已访问，检查是否是最优解
|
|
cost += dist[path[current - 1]][path[0]]; // 加上返回起点的距离
|
|
if (cost < bestCost) {
|
|
bestCost = cost;
|
|
for (int i = 0; i < n; i++) {
|
|
bestPath[i] = path[i];
|
|
}
|
|
}
|
|
return;
|
|
}
|
|
// 计算当前路径的界限
|
|
int lowerBound = cost + calculateLowerBound(path, current);
|
|
// 如果当前解已经不可能优于最优解，剪枝
|
|
if (lowerBound >= bestCost) return;
|
|
// 继续扩展路径
|
|
for (int i = 0; i < n; i++) {
|
|
int flag = 0;
|
|
for (int j = 0; j < current; j++) {
|
|
if (path[j] == i) {
|
|
flag = 1; // 检查当前城市是否已访问
|
|
break;
|
|
}
|
|
}
|
|
if (flag == 0) {
|
|
path[current] = i;
|
|
branchAndBound(path, current + 1, cost + dist[path[current - 1]][i]);
|
|
}
|
|
}
|
|
}
|
|
int main() {
|
|
int path[MAX_CITIES];
|
|
path[0] = 0; // 从第一个城市出发
|
|
branchAndBound(path, 1, 0);
|
|
printf("\n最优路径是: ");
|
|
for (int i = 0; i < n; i++)
|
|
printf("%d ", bestPath[i]);
|
|
printf("\n总路程: %d\n", bestCost);
|
|
return 0;
|
|
}
|