「旅行商问题 TSP 动态规划 贪心算法 数据结构 Java 代码」

旅行商问题（TSP）—— 从问题建模到经典算法实现（数据结构视角）

旅行商问题（Traveling Salesman Problem, TSP）是组合优化领域的经典NP难问题，核心目标是找到一条经过所有城市且仅经过一次、最终回到起点的最短路径。本文从数据结构角度出发，梳理TSP的问题定义与建模方式，详解暴力枚举、动态规划、贪心算法三类基础解法的原理、数据结构选型，对比不同算法的时间复杂度与适用场景，为算法爱好者和学习者提供清晰的实践参考。

一、 旅行商问题的定义与建模

1.1 问题描述 给定n个城市和两两之间的距离，旅行商需要从某一城市出发，遍历所有城市一次且仅一次，最后返回出发城市，求总路程最短的路径。

1.2 数据结构建模 TSP的核心是存储城市间的距离关系，常用以下两种数据结构： 邻接矩阵：用n×n的二维数组dist[i][j]表示城市i到城市j的距离，若i=j则dist[i][j]=0；适用于城市数量较少（n≤20）的场景，查询距离的时间复杂度为O(1)。 邻接表：用链表或数组列表存储每个城市可达的城市及对应距离，适用于稀疏图场景，能节省存储空间；但查询任意两城市距离的时间复杂度为O(n)。 注：本文示例均采用邻接矩阵建模，因为其更直观适配TSP的经典算法实现。

二、 经典算法实现（Java版）

2.1 暴力枚举法 — 全排列遍历（穷举所有路径） 原理 枚举所有城市的全排列，计算每条排列对应路径的总距离，筛选出最小值。 数据结构选型 - 用一维数组存储城市的排列组合（如path = [0,2,1,3]表示路径0→2→1→3→0）。 用邻接矩阵存储城市间距离。

代码运行结果截图 （IDEA中暴力枚举法代码运行的控制台输出截图）

复杂度分析 - 时间复杂度：O(n!)，n为城市数量，仅适用于n≤10的极小规模场景。 - 邻接矩阵存储城市间距离。