这是我在学校收到的作业之一。任何形式的建议将不胜感激。
我有一张街道 map ，其中每个十字路口都用坐标 = 整数元组 (x, y) 表示。两个坐标之间的长度等于它们之间的曼哈顿距离。我是出租车司机，我有每个顾客的坐标和他们想去的坐标、起始坐标和车里可以容纳的最大顾客数量。我需要找到最短路径将所有客户送至目的地。客户只能在最终目的地下车。 结果是顾客的顺序，出租车员必须在其中挑选/放下他们。
我当前的解决方案使用递归来查找所有路径，比较它们的长度并返回最短的路径。问题是，它太慢了。它需要在一秒钟内完成。
感谢您的帮助!
编辑1: 函数:taxi = 当前出租车坐标，starti = 所有客户的接载坐标(starti[0] = 客户 1 的接载坐标)，cilji = 所有客户的最终目的地(cilji[0] = 客户 1 的下车坐标)，left = 剩余开车前往目的地的客户数量，index = just为了得出最终结果，n = 出租车内的最大顾客数量，atm = 当时车内的顾客数量
public static int abs(int n) {
if (n < 0) {
return -n;
}
return n;
}
public static int razdalja(int[] a, int[] b) {
return abs(a[0] - b[0]) + abs(a[1] - b[1]);
}
public static int[] fun(int[] taxi, int[][] starti, int[][] cilji, int left, int m, int index, int n, int atm) {
int[] temp1;
int[] temp2;
int[] tab = new int[m*2+1];
int[] min = new int[m*2+1];
min[m*2] = Integer.MAX_VALUE;
if (left == 0) {
return tab;
}
for (int i = 0; i < m; i++) {
if (starti[i] != null && atm < n) {
temp1 = starti[i];
starti[i] = null;
tab = fun(temp1, starti, cilji, left, m, index+1, n, atm+1);
tab[index] = i+1;
tab[m*2] += razdalja(taxi, temp1);
starti[i] = temp1;
if (tab[m*2] < min[m*2]) {
min = tab;
}
}
else if (cilji[i] != null && starti[i] == null) {
temp2 = cilji[i];
cilji[i] = null;
tab = fun(temp2, starti, cilji, left-1, m, index+1, n, atm-1);
tab[index] = i+1;
tab[m*2] += razdalja(taxi, temp2);
cilji[i] = temp2;
if (tab[m*2] < min[m*2]) {
min = tab;
}
}
}
return min;
}
输入示例
6 //max customers in car
148,128 //taxi starting coordinates
7 //number of customers
1,45,199,178,69 //first customer startX,startY,endX,endY
2,54,87,26,83 //and so on...
3,197,147,135,93
4,12,49,61,66
5,91,8,55,73
6,88,42,15,9
7,184,144,31,34
上面输入的正确输出(我的函数返回这些数字的表+表中的最后一个数字是路径的长度)
7,3,1,2,6,5,6,7,4,2,5,4,3,1
this means:
pick (customer) 7 (184,144)
pick 3 (197,147)
pick 1 ...
pick 2
pick 6
pick 5
drop 6
drop 7
pick 4
drop 2
drop 5
drop 4
drop 3
drop 1
编辑2: 更重要的是，我注意到一些我可能可以改进的地方，但我不确定如何改进。函数中的 for 循环总是迭代所有 i 值，即使在很多情况下它什么也不做，直到达到足够高的“i”，因为 starti[i] 和 cilji[i] 对于大多数情况都等于 null一旦我们的递归足够深入，就会得到 i 值。对于每个已交付的客户，都有一个不执行任何操作的迭代。
这就是两个客户的树的样子: /image/P3irL.png 圈出的坐标是出租车载客的地方(我忘了圈出一个，很明显)。
input:
2
5,5
2
1,3,7,5,7
2,9,2,9,7
output:
1,1,2,2
最佳答案
我制定了一个基于动态编程的解决方案，对于最难的测试用例，它的运行时间约为 0.17 秒:https://ideone.com/lKUql9
INF = 100000000000
pickup = {}
dest = {}
trace = {}
dp = {}
def calc(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def solve(curPos, completed, ongoing):
if len(completed) == N and len(ongoing) == 0:
return 0
curState = (curPos, frozenset(completed), frozenset(ongoing))
if curState in dp.keys():
return dp[curState]
minVal = INF
for i in pickup.keys():
if i in completed: continue
newOngoing = ongoing.copy()
newCompleted = completed.copy()
if i in ongoing:
newOngoing.remove(i)
newCompleted.add(i)
val = calc(curPos, dest[i]) + solve(dest[i], newCompleted, newOngoing)
if val < minVal:
minVal = val
trace[curState] = \
("drop " + str(i), (dest[i], newCompleted, newOngoing))
elif len(ongoing) < maxCustomers:
newOngoing.add(i)
val = calc(curPos, pickup[i]) + solve(pickup[i], newCompleted, newOngoing)
if val < minVal:
minVal = val
trace[curState] = \
("pickup " + str(i), (pickup[i], newCompleted, newOngoing))
dp[curState] = minVal
return minVal
def path(state):
stateVar = (state[0], frozenset(state[1]), frozenset(state[2]))
if stateVar not in trace.keys():
return
print (trace[stateVar][0])
if trace[stateVar][1] != None:
return path(trace[stateVar][1])
maxCustomers = int(input())
rstr = input().split(",")
start = (int(rstr[0]), int(rstr[1]))
N = int(input())
for i in range(N):
line = input().split(",")
pickup[int(line[0])] = (int(line[1]), int(line[2]))
dest[int(line[0])] = (int(line[3]), int(line[4]))
print("Total distance travelled: ", solve(start, set(), set()))
path((start, set(), set()))
代码在很多方面都是不言而喻的，但如果有不清楚的地方，我愿意更详细地解释。
编辑:
我们将当前状态定义为我们所在的当前坐标(curPos)、我们已经完成(完成)的行程集和仍在进行中的行程集，即我们有客户在车里(正在进行)- 这两组中的任何行程尚未开始。我使用 frozenset() 因为 python 字典不允许使用 set() 作为字典哈希键的一部分(即 Map、dp 和 trace 在我们的例子中)，因此普通的 set() 必须转换为不可变的集合，即 frozenset()
存在多个重叠的子问题，这是我们使用 dp 的主要原因。只要 dp.keys() 中存在 curState，您就可以添加 print ("Dp Hit: ", curState)，就像我所做的那样:https://ideone.com/mKFsVH (由于输出行太多而产生运行时错误)。正如您所看到的，记忆化处理了大量我们不需要重新探索的情况。为了更好地理解，请考虑阅读有关使用动态规划来解决旅行推销员问题的内容:https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/
if i incomplete 是 ~ O(log(n)) 查找，因为 set 内部被实现为自平衡二叉树，是的，仅仅是条件 if len(completed) == N 应该足够了。刚刚添加了另一半作为健全性检查。
关于java - 使用曼哈顿距离计算多点之间的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53160009/