局部搜索与全局搜索策略在TSP问题中的应用

# 1. 旅行商问题（TSP）基础知识

## 1.1 旅行商问题概述
旅行商问题是一个著名的组合优化问题，描述了一个旅行商要访问一系列城市并回到起点的最短路径规划。TSP在实际生活中有着广泛的应用，如物流配送、电路板布线等领域。其复杂度随着城市数量增加而呈指数增长，因此寻找高效的求解算法至关重要。

## 1.2 TSP问题的数学建模
TSP问题可以用图论中的有向完全图表示，节点表示城市，边表示城市间的距离。目标是找到一条路径经过所有节点且距离最短。数学建模通常采用邻接矩阵或距离矩阵表示城市间距离，优化目标是最小化路径长度或总旅行成本。常用的评价指标包括总路径长度、路径耗费等。

# 2. 基本的搜索算法

### 2.1 穷举法在TSP问题中的应用
在解决旅行商问题时，一种直观但非常耗时的方法是穷举法。穷举法简单易懂，即尝试列举出所有可能的路径，然后计算每条路径的总成本，最终选取最短路径作为最优解。然而，随着城市数量增加，穷举法需要计算的路径数量呈指数级增长，导致计算量巨大，不适用于大规模的TSP问题。

# Python 代码示例：穷举法求解TSP问题
import itertools

def calculate_cost(path, graph):
    cost = 0
    for i in range(len(path) - 1):
        cost += graph[path[i]][path[i+1]]
    cost += graph[path[-1]][path[0]]  # 回到起点
    return cost

def brute_force_tsp(graph):
    n = len(graph)
    min_cost = float('inf')
    min_path = []
    for path in itertools.permutations(range(n)):
        cost = calculate_cost(path, graph)
        if cost < min_cost:
            min_cost = cost
            min_path = path
    return min_path, min_cost

### 2.2 贪婪法的原理与局限性
贪婪算法是一种启发式算法，它每次选择最优的局部解，并希望通过局部最优解的积累达到全局最优解。在TSP中，贪婪法会从初始节点出发，每次选择最近的未访问城市作为下一个访问节点，直至所有城市都被访问。尽管贪婪法计算简单，但常常不能得到最优解，容易陷入局部最优解而无法跳出。

// Java 代码示例：贪婪算法解决TSP问题
public int[] greedyTSP(int[][] graph) {
    int n = graph.length;
    int[] path = new int[n];
    boolean[] visited = new boolean[n];
    path[0] = 0;  // 从第一个城市出发
    visited[0] = true;
    for (int i = 1; i < n; i++) {
        int minCost = Integer.MAX_VALUE;
        int nextCity = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[path[i-1]][j] < minCost) {
                minCost = graph[path[i-1]][j];
                nextCity = j;
            }
        }
        path[i] = nextCity;
        visited[nextCity] = true;
    }
    return path;
}

以上是关于基本的搜索算法穷举法和贪婪法在TSP问题中的介绍以及简单代码示例，这两种算法各有优劣，可