1

我正在做一个项目，其目标是找到一种成本更低的方式将 X 蚂蚁从 A 点发送到 B 点，但每次只有一只蚂蚁可以站在“中间平台”上——不要不知道用英语怎么说——除了 A 点和 B 点。

我已经研究过 A* 或 Dijkstra 等算法，但它们只关注从 A 点到 B 点的最短路径，在某些情况下，这不是最好的，因为你宁愿走 2 条更长的路径并一次发送更多的蚂蚁。

这就是我需要你的地方。你们知道这样的算法吗？

希望我的问题很清楚，并期待答案。谢谢。

编辑：这是 A* 不起作用的示例：

-L-M-N-O-P-S-T-U-V-W-X-Y-Z--|    Going from one letter
|                  |        |    to another costs 1 turn
H-----I-----J------K        |
|                  |        |
START--A-B-C-D-E-F-G-------END

如果我有 17 只蚂蚁，最好的选择是一次向方向发送 2 只蚂蚁：

  • START-HIJKWXYZ-END
  • 开始-ABCDEFG-结束

而不是所有在 START-HIJKG-END 中，因为 A* 建议作为最佳选择。

4

2 回答 2

0

您可以使用 A* 来解决您的问题您只需要动态调整地图以考虑蚂蚁的位置

于 2013-04-03T13:35:27.930 回答
0

你可以使用floodfill。Floodfill 所做的是它跟踪每条可能的路径并确定最佳解决方案，但您可以定义“最佳”。例如，您可以创建一个通过递归跟踪时间的总时间变量。你可以做一个递归方法，只在到达B时返回时间变量，然后选择最短的值。

于 2016-10-23T19:56:08.047 回答