项目说明

本项目用于TSP算法评测、对比与可视化分析，包含数据加载、求解器、评估指标、统计分析与图表输出。

快速开始

python -m venv venv
source venv/bin/activate
pip install -r requirement.txt
python test.py

运行后会：

• 输出控制台评估日志
• 生成结果CSV（进度与最优）
• 生成可视化图表与GIF/PNG到outputs目录

目录结构

• loader.py：数据加载与实例工厂
• solver.py：算法实现
• metric.py：评估指标
• evaluation.py：评测逻辑
• visualization.py：图表与GIF/PNG输出
• test.py：测试入口
• ground_truth.py: 测试数据生成
• archive/: 运行结果存档
• outputs/: 输出目录

使用测试数据

使用工厂实例获取对应的数据：

from loader import TSPInstanceFactory

# 初始化工厂
factory = TSPInstanceFactory("tsp_instances_solved.csv")

# 获取所有实例
all_instances = factory.get_all()

评测流程

见test.py

拓展

1. 新增求解算法

在 solver.py 中继承 TSPSolver 并实现 solve():

• 输入：TSPInstance, time_limit
• 输出：tour, runtime, memory

solve()中用tracemalloc计算内存

然后在test.py的solvers列表中注册。

2. 新增评估指标

在metric.py中继承Metric并实现calculate()。 再在test.py中为evaluator.add_metric(...)注册即可。

3. 扩展可视化

在visualization.py中新增绘图函数, 并在generate_analysis()中调用。 输出会自动写入outputs/。

4. Ground Truth

使用random生成输入数据，再使用Google Ortools求解.

pip install ortools

评估指标

• 运行时间 - outputs/evaluation_results_all.csv + evaluation_results_best.csv
• 最优差距 - outputs/evaluation_results_all.csv + evaluation_results_best.csv + outputs/gap_bar.png + outputs/gap_heatmap_type.png + outputs/gap_heatmap_size_label.png
• 边匹配率 - outputs/evaluation_results_all.csv + evaluation_results_best.csv
• 路径长度 - outputs/evaluation_results_all.csv + evaluation_results_best.csv
• 稳定性 (均值、标准差) - outputs/gap_boxplot.png
• 内存消耗 - outputs/evaluation_results_all.csv + evaluation_results_best.csv
• 可扩展性分析 (按城市数, 按类型/规模结构) - outputs/runtime_heatmap_size.png + outputs/gap_heatmap_type.png + outputs/gap_heatmap_size_label.png
• 理论与实验一致性 (log-log 拟合分析时间增长趋势, 计算经验指数, 对比理论复杂度) - outputs/theory_empirical_loglog.png + outputs/theory_empirical_summary.csv
• 显著性统计分析 - outputs/significance_tests.csv + outputs/gap_boxplot.png
• 算法性能预测模型 - outputs/runtime_prediction.png + outputs/runtime_prediction_model.csv
• 路径可视化 - outputs/gifs/{solver}/{instance}_best_len{X}.gif + .png
• 方差
• 优势区间分析
• 收敛速度