-1

我必须编写一个程序来计算完成所有交付的最短路径。地图表示为 x，y 坐标，路径是使用曼哈顿距离计算的（所以沿着 x 走，然后沿着 y 走）。起点始终是 (0, 0)，快递员可以在任何点结束。快递员在任何给定时间只能携带 1 个包裹。

这可以使用 A* 搜索算法来实现，我的问题是由于 A* 算法是一个 I 形成的搜索，它需要知道其 statusNode 的启发式值。对于这个问题，什么是好的启发式实现？甚至是启发式价值的想法？

我有一个示例输入：

Job 3 3 to 5 3        # there is a job from (3,3) to (5,3)
Job 1 1 to 9 2        # there is a job from (1,1) to (9,2)
Job 3 5 to 2 7        # there is a job from (3,5) to (2,7)
Job 5 5 to 5 7        # there is a job from (5,5) to (5,7)

和输出：

Cost = 31
Move from 0 0 to 1 1
Carry from 1 1 to 9 2
Move from 9 2 to 3 3
Carry from 3 3 to 5 3
Move from 5 3 to 5 5
Carry from 5 5 to 5 7
Move from 5 7 to 3 5
Carry from 3 5 to 2 7

我目前的搜索方法是：

我有 jobToBeDone 和 jobDone 的列表

  1. Initialise 当前位置的初始值为 0, 0

  2. 检查是否所有作业都已完成

  3. 如果不是，对于所有剩余的工作，计算总成本=到达那里的路径 + 工作的一些启发式价值。

  4. 将它们放在jobsToBeDone 中并以最短路径排序具有较低的索引（如java 中的priorityQueue）。

  5. 通过将当前位置更新到第一个索引中的作业来重复第 2 条指令。

4

1 回答 1

0

有两个问题。最短路径和旅行推销员。

您需要计算点之间的所有路径，然后对点进行排序以获得最终的最短路径。对于最后一部分，您需要少量点的启发式或蛮力。

而不是 A* 使用 Dijkstra 和 dijkstra 您可以轻松地一次计算多条路径（因为它是一对多的）

于 2013-05-08T10:11:25.353 回答