"데이크스트라 알고리즘"의 두 판 사이의 차이

잔글
봇: 틀 이름 및 스타일 정리
(번역:en:Dijkstra's algorithm, 주석처리한 단어는 대체할 단어를 아시면 바꿔주십시오)
잔글 (봇: 틀 이름 및 스타일 정리)
 
# 모든 꼭짓점을 미방문 상태로 표시한다. ''미방문 집합''이라는 모든 미방문 꼭짓점의 집합을 만든다.
# 모든 꼭짓점에 시험적 거리 값을 부여한다: 초기점을 0으로, 다른 모든 꼭짓점을 무한대로 설정한다. 초기점을 현재 위치로 설정한다.
# 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 그 ''시험적'' 거리를 현재 꼭짓점에서 계산한다. 새로 계산한 ''시험적'' 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다. 예를 들어, 현재 꼭짓점 ''A''의 <!--시험적 ((이 거리는 '''시험적 거리가 아니기''' 때문에 주석 처리 했습니다.. 이 값은 인접 꼭짓점을 방문할 때 바뀔 수 없습니다.. 따라서 이것을 시험적이라고 부르는 것은 아직 바뀔 수 있다는 것을 의미하므로 혼동을 줄 수 있습니다))-->거리가 6이라고 표시되었고, 인접 꼭짓점 ''B''으로 연결되는 변의 길이가 2라고 한다면, ''A''를 통한 ''B''의 거리는 6 + 2 = 8이 될 것이다. B가 이전에 거리가 8보다 크다고 표시되었었다면 8로 바꾸고, 그렇지 않다면 그대로 놔둔다.
# 만약 현재 노드에 인접한 모든 미방문 꼭짓점을 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 ''미방문 집합''에서 제거한다. 방문한 꼭짓점은 이후에는 다시 검사하지 않는다.
<!-- 이 거리는 마지막이며 최솟값으로 기록된다. ((거리는 큐에서 꺼내어 다루고 있던 현재 위치에 대해서 마지막이기 때문에 주석 처리했습니다.. 이 거리는 인접 꼭짓점을 방문하는 동안 줄어들 수 없습니다.. 하지만 현재 꼭짓점은 이 단계 전까지는 미방문 상태입니다. 이 점은 일관적이지 않으며 혼란을 줍니다.)) -->
<!-- # 시험적 거리가 가장 작은 다음 미방문 꼭짓점으로 이동하고 위의 인접 꼭짓점을 계산하고 방문한 상태로 표시하는 단계를 반복한다. ((이 줄은 아래의 내용과 동일하며, 무한루프를 형성하고, 설명이 더 모호합니다)) -->
# 도착점이 방문한 상태로 표시되거나 (특정 두 꼭짓점 사이의 경로를 계획하고 있을 때) ''미방문 집합''에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면(완전 순회를 계획중일 때. 이 현상은 초기점과 나머지 미방문 집합 간에 연결이 없을 때 일어난다), 멈춘다. 알고리즘을 종료한다.
9
10 dist[''source''] ← 0 ''// 소스에서 소스까지의 길이''
11
12 '''while''' ''Q'' is not empty:
13 ''u'' ← vertex in ''Q'' with min dist[u] ''// 최소 거리를 갖는 꼭짓점''
14 ''// 을 가장 먼저 선택한다''
15 remove ''u'' from ''Q''
16
17 '''for each''' neighbor ''v'' of ''u'': ''// v는 여전히 Q에 있다.''
18 ''alt'' ← dist[''u''] + length(''u'', ''v'')
19 '''if''' ''alt'' < dist[''v'']: ''// v 까지의 더 짧은 경로를 찾았을 때''
20 dist[''v''] ← ''alt''
21 prev[''v''] ← ''u''
22
23 '''return''' dist[], prev[]
4 create vertex set Q
5
6 '''for each''' vertex ''v'' in ''Graph'':
7 '''if''' ''v'' ≠ ''source''
8 dist[''v''] ← INFINITY ''// 소스에서 v까지의 아직 모르는 길이''
15 ''u'' ← ''Q''.extract_min() ''// 최고의 꼭짓점을 제거하고 반환한다''
16 '''for each''' neighbor ''v'' of ''u'': ''// Q에 여전히 남아 있는 v에 대해서만''
17 ''alt'' ← dist[''u''] + length(''u'', ''v'')
18 '''if''' ''alt'' < dist[''v'']
19 dist[''v''] ← ''alt''
 
게다가, 그래프에 있는 모든 꼭짓점을 삽입하지 않으면 알고리즘을 무한 그래프나 메모리로 표현하기에는 너무 큰 그래프에서 시작점에서 도착점까지의 최단 경로를 찾도록 확장할 수 있다. 그 결과로 나타나는 알고리즘은 인공지능 분야에서 ''균일 비용 탐색'' (UCS)이라고 불리고{{r|felner}}<ref name="aima">{{Cite AIMA|3|pages=75, 81}}</ref><ref>또는 종종 ''최소 비용 우선 탐색''이라고도 불린다: {{저널 인용|last=Nau |first=Dana S. |title=Expert computer systems |journal=Computer |publisher=IEEE |volume=16 |issue=2 |year=1983 |pages=63–85 |url=https://www.cs.umd.edu/~nau/papers/nau1983expert.pdf |doi=10.1109/mc.1983.1654302}}</ref> 다음의 의사 코드로 나타낼 수 있다
 
'''procedure''' ''UniformCostSearch''(Graph, start, goal)
node ← start
 
==참조==
{{reflist각주}}
 
== 참고 문헌 ==

편집

1,378,168