3

我需要从一些不寻常的数据中确定父/子关系。

航班号是营销创意，它们很奇怪。航空公司 X 的 22 号航班可能指的是 X 和 Y 之间的一次旅行。来自同一家航空公司的 44 号航班实际上可能指的是城市对之间的多个航班。例子：

Flight 44:  Dallas - Paris
Flight 44:  Dallas - Chicago
Flight 44:  Chicago - New York
Flight 44:  New York - Paris
Flight 44:  Chicago - Paris
Flight 44:  Dallas - New York

现实——这就是他们的工作方式。当我从“航班号和城市对大列表”中提取数据时，我得到了 44 航班的这 6 个组合。我有每个航班的乘客人数，所以如果有 10 人乘坐达拉斯 - 巴黎，我需要选择这 10乘客并将他们添加到 DAL - CHI、CHI - NY 和 NY - PAR 航段。

从所有航段的列表中，我需要弄清楚“啊，这是从达拉斯飞往巴黎的航班”——然后当我看到乘客负载时，我可以相应地增加城市到城市的实际负载，如下所示：

- Value associated with AD -- > increment segments AB, BC, CD
- value associated with AC -->  increment only segments AB, BC
- value associated with AB --> increment only segment AB
etc.

假设我得到一个无顺序的 44 航班的值列表，如下所示：（DAL-CHI、CHI-NYC、NYC-PAR、DAL-NYC、DAL-PAR、CHI-PAR）。我如何找出比较这 6 个组合中的这 4 个值的父子结构？

4

5 回答 5

4

公式

让a_i -> b_i成为i44 航班配对列表中的第 th 个条目，i = 1..M。

让V成为所有唯一值a_i和b_i值的集合：

V = {a_i | i = 1..M} U {b_i | i = 1..M}

让我们E成为所有对的集合(a_i, b_i)：

E = {(a_i, b_i) | i = 1..M}

然后G = (V, E)是一个有向无环图，其中顶点V是城市，有向边E对应a_i -> b_i于列表中的条目。

算法

您正在寻找的是图形的拓扑排序G。链接的 Wikipedia 页面包含此算法的伪代码。

这将为您提供城市的线性排序（在您的示例[Dallas, Chicago, New York, Paris]中：），这与初始列表中存在的所有排序约束一致。如果您的初始列表包含少于|V| choose 2对（意味着没有完整的约束集），那么您的 set 中的城市可能会有多个一致的拓扑排序V。

于 2013-07-11T18:26:12.107 回答
1

从您的航班列表中构建一个出发地或目的地的所有城市的列表。这给出了四个城市：

Dallas
Paris
Chicago
New York

再次遍历航班列表并计算每个目的地城市的出现次数：

0 Dallas
3 Paris
1 Chicago
2 New York

按目的地计数对列表进行排序，您就有了路线：

Dallas -> Chicago -> New York -> Paris

注意：如果目的地计数从零开始不连续（例如 0、1、2、3...），则表明该航班的出发/目的地列表不一致或不完整。

于 2013-07-11T18:36:26.053 回答
1

注意：这是一个常识性分析，但请参阅 Timothy Shields 解决方案，他将问题确定为拓扑排序问题，因此具有已知的计算复杂性和已知的唯一性条件。

我将尝试从您的答案中提取问题的核心，以便正式描述它。

在上面的示例中，您实际上有四个节点（城市），为简洁起见，分别表示为 D、P、C 和 NY。您有一组有序对 (x, y)，它们被解释为“在该航班上，节点 x 在节点 y 之前”。将其写为x<y，我们实际上有以下内容：

（对于 044 航班）：

D < P
D < C
C < NY
NY < P
C < P
D < NY

从这些约束中，我们希望找到一个有序元组(x, y, z, w)，使得x < y < z < w上述约束成立。我们知道解决方案是(x=D, y=C, z=NY, w=P)。

注意：可能在您的数据库中，您的集合中的第一个元素始终是“起点-终点对”（在我们的例子中，是D<P）。但在后面的分析中变化不大。

如何以编程方式找到这个有序元组？我对算法有相对公平的了解，但不知道解决这个问题的标准方法（其他用户可能会在这里提供帮助）。我担心结果的独特性。您应该要求该有序元组的解决方案是唯一的，这可能是对数据完整性的良好单元测试，否则您可能随后会增加错误的段。

当我们处理唯一性问题时，我建议生成节点的所有排列，并显示所有在给定约束条件下可行的解决方案。

一个简单的实现可能如下所示：

import itertools 

nodes = ['D', 'P', 'NY', 'C']

result = [ot
          for ot in itertools.permutations(nodes) # ot = ordered tuple
          if ot.index('D') < ot.index('P')
          if ot.index('D') < ot.index('C')
          if ot.index('C') < ot.index('NY')
          if ot.index('NY') < ot.index('P')
          if ot.index('C') < ot.index('P')
          if ot.index('D') < ot.index('NY')
          ] 

print result

# displays: [('D', 'C', 'NY', 'P')]

如果节点数量很少，这种类型的“幼稚”实现可能就足够了。如果数字更高，我建议以有效使用约束来修剪解决方案空间的方式实现它（询问我是否需要提示）。

于 2013-07-11T18:11:45.900 回答
0

您是否考虑过使用带有列表存储的字典。

字典基本上是一个哈希表，您可以存储一个键（乞求和终点 ex，AD）和一个值（它需要通过 [AB，BC，CD] 的段）

于 2013-07-11T16:03:14.653 回答
0

好的，拿两个：这是一个函数，它将接受一个字符串，例如您提供的字符串，并根据该维基百科文章对其进行拓扑排序。

import re
import itertools

def create_nodes(segments):
    remaining_segments = re.findall(r'(\w*?)-(\w*?)[,)]', segments)
    nodes = []
    while len(remaining_segments) > 1:
        outgoing, incoming = zip(*remaining_segments)
        point = next(node for node in outgoing if node not in incoming)
        nodes.append(point)
        remaining_segments = [segment for segment in remaining_segments if segment[0] != point]
    last_segment = remaining_segments.pop()
    nodes.extend(last_segment)
    return nodes

测试：

>>> foo = '(DAL-CHI, CHI-NYC, NYC-PAR, DAL-NYC, DAL-PAR, CHI-PAR)'
>>> scratch.create_nodes(foo)
['DAL', 'CHI', 'NYC', 'PAR']

请注意，这不是一个完美的拓扑排序函数。但是，对于您的多站单程旅行的特定用例，它应该是有效的。

于 2013-07-11T16:05:38.540 回答