algorithm - 从成对数据中确定 parent 、子女

Question

我需要根据一些异常数据确定父/子关系。

航类号是营销创意，而且很奇怪。航空公司 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 个值的父子结构？

Answer 1

配方

设 a_i -> b_i 是航类 44 的配对列表中的第 i 个条目，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) 是一个 directed acyclic graph其中顶点 V 是城市，有向边 E 对应于列表中的条目 a_i -> b_i。

算法

您正在寻找的是 topological sort图G。链接的维基百科页面包含此算法的伪代码。

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