# TSP

**Repository Path**: tensleep/tsp

## Basic Information

- **Project Name**: TSP
- **Description**: 旅行家问题相关的路径规划
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-07-28
- **Last Updated**: 2024-11-23

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README


路径规划问题

## com.zzs.App类

利用动态规划算法解决 旅行家问题，编写相关代码并成功执行，

## com.zzs.astar包

学习了AStar算法，计算两点间的路径

路程：
1、起点加入open
2、开始循环（如果 找到路径 或 open为空，结束循环）
    2.1、从open中找到 f 最小的节点，从 open 移动到 close 中，记该节点为ln
    2.2、找 ln 的所有邻居节点 nn
        1）如果 nn 节点不可达，过
        2）如果 nn 节点在 close 中，过
        3）如果 nn 节点不在 open 中，加入open
        4）如果 nn 节点在 open 中，若 ( ln.g + (ln -> nn) ) < nn.g，更新 nn 的 g 和 parent
3、循环结束，判断是否找到路径，若找到，则根据 节点中的 parent 反向构建出路径

参考：
[参考了代码](https://blog.csdn.net/zgwangbo/article/details/52078338)
[思路清晰，但没有代码](https://blog.csdn.net/hitwhylz/article/details/23089415)


## com.zzs.path包

因为旅行家问题是经过所有的目标点，而我要考虑的是经过指定的目标点，该包下用于 计算指定目标点的 旅行家问题。

通过一个小的demo来进行测试，一次测试通过
（但是这次测试，其中的路径都是采用AStar算出来的，还需要测试一下直接相邻的点）
经过简单的测试，直接相邻的点也可以使用，最终可以计算出路径和距离

整体思路 “旅行家问题动态规划 + AStar最短路径” 。

存在问题
为了防止重复进行AStar算法的计算，我使用了 <startId/endId, route> 进行了缓存，
路径方面，我将其存储到 int[][] prev 中，对于直接相邻的点还好，直接存放其前驱节点，
但是对于计算得到的 route，因为它是一个list，所以我将其存放到一个 map<key, route> 中，将 key 存放到 prev数组 中，为了方便区分，key我取负值。
无论是计算、从缓存中获取的，我都会保存到 map 中，并将对应的 key 放到 prev 中，但是 value 会重复，导致map的size很大。
总之就是，如果我得到的route（计算、缓存）已经存在于map中的value部分，我直接使用相应的key，而不是在添加一个新的key并映射到这个value。
但是我如何在map中快速定位 value 呢？？？
1、建立一个反向的map
2、将 value 对应中的某个特殊唯一字段 作为 key（我选择）
选择 方法2 后，我需要对缓存逻辑进行修改，因为我的缓存考虑<startId/endId, Route>，如果要找endId/startId，我选择读取前者的路径并翻转，这样在原有逻辑下没有问题，
但是现在增加了一个id，翻转后的Route是没有静态id的。


## 考虑更多因素

还需要考虑：电梯/楼梯，道路的类型（斜坡...）等

1、点的种类：
房间
电梯
楼梯

2、边的种类：
斜坡
小台阶

3、选择哪个电梯上下楼？
有一个电梯：采用变种2（但是一栋楼中，只有一个电梯的概率较低）
有多个电梯：
    1）采用变种1，根据停在的最后一个目标点的问题，选择近的电梯。
    2）采用变种2，将电梯点作为经过所有目标点后需要到达的指定点。问题是选择哪个电梯呢？每一个都算一次？如何考虑其他楼层的目标点分布？
    变种1、2计算的路径会存在差异，因为 变种2 相对 变种1 选择了结束的指定点，影响了路径的选择。

就目前我的能力来说，是做不到一个完美的解，但是可以尽可能趋近于完美
个人觉得采用变种2比变种1要好一点，因为加入了更多的影响因素，如果使用变种2，核心就是如何在 多个待定点中 选定 指定点

通常情况下，我从某一层的 `起点（房间、电梯）` 出发，经过当前层的所有 `目标点` ，
同时因为还有另一层的目标点需要经过，所以在经过当前层的所有目标点后，考虑并选定一个 `结束点（电梯）`
当前层的 `结束点` 会对应到 另一层的 `起点` 

选择关联两个楼层的电梯是关键。

我想了一个不成熟的方法
对于当前楼层，将每个可能的电梯作为 `结束点`，即利用变种2，每个都计算一次，得到各个 `电梯结束点` 的路径和距离
对于另一层，同样将每个可能的电梯作为 `起点`，在利用变种1，每个都计算一次，得到各个 `电梯起点` 进行分配的路径和距离
将 某个电梯 关联的路径的距离和 作为判断的依据。
计算量较大，进行了4次计算。（不过仅仅是 旅行家问题，因为AStar计算后都会进行缓存）

回去和别人讨论一下

4、目前使用的是G(V,E)，使用邻接矩阵表示图，可能会有两个房间对应一个点的问题。

图的表示：
邻接矩阵
邻接表

## 旅行家问题的变种

1、不回到起点，即经过所有目标点，直接结束就好了。

在dp数组中，将第一列的含义为：行对应的地点 到 起点 的距离。
若将值设置为0，即 行对应的地点 到 起点 的距离为零。

2、不回到起点，回到指定点，即经过所有目标点，需要前往指定点。

同理，对应dp数组 第一例的值修改为：行对应的地点 到 指定点 的距离值。

小结：
原旅行家问题、变种1、变种2都已解决。


## 多人任务规划
有一个任务，如配送，可以有多个人来完成这个任务，怎样根据不同的策略来进行任务的划分。


## 高德开放平台

[高德开放平台|高德地图API](https://lbs.amap.com/)

## 如何进行展示

毫无疑问，图形化是最基本的，3D更是很好，但是目前来说，还不是很清楚采用什么技术才完成展示。