1

我正在做一个需要使用 A* 算法的作业，但我不知道怎么做。

(0,0)任务是，想象一个邮递员在一张网格地图上从无穷远处发送包裹。他在一天开始时列出一份任务，每个任务都分配了一个起点(x1,y1)和一个终点(x2,y2)。由于他不能同时处理两个任务，所以他必须将这些任务安排好，这样当他完成一个任务并从终点移动到下一个起点时，他可以拥有全天的最小移动距离. 距离计算为曼哈顿距离，即d(x1,y1,x2,y2) = abs(x2 - x1) + abs(y2 - y1)。

样本输入：

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)

样本输出：

n nodes explored
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

在我看来，虽然这里提到了图表（或地图），但它不是必需的，因为唯一重要的部分是将这些任务排序为最小，而距离可以很容易地计算出来。一些愚蠢的事情会是排列并选择成本最低的一个，但永远不要采用它。我也尝试过 Greedy，但它可能无法获得全球最佳解决方案。

所以问题是，因为 A* 算法。是为寻路而设计的，我们如何将它或它的变体应用到寻找正确路径的问题上？

4

2 回答 2

0

获取所有这些点并将其输入到 kd-tree 中。您可以使用 kd-tree 找到任何点的最近邻居。

在运行 A* 算法时，使用最近的邻居展开下一个节点。转到最近邻居表示的路径的尽头，然后再次展开。删除操作平均需要 O( log n ) 时间，我希望这适合您的实现。

例如：

探索了 n 个节点

成本 = 31

找到 (0,0) => (1,1) 的最近邻

从 0 0 移动到 1 1

从 1 1 进位到 9 2

找到 (9,2) => (3,3) 的最近邻

从 9 2 移动到 3 3

携带从 3 3 到 5 3

找到 (5,3) => (5,5) 的最近邻

从 5 3 移动到 5 5

携带从 5 5 到 5 7

找到 (5,7) => (3,5) 的最近邻

从 5 7 移动到 3 5

从 3 5 进位到 2 7

+++++++++++++++++++++++++++++++++++++++++++++

检查 kd-tree 概述：http ://en.wikipedia.org/wiki/Travelling_salesman_problem

并查看此视频以了解基于数组的 kd-tree 实现：http ://www.youtube.com/watch?v=2SbVSxWGtpI

PS：- 仅将每条路径的第一个节点插入树中。还有一件事....蛮力会给你全局最优...但是会花费很多时间。

于 2013-05-02T05:12:42.250 回答
0

我认为您正在尝试解决旅行商问题 (TSP) http://en.wikipedia.org/wiki/Travelling_salesman_problem的变体

对于作业 A 和作业 B，可以计算作业 A 的终点与作业 B 的起点之间的曼哈顿距离，并将其视为从 A 到 B 的距离。此操作会将问题转化为 TSP。

转换后，你的问题变成了“使用A*解决旅行商问题”，这是一个完美的匹配：A*算法如何应用于旅行商问题？

于 2013-04-29T15:57:10.067 回答