带有墙壁(障碍物)的 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)
计算中。
希望这对您有所帮助。