Pythonでのダイクストラのアルゴリズムの実装
Dijkstra's algorithmPythonを使用して、経済モデルの研究のために実装しました。私の研究では、2つの機能とそれらの違いを調査しています。すべての関数は、入力として2つのパラメーターを取ります：F(a,b)とZ(a,b)。
マトリックスのすべてのセルは次のように定義されます。 $$M[a][b]=|F(a,b)-Z(a,b)|$$
これの目的は、すべての入力に対して正しい方程式間の最小の差のパスを見つけることです。 a
ダイクストラのアルゴリズムのオンライン実装はすべて重み付きエッジを使用していましたが、私は頂点に重みを付けました。
擬似コード：
function Dijkstra(Graph, source):
create vertex set Q
for each vertex v in Graph:
dist[v] ← INFINITY
prev[v] ← UNDEFINED
add v to Q
dist[source] ← 0
while Q is not empty:
u ← vertex in Q with min dist[u]
remove u from Q
for each neighbor v of u: // only v that are still in Q
alt ← dist[u] + length(u, v)
if alt < dist[v]:
dist[v] ← alt
prev[v] ← u
return dist[], prev[]
入力：
- 各セルの値がその重みである2次元配列
- ソースタプル（x、y）
出力：
各セルにソースから頂点までの距離が含まれる距離行列（i、j）
各セルにその親が含まれる前の行列。（98,98）からトレースバックすることで、最短経路を見つけることができます。
実装：
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
def dijkstra_get_min(Q, dist):
min = MAX_DISTANCE + 1
u = None
for vertex in Q:
if dist[vertex[0], vertex[1]] <= min:
min = dist[vertex[0], vertex[1]]
u = vertex
return u
def dijkstra(graph, src=(0, 0)):
dist = np.array([np.array([0 for x in RANGE_ARR], dtype=float) for y in RANGE_ARR])
prev = np.array([np.array([(0, 0) for x in RANGE_ARR], dtype='i,i') for y in RANGE_ARR])
Q = []
for i in RANGE_ARR_0:
for j in RANGE_ARR_0:
dist[i, j] = MAX_DISTANCE
prev[i, j] = (0, 0)
Q.append((i, j))
dist[0][0] = 0
while Q:
u = dijkstra_get_min(Q, dist)
Q.remove(u)
moves = [x for x in ( (u[0], u[1] + 1), (u[0] + 1, u[1]), (u[0] + 1, u[1] + 1) ) if x in Q]
for v in moves:
alt = dist[u[0]][u[1]] + graph[v[0]][v[1]]
if alt < dist[v[0]][v[1]]:
dist[v[0], v[1]] = alt
prev[v[0], v[1]] = u
return dist, prev
その正しさについて何か意見はありますか？
回答
コードは概ね正しいように見えますが、無視srcして正の方向にのみ検索します。さらに、クリーンアップして大幅に最適化することができます。
最初にいくつかの一般的なコメント：
- コードでは、意味/目的を表す完全な変数名を使用します。意味のある名前を使用するのに大きなコストはかかりませんが、コードを簡単に消化できるようになります。
- ホスト言語の機能と標準に注意してください。ビルトインの名前（例
min）を再利用することは避け、コーディングスタイルの標準に準拠するようにしてください。 numpy組み込みの機能を実際に使用しない限り、避けてください。numpy.array直接アクセスに使用すると、アクセスごとに値が完全なPythonオブジェクトに変換されるため、通常は/ / ...よりも遅くなります。listset
データの特徴について推測しないでください。具体的には、次のことは避けてください。
MAX_DISTANCE = 99999
RANGE_ARR = [x for x in range(1, 1001)]
これらは、距離が99999を超えるグラフまたは1000要素を超えるグラフでは失敗します。入力に対してそれらを計算するか、真の上限を使用します。
数値には明確に定義された「最大」があるため、これを安全に使用できます。
INFINITY = float('int')
入力graphはnxn行列なので、そのサイズを照会するだけです。
# inside `def dijkstra(graph, source):`
indices = range(len(graph))
vertex in Q with min dist[u]/から始めましょうdijkstra_get_min。あなたのアルゴリズムは適切ですが、Pythonの組み込みがminすでにカスタムの重みを許可していることを利用できます。for vertex in Q:主要な引数となりmin、if dist[vertex[0], vertex[1]] <= min:重量となりkey。
def dijkstra_get_min(vertices, distances):
return min(vertices, key=lambda vertex: distance[vertex[0]][vertex[1]])
Dijkstra初期化と検索-アルゴリズムは、2つの部分から構成されています。これらの2つの部分を分割すると、コードがより明確になりますdist[0][0] = 0。つまり、行は一方から他方への遷移です。
def dijkstra(graph, src=(0, 0)):
# dist, prev, Q
distances, prev_nodes, unvisited = dijkstra_initial(len(graph))
# set starting point
distances[src[0]][src[1]] = 0
dijkstra_search(graph, distances, prev_nodes, unvisited)
return distances, prev_nodes
初期化の目的は、すべてのポイントが同じ値を持つことです。これは、最終値を使用してマトリックスを直接作成できることを意味します。また、アルゴリズムは「前のノード」を使用しないため、安価なプレースホルダーに初期化できます。
def dijkstra_initial(size):
distances = [[INFINITY] * size for _ in range(size)]
prev_nodes = [[None] * size for _ in range(size)]
unvisited = {(x, y) for x in range(size) for y in range(size)}
# dist, prev, Q
return distances, prev_nodes, unvisited
訪問したノードをリスト（[..., ...]）として追跡する代わりに、セット（{..., ...}）を使用します。セットは順序付けられておらず、リストO（n）メンバーシップテストと比較して、O（1）メンバーシップテストをサポートします。これにより、訪問済み/未訪問のノードの簿記に適しています。
グラフを検索するために、私たちは隣人を繰り返し訪問します。これは簡単に間違って実行される可能性のある重要な部分です。グラフの実装で提供されない限り、明示的に実装する価値があります。
def neighbours(node):
x, y = node
return [
(x + x_offset, y + y_offset)
for x_offset in (-1, 0, 1)
for y_offset in (-1, 0, 1)
if not (x_offset == y_offset == 0) # reject node itself
]
アルゴリズムのコアは論理的に同じままです。より話すようにいくつかの名前を調整します（例：u-> node、v-> neighbour）。neighbours長い表現の代わりに準備された表現を使用します。
def dijkstra_search(graph, distances, prev_nodes, unvisited):
while unvisited:
node = dijkstra_get_min(unvisited, dist)
unvisited.remove(node)
for neighbour in neighbours(node):
if neighbour not in unvisited:
continue
alt = distances[node[0]][node[1]] + graph[neighbour[0]][neighbour[1]]
if alt < distances[neighbour[0]][neighbour[1]]:
distances[neighbour[0]][neighbour[1]] = alt
prev_nodes[neighbour[0]][neighbour[1]] = node
この時点で、コードはより高速で保守が容易になるはずです。私たちがまだ持っている最も明白な欠陥は、寸法の明示的な取り扱いです。各ディメンションに手動でアクセスするのではなく、ポイントに直接アクセスできる方がよいでしょう。
# currently
distances[neighbour[0]][neighbour[1]]
# desirable
distances[neighbour]
これは{point: value, ...}、ネストされたリスト（[[value, ...], ...]）の代わりに辞書（）を使用することで「修正」できます。直接の欠点は、これがメモリと単純さを交換することです。
ただし、実際にメモリ使用量を削減するために使用できます。辞書は自然にまばらになり、未決定のフィールドを保存しないようにすることができます。訪問したノードは距離とは無関係になるため、distancesすでに処理されているノードをクリアすることもできます。
[x for x in range(1, 1001)]と書くことができますlist(range(1, 1001))。
その1001名前も付けておくといいでしょう。
同様に、[0 for x in RANGE_ARR]と書くことができます[0] * len(RANGE_ARR)。シーケンスタイプに整数を掛けると、シーケンス内の要素が繰り返されます。ボーナスとして、私が今行ったいくつかの簡単なベンチマークから、それはまた10倍以上速いです：
from timeit import timeit
N = int(1e6)
TRIALS = int(1e3)
print(timeit(lambda: [0] * N, number=TRIALS), "seconds")
print(timeit(lambda: [0 for x in range(N)], number=TRIALS), "seconds")
2.9889957 seconds
38.1463017 seconds
ただし、要素タイプが変更可能である場合（のように[[0]] * 5）、これを使用しないように注意してください。シーケンスを乗算すると、同じオブジェクトへの複数の参照が作成されます。コピーは作成しません。
それは次のようになりますQ設定する必要があります。あなたは順序を気にしません、そしてあなたがそれを使う唯一のことはセットのメンバーシップを追跡することです。ここではセットが大幅に高速になります。必要な変更は次の2つだけです。
Q = set()
. . .
Q.add((i, j))
この作成を確認できる唯一の変更は、dijkstra_get_min技術的にはの順序に依存していることですQ。同じ最小値を持つ2つの要素がQにある場合、アルゴリズムは最後のインスタンスを選択します。セットは異なる順序を使用する可能性があるため、これにより、返される頂点が変わる可能性があります。
それは、MAX_DISTANCE他のすべてがより少なくなる任意の大きな数であることを意味しているように見えます。あなたはnp.infそのために使ってみたくなるかもしれません。上限をハードコーディングすることにより、問題が後で「拡大」し、その最大値を超える可能性があるリスクがあります。誤った動作を引き起こします。