# 旅行商问题的遗传算法求近似解法

**Repository Path**: half_tree/tsp-solution

## Basic Information

- **Project Name**: 旅行商问题的遗传算法求近似解法
- **Description**: 本仓库储存本人的西北工业大学程序设计课程大作业——旅行商问题的遗传算法求近似解法。
- **Primary Language**: C++
- **License**: GPL-2.0
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-12-09
- **Last Updated**: 2024-12-09

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 西北工业大学程序设计课大作业 ~ 旅行商问题的遗传算法求近似解法
## 背景介绍
**旅行商问题（TSP）**是组合优化中的一个NP问题，在运筹学和计算机科学中非常重要。问题内容为：给定一系列城市和每对城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。

作为一个NP问题，旅行商问题是无法在多项式时间内给出解的。然而，我们可以**设计近似算法**来在可接受的时间代价内给出近似解。**遗传算法**即为一种广泛使用的近似算法。

遗传算法是一种计算机模拟算法，计算机将每一种可能的解视为一个个体，将所有解组成的集合视为种群。在TSP问题的一开始，计算机生成一些随机方案，然后再对所有的解进行迭代——类似于生物的进化：在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），基于这些个体的一些特性生成新的个体，淘汰旧的个体，该种群在算法的下一次迭代中成为当前种群。

每一轮迭代，我们都通过选择算法尝试让种群中更优的那一部分解进行杂交操作，以繁衍适应度（即更优）更好的一部分后代，类似于种群的进化。同时，我们还会模拟种群中的变异，以刺激种群产生新的可能解，避免算法陷入局部最优解。

以上是对于遗传算法的介绍，这也是*本程序*尝试给出TSP问题近似解的主要算法。实际上，遗传算法也是一个典型的启发式算法，算法通过当前的搜索状态在更有可能得到更优解的子分支上搜索，这样的方法可以降低时间成本，相关的算法在人工智能、机器学习领域也有相关应用（例如著名的A*寻路算法）。

## 构建程序
### 构建环境

- MinGW v8.0.1 Posix
- CMake v3.31

### 构建步骤

在程序目录下执行：
```sh
cmake -S . -B ./build -G "MinGW Makefiles"
cd ./build
cmake --build .
```

完成构建后，将生成`tsp-solution.exe`可执行文件。

### 直接下载二进制文件
在本仓库的Release页面下载程序包即可直接使用。

## 使用程序
请在可执行程序同目录下创建`city_test.txt`，并以`posX/posY/cityName`的格式输入城市的信息，一行一个，不允许末尾空行。

以下是一个示例，你也可以在Release的程序压缩包中找到同样的示例：
```
-100/-100/Alfa
-100/100/Bravo
100/100/Charlie
100/-100/Delta
-200/-200/Echo
-200/200/Foxtrot
200/200/Golf
200/-200/Hotel
-500/0/India
500/0/Juliett
```

*请注意：文件的编码格式应当为UTF-8，且尽量不要在城市名称中包括中文。*

填充好了`city_test.txt`后，打开可执行程序，并依照程序提示依次填入下列参数：
```
npucs2024302258 Program Design Homework
TSP Problem-Shooting Program
Enter The File of Cities Location >> city_test.txt
Enter The Max Round The Program Would Active >> 100000
Enter The Max Round The Program Would Culture On The Same Answer >> 40000
```
- 第一个参数代表读取城市的文件名，这里填写上方的`city_test.txt`；
- 第二个参数代表程序最大的迭代次数，请填写一个正整数；
- 第三个参数代表程序在发现程序超过指定迭代次数后答案未发生变化时停止迭代的最大迭代次数。

完成填写后，程序将会自动执行，并在屏幕上指示当前的迭代进度，最后给出一个近似结果，以下是一个示例。
```
The Final Solution >> The Distance Of The Final Solution Is 2750.695546
The Route Was :
City 0 >> Delta
City 1 >> Golf
City 2 >> Charlie
City 3 >> Bravo
City 4 >> Foxtrot
City 5 >> India
City 6 >> Echo
City 7 >> Alfa
City 8 >> Hotel
City 9 >> Juliett
City 10 >> Delta
It May Be A Possible Solution For The TSP Problem.
The Program Ended Here.
```

## 问题反馈
本项目作为我的大一程序设计大作业，大作业工期比较短，所以该项目的代码可读性和规范性可能不是很好，同时本项目可能也存在一些问题，若有人在程序中发现问题，可以向我反馈，感激不尽。

通过本仓库的Issue栏目即可反馈问题。