Python에서 Dijkstra의 알고리즘 구현
저는 Dijkstra's algorithmPython을 사용하여 경제 모델에 대한 연구를 구현 했습니다. 내 연구에서 두 가지 기능과 그 차이점을 조사하고 있습니다. 모든 함수는 입력으로 두 개의 매개 변수를 취합니다 : F(a,b)및 Z(a,b).
행렬의 모든 셀은 다음과 같이 정의됩니다. $$M[a][b]=|F(a,b)-Z(a,b)|$$
이것의 목적은 모든 입력에 대해 올바른 방정식 간의 최소 차이의 경로를 찾는 것입니다. a
Dijkstra 알고리즘의 온라인 구현은 모두 가중치가 적용된 가장자리를 사용하는 반면 나는 가중치가있는 정점을 사용했습니다.
의사 코드 :
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[]
입력:
- 각 셀 값이 가중치 인 2D 배열
- 소스 튜플 (x, y)
산출:
각 셀이 소스에서 정점까지의 거리를 포함하는 거리 행렬 (i, j)
각 셀이 부모를 포함하는 prev 행렬. (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초기화 및 검색 - 알고리즘은 두 부분으로 구성되어 있습니다. 이 두 부분을 분할하면 코드가 더 명확 해집니다. 즉, 한 부분 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) 멤버십 테스트를 지원합니다. 이것은 방문 / 비 방문 노드의 부기에 더 적합합니다.
그래프를 통해 검색하기 위해 우리는 이웃을 반복해서 방문 할 것입니다. 이것은 쉽게 잘못 될 수있는 핵심 부분입니다. Graph 구현이 제공하지 않는 한 명시 적으로 구현하는 것이 가치가 있습니다.
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세트 여야 할 것 같습니다 . 당신은 주문에 대해 신경 쓰지 않으며, 당신이 그것을 사용하는 유일한 것은 세트의 회원을 추적하는 것입니다. 여기서 세트는 훨씬 더 빠릅니다. 필요한 두 가지 변경 사항은 다음과 같습니다.
Q = set()
. . .
Q.add((i, j))
내가 볼 수있는 유일한 변화는 dijkstra_get_min기술적으로의 순서에 의존한다는 것입니다 Q. 최소값이 동일한 두 요소가 Q에 있으면 알고리즘이 마지막 인스턴스를 선택합니다. 세트는 다른 순서를 사용할 수 있으므로 반환되는 정점을 변경할 수 있습니다.
MAX_DISTANCE다른 모든 것보다 작은 임의의 숫자를 의미하는 것 같습니다 . 그것을 위해 사용해 볼 수도 있습니다 np.inf. 상한을 하드 코딩하면 나중에 문제가 "성장"하여 잠재적으로 최대치를 초과 할 위험이 있습니다. 잘못된 행동을 유발합니다.