python - Algorithm to generate routes subject to pickup/delivery

Question

Suppose we have 3 people wanting to go from point p1 to d1, p2 to d2, and p3 to d3.

I want to list all possible trips that these people could take, such that every point p1...p3, d1...d3 is on the trip, and that it satisfies pickup delivery constraint: that is, the delivery (d) for a respective number must come AFTER the pickup for that same number. For instance, p1d1 is acceptable, but d1p1 is not.

I was able to generate possible trips for 2 people, as there were only 6. But for higher numbers, it gets cumbersome. Is there an algorithm that can generate such trips?

The language in practice is python, so if there any available libraries or some such that would be helpful!

标签： pythonalgorithmtraveling-salesman

Answer 1

这是由边 (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()

运行 3 对：

for path in iterpaths([[1,2],[3,4],[5,6]]):
    print(path)