c - 具有顶点的 TSP 可能会被多次访问

Question

在一个研究项目中，我的项目组正在研究一种驾驶 5x5 并带有地雷的机器人。我们不知道地雷的位置，也无法开车越过地雷(只允许传感器感知)。

我们的目标是(尽可能快地)扫描该矩阵以查找起点位于矩阵点 (1,5) 下方的地雷。我们决定该矩阵的边和起点将是 TSP 问题的顶点，但我们一直在寻找一种好的算法，如果速度更快，该算法可以(如果需要)多次穿过边。

目前我们唯一拥有的是一个 41x41 矩阵，其中包含从一个边缘到另一个边缘的所有可能方法(如果检测到地雷，可以将其更改为无限)以及一个用于预定义路线的备份计划，如果检测到地雷，将其发送到下一个点。

可以解决我们的问题的最快算法是什么？您能否提供示例 C 代码或如何创建它的想法？

Answer 1

要回答一般问题(如何求解具有可以多次访问的顶点的 TSP):只需在运行标准 TSP 求解器之前运行 Floyd-Warshall 算法即可。

回答你的具体问题:由于你在游戏开始时不知道地雷在哪里，因此每次发现你的路线被封锁时，你都必须重新计算你的路线。