带有墙壁（障碍物）的 2d 地图上的旅行推销员概率，因此需要寻路
Traveling salesman prob on 2d map with walls (obstacles) so pathfinding needed
我需要在二维地图上的多个点之间找到最佳路径。
2d 地图是建筑物的，只会有你不能去的地方（穿过墙壁）和地图上的所有点。所以它不是真正的地图，而是你不能通过的线和要通过的点。
- 我有很多点，比如说在 20 到 500 之间
- 我从 select 开始，然后需要为最佳路径计算路线。
我很想知道在哪里寻找这个有障碍的旅行商问题的提示。或者更好的是，done library for doing it.
奖金
- 门之类的东西可以加重，因为它们来回穿过的乐趣不大。
- 可能 prioritizing/Weighting 能够在您开始的地方附近结束。
- 选择可以通过但令人讨厌的区域（权重降低）
- .Net/C# 我可以使用的代码，我想在 .NET MVC 项目和 Xamarin 移动项目上都使用它，所以 .net 代码会很棒（如果代码存在）
更新示例
在我这里的例子中，我们有一个办公室。现在我还没有考虑到每一个细节，所以这只是一个例子。
- 需要检查所有紫色点
- 黄色区域可能意味着难以通过但可行
- 红色可能表示未激活，但如果不存在其他选项则可以通过。
- 蓝色（墙壁）坚不可摧，无法通过。
- 绿色是门，可能会变重，因为关闭门很烦人（通常这可能是有道理的，因为房间里的点最容易一起检查。
- 用户会去一个点，检查它，然后软件应该告诉他下一步要做什么，直到他完成。
- 结束接近开始的地方可以获得奖励。因此，例如在这个例子中，如果红色区域是正常的并且包含点，那么很容易让它成为一个循环。 （所以用户回到他开始的地方）
- 最后我想区分户外区域也很聪明，因为你需要为户外穿好衣服，所以你只想出去一次。
- 如果他们打算一次检查多个楼层，那么能够优先在靠近楼梯间的点结束到下一层可能是明智的。
- 当然会有比这个例子更复杂更大的计划。
再次抱歉只是集思广益，但我从未做过这种工作，很高兴收到任何指示:-)
设N为要访问的节点集（紫色点）。对于 N 中的每个 i 和 j，令 c(i,j) 为从 i 到 j 的距离（或旅行时间）。这些可以根据实际距离加上墙壁、门、其他障碍物等预先计算。
现在，如果从 i 到 j 的路径穿过门、"annoying" 区域等，则可以对 c(i,j) 添加惩罚。但是更灵活的方式可能如下：
让 k = 1,...,K 成为各种类型的不良路线属性（门、烦人的区域等）。令 a_k(i,j) 为从 i 到 j 的路径上每个属性的数量。 （例如，假设k=1代表门，k=2代表黄色区域，k=3代表外面。那么从休息区的i到休息区的j浴室可能有 a_1(i,j) = 1，从 i 到 j 两个黄色区域都有 a_2(i,j) = 0.5 或 2.0 或者不管那个区域有多烦人，等等.)
然后，让 p_k 成为对每个单位不良属性的惩罚 k -- 如果你不介意穿过门太多，也许 p_1 = 0.1 但 p_2 = 3.0 如果你真的不喜欢黄色区域。
然后，让c'(i,j) = c(i,j) + sum{k=1,...,K} p_k * a_k(i,j)。换句话说，用距离加上对所有烦恼的惩罚来代替实际距离。用户可以在优化前设置 p_k 值，以表达其中的 his/her 偏好。最终的惩罚 p_k * a_k(i,j) 应该与用于 c(i,j) 的距离单位相称，但是——你不想要 100 米的距离，而是 1,000,000 的惩罚。
现在用 c'(i,j) 给定的距离求解 TSP。
TSP 要求您在同一节点开始和结束，因此偏好确实是一种约束。如果您要同时解决多个楼层的问题，那么楼梯时间将在 c(i,j) 内，因此无需明确鼓励在楼梯附近结束的路线——无论如何解决方案都会这样做，因为楼梯很慢。如果您要独立解决每个楼层，则只需将每个楼层的起始节点设置为等于楼梯即可。
我不会对红色（允许但未使用）区域做任何事情——它们已经被纳入 c(i,j) 计算中。
希望这对您有所帮助。
我需要在二维地图上的多个点之间找到最佳路径。 2d 地图是建筑物的，只会有你不能去的地方（穿过墙壁）和地图上的所有点。所以它不是真正的地图，而是你不能通过的线和要通过的点。
- 我有很多点，比如说在 20 到 500 之间
- 我从 select 开始，然后需要为最佳路径计算路线。
我很想知道在哪里寻找这个有障碍的旅行商问题的提示。或者更好的是，done library for doing it.
奖金
- 门之类的东西可以加重，因为它们来回穿过的乐趣不大。
- 可能 prioritizing/Weighting 能够在您开始的地方附近结束。
- 选择可以通过但令人讨厌的区域（权重降低）
- .Net/C# 我可以使用的代码，我想在 .NET MVC 项目和 Xamarin 移动项目上都使用它，所以 .net 代码会很棒（如果代码存在）
更新示例
- 需要检查所有紫色点
- 黄色区域可能意味着难以通过但可行
- 红色可能表示未激活，但如果不存在其他选项则可以通过。
- 蓝色（墙壁）坚不可摧，无法通过。
- 绿色是门，可能会变重，因为关闭门很烦人（通常这可能是有道理的，因为房间里的点最容易一起检查。
- 用户会去一个点，检查它，然后软件应该告诉他下一步要做什么，直到他完成。
- 结束接近开始的地方可以获得奖励。因此，例如在这个例子中，如果红色区域是正常的并且包含点，那么很容易让它成为一个循环。 （所以用户回到他开始的地方）
- 最后我想区分户外区域也很聪明，因为你需要为户外穿好衣服，所以你只想出去一次。
- 如果他们打算一次检查多个楼层，那么能够优先在靠近楼梯间的点结束到下一层可能是明智的。
- 当然会有比这个例子更复杂更大的计划。
再次抱歉只是集思广益，但我从未做过这种工作，很高兴收到任何指示:-)
设N为要访问的节点集（紫色点）。对于 N 中的每个 i 和 j，令 c(i,j) 为从 i 到 j 的距离（或旅行时间）。这些可以根据实际距离加上墙壁、门、其他障碍物等预先计算。
现在，如果从 i 到 j 的路径穿过门、"annoying" 区域等，则可以对 c(i,j) 添加惩罚。但是更灵活的方式可能如下：
让 k = 1,...,K 成为各种类型的不良路线属性（门、烦人的区域等）。令 a_k(i,j) 为从 i 到 j 的路径上每个属性的数量。 （例如，假设k=1代表门，k=2代表黄色区域，k=3代表外面。那么从休息区的i到休息区的j浴室可能有 a_1(i,j) = 1，从 i 到 j 两个黄色区域都有 a_2(i,j) = 0.5 或 2.0 或者不管那个区域有多烦人，等等.)
然后，让 p_k 成为对每个单位不良属性的惩罚 k -- 如果你不介意穿过门太多，也许 p_1 = 0.1 但 p_2 = 3.0 如果你真的不喜欢黄色区域。
然后，让c'(i,j) = c(i,j) + sum{k=1,...,K} p_k * a_k(i,j)。换句话说，用距离加上对所有烦恼的惩罚来代替实际距离。用户可以在优化前设置 p_k 值，以表达其中的 his/her 偏好。最终的惩罚 p_k * a_k(i,j) 应该与用于 c(i,j) 的距离单位相称，但是——你不想要 100 米的距离，而是 1,000,000 的惩罚。
现在用 c'(i,j) 给定的距离求解 TSP。
TSP 要求您在同一节点开始和结束，因此偏好确实是一种约束。如果您要同时解决多个楼层的问题，那么楼梯时间将在 c(i,j) 内，因此无需明确鼓励在楼梯附近结束的路线——无论如何解决方案都会这样做，因为楼梯很慢。如果您要独立解决每个楼层，则只需将每个楼层的起始节点设置为等于楼梯即可。
我不会对红色（允许但未使用）区域做任何事情——它们已经被纳入 c(i,j) 计算中。
希望这对您有所帮助。