生成受 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)