1

Python には、頂点オブジェクトのディクショナリを持つ Graph クラスがあります。各頂点オブジェクトには、エッジのディクショナリがあります (開始ノード、終了ノード、重みで構成されています...移動コストの数値が割り当てられた別のノードを指している矢印の端を想像してください)。

これらのクラスを使用して、飛行機が都市から都市へと飛行するのにかかる時間をグラフにしています。このグラフから、ダイクストラのアルゴリズムを使用して、2 つのノード間の最短経路 (最速経路) を決定することになっています。また、開始頂点から到達可能なすべての頂点を決定することになっています。

グラフで完全にエッジを追加したり、エッジを削除したり (その結果、ノードを追加したり) することができます。しかし、私の人生では、私が作成したデータ構造を使用して、ダイクストラのアルゴリズムまたは幅優先探索 (到達可能な頂点を決定するため) を実装する簡単な方法を理解できないようです。

これらのアルゴリズムを変更または実装して正しく動作させるために何をする必要があるかを誰かが提案できる場合は、助けていただければ幸いです。これは、私が 1 週間近く、1 日に何時間も取り組んできた宿題であり、この壁を乗り越えることができないようです。繰り返しますが、アドバイスや助けをいただければ幸いです。誰かが私のためにコードを書いてくれるとは思っていませんが、疑似コードが役に立ちます (そしてそれを適用します。ウィキペディアから疑似コードをコピーして貼り付けても、私は既にそこにいるので役に立ちません)。

4

1 に答える 1

1

コードが複雑すぎます。

基本を実装するだけのコードから始めて、徐々に機能を追加していきます。始めるために、グラフを扱うときに簡単ですが基本的なものを投稿します。

from collections import deque

class fringe(object):
    def __init__(self, kind= 'stack'):
        f= deque()
        self._p= f.append if kind is 'stack' else f.appendleft
        self._f= f

    def __call__(self, item):
        self._p(item)
        return self

    def __iter__(self):
        while len(self._f):
            item= self._f.pop()
            yield item

    def __repr__(self):
        return self._f.__repr__().replace('deque', 'fringe')

def paths(G, start, terminal, F= fringe()):
    for node, path in F((start, [start])):
        for node in G[node]:
            if node is terminal:
                yield path+ [terminal]
            elif node not in path:
                F((node, path+ [node]))

とテスト：

if __name__ == '__main__':
    a, b, c, d, e, f= 'A', 'B', 'C', 'D', 'E', 'F'
    G= {a: [b, c], b: [c, d], c: [d], d: [c], e: [f], f: [c]}
    print 'All paths from:', a, 'to:', d
    print 'BFS'
    for path in paths(G, a, d): print path
    print 'DFS'
    for path in paths(G, a, d, fringe('queue')): print path

実行すると、次のようになります。

All paths from: A to: D
BFS
['A', 'C', 'D']
['A', 'B', 'D']
['A', 'B', 'C', 'D']
DFS
['A', 'B', 'D']
['A', 'C', 'D']
['A', 'B', 'C', 'D']
于 2011-05-11T10:13:37.810 に答える