同一路线上的不同路径重叠

Question

我在 A 和 B 之间有一段旅程，结束它的路径不同。路径由起始公里和最终公里定义：

path 0 -> (0, 10)
path 1 -> (10, 25)
path 2 -> (10, 15)
path 3 -> (15, 20)
path 4 -> (20, 30)
path 5 -> (25, 35)
path 6 -> (30, 35)
path 7 -> (35, 40)
path 8 -> (40, 50)

如您所见，有些路径是重叠的。事实上，我们可以得到重叠路径的列表：

path 0 -> NONE
path 1 -> 2,3,4
path 2 -> 1
path 3 -> 1
path 4 -> 1,5
path 5 -> 4,6
path 6 -> 5
path 7 -> NONE
path 8 -> NONE

我想得到的是所有可能的路线，路线中没有重叠的路径，但应该只走一条。有没有算法可以解决这个问题？我尝试用递归或像堆栈这样的辅助数据结构来实现，但我发现很难获得包含最终可能路径的列表，我也试图反转问题并尝试获得丢弃路径的列表，这是：

route 0-2-3-4-6-7-8 -> [1,5] discarded
route 0-2-3-5-7-8 -> [1,4,6] discarded
route 0-1-6-7-8 -> [2,3,4,5] discarded
route 0-1-5-7-8 -> [2,3,4,6] discarded

Answer 1

是的。这是一个简单的图形问题。与其将它们视为重叠路径，不如意识到里程碑是不相交的节点。例如，如果您处于里程碑 20，那么您唯一可以向前迈进的是 30——与其他细分市场的重叠根本无关紧要。如果您将它们视为通往编号城市的航线，或许效果会更好。

您可以查阅各种图遍历算法来选择算法。这个很简单：你只有一个决定点，在里程碑 10。一旦你做出这个选择，剩下的路线就确定了。

你能从那里拿走吗？

Answer 2

终于拿到验证码了！（可能可以改进）：

from copy import deepcopy

discarded_overlapped = []
def overlap(overlapped,discarded):
    if all(x is None for x in overlapped):
        discarded.sort()
        if discarded not in discarded_overlapped:
            discarded_overlapped.append(discarded)
        return
    for i in range(len(overlapped)):
        if not overlapped[i] == None:
            overlapped_copy = deepcopy(overlapped)
            discarded_copy = deepcopy(discarded)
            for j in overlapped[i]:
                if j not in discarded:
                    discarded_copy.append(j)
                    overlapped_copy[j] = None
            overlapped_copy[i] = None
            overlap(overlapped_copy,discarded_copy)


Data = [None,[2,3,4],[1],[1],[1,5],[4,6],[5],None,None]
overlap(Data,[])
print(discarded_overlapped)
# [[2, 3, 4, 6], [2, 3, 4, 5], [1, 5], [1, 4, 6]]

同一路线上的不同路径重叠

Different paths on the same route with overlapping

algorithm

recursion

data-structures

routing

overlap