3

NetworkXライブラリを使用して最短経路アルゴリズムを実装したいと思います。私の場合、重み関数は他のエッジ属性から値を導き出します。重みは計算値であるため、他の属性が変更されたときに値を更新するなどの複雑さを避けるために、追加の属性として保存したくありません。ただし、 NetworkXのアルゴリズムAPIでは、エッジデータキーとして重みが必要なようです。

それで、値を保存しないことは可能かどうか疑問に思いましたか？私の理想的なケースは、アルゴリズムにカスタムの重み関数を指定することです。

4

2 に答える 2

4

パラメータは、エッジ属性ディクショナリのキーである必要があります。そのため、辞書にエッジ属性を設定して重みとして使用する必要があります。最短パスを計算する前に単純なループでそれらを割り当てることができます (必要に応じて後で削除します)。

または、ダイクストラ アルゴリズム コードを変更して、他のエッジ属性から重みを計算することもできます。グラフ (マルチグラフではない) があると仮定すると、それは 1 行の変更です。重み式を 231 行目に入れます https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/shortest_paths/weighted.py#L231

vw_dist = dist[v] + edgedata.get(weight,1)
于 2011-05-04T03:01:07.157 に答える
3

重みの値を遅延して計算できますが、プロパティを使用して属性であるかのように表示できます。例えば：

class Edge(object):

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get_z(self):
        return self.x + self.y

    z = property(get_z)


e = Edge(3,4)
print e.z

ここe.zには、オブジェクトの属性である実際に格納された値が表示されEdgeます。しかし、そうではありません。オンデマンドで計算されます。メソッドで更新コードを記述するget_z必要がありますが、ここでの利点は、依存するプロパティが変更されるたびに具体的な値を更新することを心配する必要がないことです。代わりに、要求されたときにのみ計算します。

zこの例をキャッシュ値に拡張するのは簡単です。多くのアクセスが不要で潜在的に高価な計算を引き起こすことを懸念している場合です。ゲッターは、計算を行う前にルックアップ テーブルをチェックします。これは単なるメモ化です。

于 2011-05-02T20:02:47.323 に答える