algorithm - 在路线规划中应用A*算法？

Question

我正在做一项需要使用 A* 算法的作业，但我不知道如何做。

作业是，想象一个 postman 在从 (0,0) 到无穷大的网格 map 上发送包裹。他在一天开始时列出了一个任务列表，每个任务都分配了一个起点 (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

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

所以问题是，因为 A* 算法。是为寻路而设计的，我们如何应用它或它的变体来解决这个寻找正确方法的问题？

Answer 1

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

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

转换后，你的问题变成了“用A*解决旅行商问题”，这就是绝配:How can the A* algorithm be applied to the traveling salesman problem?