1

問題: 有向巡回グラフのエッジ オブジェクトを指定して、最初の n 個の最も近いエッジ (2000) を見つける。

データ構造: Link クラスと Node クラス。リンク クラスには、それぞれのノード オブジェクトを指す from ノードと to ノードがあります。ノード オブジェクトには、リンク オブジェクトの受信リストと送信リストがあります。

エラー: RuntimeError: maximum recursion depth exceeded が発生しました。これを回避する方法を教えてください。ロジックに問題があるか、コードを最適化する必要があるかどうかをお知らせください。私は、オブジェクトに関連するノードからキューを作成するという BFS 戦略に従っていると信じています。

def start_search(self,link_object,neighbour_links):
    buffer_links=[]
    link_object.visited_flag=1
    neighbour_links.append(link_object)
    from_node=link_object.from_node
    to_node=link_object.to_node
    [buffer_links.append(link_object) for link_object in from_node.incoming_links]
    [buffer_links.append(link_object) for link_object in from_node.outgoing_links]
    [buffer_links.append(link_object) for link_object in to_node.outgoing_links]
    [buffer_links.append(link_object) for link_object in to_node.incoming_links]
    while len(buffer_links)>0 and len(neighbour_links)<1000:
        link_object=buffer_links.pop()
        if link_object.visited_flag==0:
           self.start_search(link_object,neighbour_links)
    return neighbour_links
4

2 に答える 2

1

ノードでアドバンスドウェーブフロントアルゴリズム（幅優先探索）を使用して再帰を使用することを回避できます。これがアルゴリズムの概要です。これは、エッジで機能するようにするための小さな適応です。

  1. top_dist最初は空の辞書を使用して、トポロジー距離を追跡します。
  2. させてdist = 0
  3. 初期ノードをセットに入れwavefrontます。
  4. top_dist[node] = distのノードごとに設定しますwavefront。
  5. に隣接するノードwavefrontがない場合はtop_dist、そのノードを追加して設定しnext_wavefrontます。
  6. インクリメントdist
  7. セットするwavefront = next_wavefront
  8. それ以上ノードに到達できなくなるまで、4から繰り返します。

一部のノードが未訪問のままである場合、グラフには複数の弱いコンポーネントがあります。

手順3の最初のノードが最初のエッジの端点である場合はtop_dist、エッジのノードのマップを使用して、エッジまでの距離を取得できます。エッジまでの距離の有用な定義はですmin(top_dist(e1), top_dist(e2)) + 1。各エッジまでの距離が決まったので、最も近い2000を取得できます。

このアルゴリズムはO（| N | + | E |）-エッジとノードの数の合計に対して線形です。

于 2013-02-08T03:55:16.467 に答える
0

後続ノードにマップされたノードのディクショナリとして表される DAG を使用すると、ノードを検出したときにノードをループできます。

>>> def bfs(dag, start, maximum):
        'Breadth-first search up to a given maximum number of nearest nodes'
        nearest = [start]
        seen = {start}
        for pred in nearest:
            for succ in dag.get(pred, ()):
                if succ not in seen:
                    seen.add(succ)
                    nearest.append(succ)
                    if len(nearest) == maximum:
                        return nearest
        return nearest
>>> dag = {'start': ['a', 'b', 'c'],
           'b': ['m', 'n'],
           'c': ['n', 'z'],
           'n': ['z'],
          }
>>> bfs(dag, 'start', 5)
['start', 'a', 'c', 'b', 'z']
于 2013-02-08T04:54:46.173 に答える