决旅行商 TSP 问题
一、 实验任务和要求
1、 问题描述
本实验的目的是解决经典的旅行商问题（TSP, Traveling Salesman Problem），该问题是计算
机科学中的一个著名问题。在这个问题中，一个旅行商必须访问一组城市，每个城市仅访问一
次，并最终返回出发城市，目标是最小化总的旅行距离。这个问题是 NP-hard 问题，对于实际
的应用场景具有广泛的意义，比如物流配送、路线规划等。
在给定的程序中，实现了两种算法来解决 TSP 问题：
�穷举法（Brute Force）：这种方法尝试所有可能的路径组合，以找到最短路径。
�动态规划法：这种方法使用了动态规划的技术来减少计算的重复，通过记忆化搜索优化
了时间复杂度。
2、 设计问题求解的算法、并进行代码的编写、调试、运行。
穷举法：
� 代码中使用了递归函数 tsp_bruteforce 来生成所有可能的路径。
� 通过一个数组 visited 跟踪访问过的城市，以避免重复访问。
� 对于每条生成的路径，计算总长度，并与当前的最短路径进行比较，更新最短路径。
动态规划法：
� 使用二维数组 dp 来存储子问题的解，避免重复计算。
� tsp_dynamic_programming 函数通过递归方式计算给定起点和访问过的城市集合的最短
路径长度。
� 使用位掩码（bitmask）来高效地表示城市集合
旅行商问题.zip （4个子文件） 
1.c 4KB
测试数据复制粘贴即可.txt 292B
算法实验报告模板 - 副本(1)(1).doc 197KB
1.exe 132KB
