# Algorithm-experiment

**Repository Path**: zhu-fengkai/algorithm-experiment

## Basic Information

- **Project Name**: Algorithm-experiment
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-05-15
- **Last Updated**: 2025-06-03

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Algorithm-experiment  

## 代码文件说明
```dp-tspd.cpp```  

**算法实现：**    
- 实现第一步 DP，计算最短卡车路径 ，时间复杂度
- 实现第二步 DP，生成高效操作，结合无人机路径，考虑 k 限制
- 实现第三步 DP，计算最优解，时间复杂度
- 实现算法，基于最小生成树下界优化搜索，降低运行时间   

**输入参数：**  
- 节点数 n：GR17 为 17，P01 为 15
- 距离矩阵：n*n矩阵，卡车距离c(v ,w )，无人机距离c'(v, w) = c(v, w) / a
- a = 2：无人机速度是卡车速度的两倍
- k：卡车节点数限制，取值{0, 1, 2, 4, infinity}  

**输出参数：**  
- 运行时间（秒）：每种方法（DP 和 A*）在不同k值下的运行时间。
- 解成本Z^k ：给定k时的路径成本。
- 偏差detla%：与最优 TSP 解的偏差百分比
- 节点分配：卡车节点数（TruckNodes）和无人机节点数（DroneNodes）
- 等待时间：卡车等待时间（TruckWaiting）和无人机等待时间（DroneWaiting）
- 总结指标：平均偏差（Avg Delta%）、最大偏差（Max Delta%）、最优解次数（#opt）  

**主要功能模块：**  
- readDistanceMatrix：读取距离矩阵，确保对角线为0，无效路径为 INF
- computeDroneDistance：计算无人机距离
- shortestTruckPath：第一步 DP，计算卡车最短路径
- efficientOperation：第二步 DP，生成高效操作
- optimalSolutionDP：第三步 DP，计算最优解并回溯路径
- optimalSolutionAStar：A* 优化算法，基于启发式搜索
- runExperiment：运行实验，记录结果并保存到文件  
- 
**用途：**  
- 复现论文中的 TSP-D 算法实验，验证运行时间、解质量、无人机比例和等待时间
- 提供可扩展的代码框架，支持不同规模的数据集测试。

## 数据文件说明  
```dp_tspd-FUS-01(gr17).txt ``` 
数据来源于*Florida State University(FSU)*  
```dp_tspd-TSPLIB-02(p01).txt  ```
数据来源于*TSP LIB(TSPLIB)*  
格式为txt文本文件  
内容为 17^2 / 15^2 对称距离矩阵，用空格分隔，表示城市间距离  

## 结果文件说明  
以下两个输出文件都是基于dp-tspd.cpp运行data中不同数据的结果
```dp_tspd-FUS-01-17.txt  ```
```dp_tspd-TSPLIB-02-15.txt```  
输出为文本文件，内容为结构化的实验结果  
每行表示一个实验配置的结果，字段以逗号和等号分隔，包含运行时间、解成本、偏差等指标  
**参数指标：**  
1. Time：运行时间（秒）  
2. Z^K：给定k的解成本  
3. Delta%：解成本与最优 TSP 解的偏差百分比  
4. TruckNodes 和 DroneNodes：卡车和无人机覆盖的节点数  
5. TruckWaiting 和 DroneWaiting：卡车和无人机的等待时间（基于路径成本估算）  
6. Summary：平均偏差（Avg Delta%）、最大偏差（Max Delta%）、找到最优解的次数（#opt）  
7. k：卡车节点数限制  

**实验结果作用：**  
两个输出文件记录了 TSP-D 算法在不同k值下的运行时间和解质量  
1. 运行时间趋势:随飞增加，运行时间减少，A*方法优于DP  
2. 解质量:Z、随k增加接近最优解，偏差逐渐减小  
3. 无人机比例:约47%-50%，符合论文预期  
4. 等待时间:卡车等待时间高于无人机，符合协同路径特性