# tsp

**Repository Path**: ipid/tsp

## Basic Information

- **Project Name**: tsp
- **Description**: 北京邮电大学（北邮/BUPT）《智能算法》旅行商问题实验，分别用蛮力法、回溯法、分支限界法、动态规划法求解了 TSP 问题。
- **Primary Language**: Unknown
- **License**: 0BSD
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 3
- **Forks**: 0
- **Created**: 2021-04-08
- **Last Updated**: 2023-08-26

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

<h1 align="center">旅行商问题实验</h1>
<p align="center">北京邮电大学<sup>北邮/BUPT</sup>《智能算法》课程 实验一<sup>by @ipid</sup></p>

<br>

在本仓库中，分别用蛮力法、回溯法、分支限界法、动态规划法求解了 TSP 问题。

TSP 问题可描述为如下问题：假设某地区有 N 个城市，每两个城市之间都有一条路，求从 0 号城市出发，不重复地经过所有城市，最后回到 0 号城市的最小距离。

<br>

## 样例输入

假设有 5 个城市，其路线如下图所示：

![TSP 样例输入](./assets/example.png)

```tsv
5
0 3 1 5 8
3 0 6 7 9
1 6 0 4 2
5 7 4 0 3
8 9 2 3 0
```

**注意：** 本代码在读取时会检测您输入的邻接矩阵是否对称。

<br>

## 样例输出

```python
最佳路线：[0, 1, 3, 4, 2, 0]
最佳路线总长度：16
```

**注：** `[0, 2, 1, 3, 4, 0]` 即为 A -> C -> B -> D -> E -> A。

<br>

## 版权声明

本项目在 0BSD 协议下开源。