-1

元组列表是有能力的车辆路线优化的输出，表示从一个站点到另一个站点的弧线，其中0表示车辆的站点（车辆的起点和终点）。由于车辆必须行驶几圈，它可能会在所有停车前返回站点。求解器将始终首先返回起始弧，在下面的示例中，这意味着第一个以 开头的连续元组0，(0, 3), (0, 7), (0, 8)即将确定有多少圈（= 3）。

如何按连续顺序对弧进行排序，以便一辆车可以一个接一个地驱动弧？

输入：

li = [(0, 3), (0, 7), (0, 8), (3, 0), (4, 0), (7, 3), (8, 4), (3, 0)]

输出：

[(0, 3), (3, 0), (0, 7), (7, 3), (3, 0), (0, 8), (8, 4), (4, 0)]

到目前为止我尝试了什么：

    laps = 0
    for arc in li:
        if arc[0] == 0:
            laps = laps + 1
    new_list = []
    for i in range(laps):
        value = li.pop(0)
        new_list.append([value])
    for i in range(laps):
        while new_list[i][-1][1] != 0:
            arc_end = new_list[i][-1][1]
            for j in range(len(li)):
                if li[j][0] == arc_end:
                    value = li.pop(j)
                    new_list[i].append(value)
                    break
    flat_list = [item for sublist in new_list for item in sublist]
    return flat_list
4

1 回答 1

0

您正在尝试解决在有向图中查找循环的问题。这个问题本身并不难解决，Python 有一个非常好的包来解决这类问题——networkx。学习一些基本的图算法是个好主意。还有另一个关于此算法的堆栈溢出问题，您可以在Find all Cycles in adirected graph 中查阅。

于 2020-05-05T10:41:35.993 回答