生成受 pickup/delivery 约束的路由的算法
Algorithm to generate routes subject to pickup/delivery
假设我们有 3 个人想从点 p1 到 d1,p2 到 d2,p3 到 d3。
我想列出这些人可能进行的所有行程,使得每个点 p1...p3, d1...d3 都在行程中,并且满足取件交付约束:即相应号码的交付 (d) 必须在同一号码的取货之后到达。例如,p1d1 是可以接受的,但 d1p1 不是。
我能够为 2 个人生成可能的行程,因为只有 6 个人。但是对于更多的人,它会变得很麻烦。有没有算法可以生成这样的行程?
实践中的语言是 python,所以如果有任何可用的库或一些类似的库将会有所帮助!
这是由边 (p1, d1), (p2, d2), (p3, d3)... 定义的有向图上的拓扑排序问题,您希望在其中收集所有可能的拓扑排序。
itertools 可能有一些巧妙的用途,但这是一个基本的递归实现:
def iterpaths(paths):
def recur():
if not paths:
yield []
return
for i in range(len(paths)):
val = paths[i].pop()
if not paths[i]:
paths.pop(i)
for result in recur():
yield result + [val]
paths.insert(i, [val])
else:
for result in recur():
yield result + [val]
paths[i].append(val)
yield from recur()
A 运行 3 对:
for path in iterpaths([[1,2],[3,4],[5,6]]):
print(path)