algorithm - 使用图形来翻译不同的表示

Question

我遇到了数据转换问题，希望获得有关如何破解它的指导:

我有一个入站项目列表，这些项目代表沿途分配给各个路段的火车车厢。每个项目都有一个索引、一个汽车引用、一个起点和一个终点。例如

Index Car Origin Destination
1     C1  L1     L2
2     C2  L1     L2
3     C3  L1     L2
4     C1  L2     L3
5     C2  L2     L3
6     C4  L2     L3

上面的示例显示了四辆汽车(C1、C2、C3、C4)。汽车 C1-C2 从 L1 行驶到 L3。 C3 从 L1 到 L2。 C4 从 L2 行进到 L3。该索引维护了每个“腿”内汽车的顺序，但它是相对的:对于第二个腿 (L2-L3)，使用的第一个索引是 4。

我需要将其转换为提供不同车厢列表的不同模型，同时保持车厢内车厢的顺序。例如

Index Car Origin Destination
1     C1  L1     L3
2     C2  L1     L3
3     C3  L1     L2
4     C4  L2     L3

第二个模型不允许在旅途中对火车车厢进行完全重新排序。 IE。我不能让汽车 A、B、C、D 将顺序更改为 A、C、B、D。我必须应用一些启发式方法来获得最终的汽车顺序，这不会反射(reflect)现实。我很乐意接受这个缺点。

此外，虽然目标模型索引指定了列车内的车厢顺序，但无论我是从列车的前部还是后部进行索引都无关紧要。在旅程的早期使用较低的索引进行汽车分配会很好。

因此，对于解决方案:我想我需要使用图表来进行翻译，但我不确定从哪里开始。我想我应该将汽车建模为顶点，将同一条腿上的两辆汽车的耦合作为边。但我不确定我从那里去哪里。

如果能提供有关如何解决该问题的任何指示，我将不胜感激:建模技巧、合并算法...

编辑更复杂的是:在某些线路上，火车中车厢的顺序可能会完全颠倒。这用于指示火车改变方向。我不需要捕获这种反转，但我确实需要保留汽车的互连顺序。

Answer 1

本质上，撇开反向段的问题不谈，这个问题简化为 topological sort为此存在许多简单有效的算法(有关示例，请参见维基百科链接)。为了构建图形，我们使用汽车作为顶点并插入一条来自 C<sub>i</sub> 的边。至 C<sub>j</sub>如果C<sub>i</sub>紧接在 C<sub>j</sub> 之前在某条腿上。 (这最大限度地减少了边的数量，从而降低了 O(V+E) 拓扑排序的成本。)

但这不适用于“反向”腿；这些将导致拓扑排序失败。所以问题的另一部分是检测反向腿。在这里，我假设没有明确的反转边列表；如果有，解决方案将是显而易见的。

我认为以下内容会相当有效地工作，但它可能不是最佳的。

假设两条腿前向兼容如果它们共享至少两辆车并且共享汽车的顺序在两条腿中是相同的。类似地，如果两条腿共享至少两辆车，并且一条中共享汽车的顺序与另一条中共享汽车的顺序完全相反，则两条腿反向兼容。最后，如果两条腿最多共享一辆车，则它们双向兼容。 (有可能两条腿不属于这三个类别中的任何一个，在这种情况下它们不兼容并且问题无解。)

两条腿之间的关系很容易归类。使用正确的数据结构(例如哈希表)找到两条腿之间的共享汽车列表是 O(min(m,n))其中 m 和 n 是腿的大小(汽车数量)，检查共享汽车是否以相同或相反的顺序出现在两个列表中。因此，构建所有可能的腿对之间的整个关系数组应该是 O(L·N)其中 L是腿的数量，N汽车的数量。 (我没有这个断言的证据，所以它可能是错误的。但它似乎是合理的。)

有了兼容性图，我们需要为每条腿指定一个方向。我们使用图的遍历来执行此操作，使用以下递归过程:

# Direction is either Forward or Reverse. We assume a function reverse(D) which
# returns Reverse if D is Forward, and Forward if D is Reverse
setDirection(Leg, Direction):
  + If the Direction of Leg is Direction, return.
  + If the Direction of Leg is set and not the same as Direction, fail.
  + Otherwise:
    + Set the Direction of Leg to Direction.
    + For each L such that Leg is forward compatible with L:
        + Call SetDirection(L, Direction)
    + For each L such that Leg is reverse compatible with L:
        + Call SetDirection(L, reverse(Direction))

setAllDirections():
  + while some Leg L does not have its direction set:
    + SetDirection(L, Forward)

现在，我们可以将标记为颠倒的腿中的汽车顺序颠倒，并应用拓扑排序。

请注意，上述过程可能会产生一组与“现实”不符的一致腿方向，因为在最后一行中设置新腿的初始方向的决定完全是任意的。但我认为这是我们能做的最好的。