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

1

フライト リストの出発地または目的地であるすべての都市のリストを作成します。これにより、次の 4 つの都市が得られます。

Dallas
Paris
Chicago
New York

フライト リストをもう一度繰り返し、各目的地都市の出現回数を数えます。

0 Dallas
3 Paris
1 Chicago
2 New York

リストを目的地の数で並べ替えると、ルートが得られます。

Dallas -> Chicago -> New York -> Paris

注: 目的地の数が 0 から始まる連続していない場合 (例: 0、1、2、3...)、そのフライトの出発地/目的地リストが矛盾しているか不完全であることを示しています。

于 2013-07-11T18:36:26.053 に答える
1

注: これは常識的な分析ですが、Timothy Shields のソリューションを参照してください。Timothy Shields のソリューションでは、問題がトポロジカル ソートの問題であると特定されており、既知の計算の複雑さと一意性の既知の条件があります。

正式に説明するために、あなたの回答から問題の核心を抽出しようとします。

上記の例では、実際には 4 つのノード (都市) があり、簡潔にするために 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

わかりました、2 つ取ります: これは、提供されたような文字列を取り、そのウィキペディアの記事に従ってトポロジ的に並べ替える関数です。

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 に答える