안녕하세요, 우리는 이번 포스트에서 그래프 탐색 알고리즘과 가장 효율적인 길찾기 방법에 대해 함께 알아보겠습니다. 먼저, 미로의 길찾기 문제를 그래프로 변환하는 방법과 그래프의 노드와 엣지에 대한 개념을 설명한 다음, 그래프 탐색 알고리즘과 최단 경로 찾기 알고리즘을 소개하겠습니다.
미로의 길찾기 문제 개요
미로 문제는 고전적인 문제로, 시작점에서 목표점까지 가장 빠른 길을 찾는 것입니다. 이 문제는 그래프 탐색 알고리즘을 사용하여 해결할 수 있습니다. 미로를 그래프로 변환하면, 그래프의 노드와 엣지를 통해 길을 찾을 수 있습니다.
미로를 그래프로 변환하기
미로를 그래프로 변환하기 위해서는 먼저 미로의 각 칸을 노드로 간주합니다. 두 칸이 인접하고 벽이 없다면, 이 두 노드 사이에 엣지를 그립니다. 이렇게 하면, 미로의 길찾기 문제를 그래프 탐색 문제로 변환할 수 있습니다. 이 과정은 다음과 같은 python 코드로 시각화할 수 있습니다.
import matplotlib.pyplot as plt
import numpy as np
def maze_to_graph(maze):
# ...
return graph
maze = np.array([
[1, 0, 1, 1, 1],
[1, 0, 1, 0, 1],
[1, 1, 1, 0, 1],
[1, 0, 1, 1, 1],
[1, 1, 0, 0, 1]
])
graph = maze_to_graph(maze)
plt.imshow(graph)
plt.show()노드와 엣지 이해하기
그래프는 노드(Node)와 엣지(Edge)로 구성되어 있습니다. 노드는 길찾기 문제에서 갈 수 있는 위치를 나타내며, 엣지는 노드 간의 연결을 표현합니다. 엣지의 가중치는 두 노드 사이의 거리나 비용을 나타낼 수 있습니다.
그래프 탐색 알고리즘 소개
그래프 탐색 알고리즘은 그래프의 노드와 엣지를 탐색하여 원하는 목표를 달성하기 위한 방법입니다. 그래프 탐색 알고리즘에는 여러 종류가 있는데, 주요 알고리즘으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. 각 알고리즘의 특징과 장단점을 알아봅시다.
깊이 우선 탐색(Depth-First Search, DFS)
깊이 우선 탐색(DFS)은 그래프에서 한 방향으로 깊게 들어가며 노드를 탐색하는 방법입니다. 이 방법은 다양한 문제를 해결하는 데 사용되며, 미로 길찾기에도 적용할 수 있습니다. 우리는 이제 깊이 우선 탐색의 특징과 장단점을 살펴보겠습니다.
DFS의 작동 원리
DFS는 시작 노드부터 목표 노드까지 깊이 방향으로 우선 탐색합니다. 이 과정에서 이미 방문한 노드를 다시 방문하지 않도록 주의해야 합니다. DFS는 재귀 함수를 사용하여 구현할 수 있으며, 스택 자료 구조를 활용하여 구현할 수도 있습니다.
예를 들어, 다음과 같은 그래프가 있다고 가정해봅시다.
A -- B -- C
| |
D -- E -- FDFS는 깊이 방향으로 노드를 탐색하기 때문에, 시작 노드 A에서 가능한 한 깊게 노드를 방문하게 됩니다. 이 경우, A에서 갈 수 있는 노드는 B와 D입니다. 여기서 임의로 A에서 B를 먼저 방문하기로 합니다.
순서: A → B이제 B에서 갈 수 있는 노드는 A와 C입니다. 그러나 A는 이미 방문한 노드이므로, 다음으로 방문할 노드는 C가 됩니다.
순서: A → B → C다음으로 C에서 갈 수 있는 노드는 B와 F입니다. B는 이미 방문한 노드이므로, F를 방문하게 됩니다.
순서: A → B → C → F이제 F에서 갈 수 있는 노드는 C와 E입니다. C는 이미 방문한 노드이므로, 다음으로 방문할 노드는 E가 됩니다.
순서: A → B → C → F → E마지막으로 E에서 갈 수 있는 노드는 D와 F입니다. F는 이미 방문한 노드이므로, 마지막으로 방문할 노드는 D가 됩니다.
순서: A → B → C → F → E → D결론적으로, 깊이 우선 탐색(DFS)을 사용하여 이 그래프에서 노드를 방문하면 A → B → C → F → E → D 순서로 방문하게 됩니다. 이 예제에서는 A에서 시작하여 B를 먼저 방문하는 것으로 가정했지만, 실제로는 A에서 시작하여 D를 먼저 방문하는 경우도 있을 수 있으며, 그 경우에는 다른 방문 순서가 나올 수 있습니다.
네, 깊이 우선 탐색(DFS)의 장단점에 대해 더 자세히 설명드리겠습니다.
DFS의 장점
- 메모리 효율성: DFS는 스택이나 재귀 함수를 사용하여 탐색을 진행하기 때문에, 메모리 사용량이 상대적으로 적습니다. 노드가 많은 대규모 그래프를 탐색할 때도 사용할 수 있어 메모리 효율성이 높습니다.
- 모든 경로 탐색 가능: 깊이 우선 탐색은 가능한 모든 경로를 따라 탐색하기 때문에, 경로가 많은 경우에도 모든 경로를 찾을 수 있습니다. 이러한 특징은 여러 경로 중 특정 조건을 만족하는 경로를 찾을 때 유용하게 사용됩니다.
- 사이클 탐지: DFS는 그래프 내 사이클을 탐지하는 데 사용될 수 있습니다. 그래프 내 사이클이 있는지 여부를 판별하는 것은 그래프의 특성을 이해하고 응용하는 데 중요한 요소입니다.
DFS의 단점
- 최단 경로 찾기 불가: 깊이 우선 탐색은 최단 경로를 보장하지 않기 때문에, 최단 경로 문제에 대한 정확한 해를 찾지 못할 수 있습니다. 따라서, 최단 경로를 찾아야 하는 문제에는 다른 알고리즘(예: 다익스트라 알고리즘)을 사용하는 것이 더 적절합니다.
- 시간 복잡도: DFS는 모든 노드를 방문해야 하므로, 시간 복잡도가 높을 수 있습니다. 시간 복잡도는 $O(|V| + |E|)$입니다($|V|$는 노드 수, $|E|$는 엣지 수). 그래프의 크기가 크고 노드와 엣지의 수가 많을수록 탐색 시간이 길어집니다.
- 스택 오버플로우: DFS는 재귀 함수를 사용하여 구현될 수 있으며, 이 경우 스택 오버플로우의 위험이 있습니다. 함수 호출이 깊어질수록 스택 메모리가 증가하며, 이로 인해 프로그램이 비정상적으로 종료될 수 있습니다. 이를 해결하기 위해 반복문을 사용한 스택 기반 구현을 사용할 수 있습니다.
너비 우선 탐색 (Breadth-First Search, BFS)
너비 우선 탐색(BFS)은 그래프를 탐색하는 또 다른 알고리즘입니다. BFS는 시작 노드에서부터 가장 가까운 노드를 우선 방문한 후, 이와 연결된 노드들을 순차적으로 방문하는 방식으로 진행됩니다. 이 알고리즘은 큐(Queue)를 사용하여 노드의 방문 순서를 관리합니다. 이 과정에서 노드들이 동일한 거리에 있는 노드를 차례대로 방문하게 됩니다.
예를 들어, 아래 그래프에서 BFS를 사용하여 노드를 방문하는 순서를 알아보겠습니다.
A -- B -- C
| |
D -- E -- F- 시작 노드인 A를 큐에 넣고, 방문한 것으로 표시합니다.
- 큐가 비어있지 않은 경우 다음 단계를 수행합니다.
- 큐에서 노드를 하나 꺼냅니다(이 경우 A).
- 꺼낸 노드와 인접한 노드들을 살펴봅니다.
- 인접한 노드 중 아직 방문하지 않은 노드들을 큐에 넣고, 방문한 것으로 표시합니다(이 경우 B와 D).
- 위 단계를 큐가 비어있을 때까지 반복합니다.
BFS 알고리즘을 적용한 결과, 노드를 방문하는 순서는 다음과 같습니다.
순서: A → B → D → C → E → FBFS 알고리즘은 시작 노드에서 가장 가까운 노드부터 방문하기 때문에 동일한 거리에 있는 노드들을 모두 방문한 후, 다음 거리에 있는 노드들을 순차적으로 방문합니다. 이러한 작동 방식 덕분에 BFS는 최단 경로 문제에 적합하며, 저런 순서로 노드를 방문하게 됩니다.
너비 우선 탐색(BFS) 알고리즘의 장단점을 자세히 살펴보겠습니다.
BFS의 장점
- 최단 경로 찾기: BFS는 시작 노드에서 다른 노드까지의 최단 경로를 찾을 수 있는 알고리즘입니다. 가장 가까운 노드를 우선 방문하기 때문에, 같은 깊이의 노드를 모두 방문하게 됩니다. 이런 특징 덕분에 최단 경로를 찾는 문제에 BFS가 적합합니다.
- 레벨 순서 순회: BFS는 그래프의 노드를 레벨 별로 순회하게 됩니다. 이는 트리와 같은 계층 구조의 그래프에서 특정 레벨의 노드들을 차례대로 방문하고자 할 때 유용하게 사용될 수 있습니다.
- 직관적이고 구현하기 쉬움: BFS는 큐를 사용하여 방문 순서를 관리하므로, 알고리즘을 이해하고 구현하기가 상대적으로 쉽습니다. 파이썬, 자바 등 다양한 프로그래밍 언어에서 큐를 사용할 수 있는 자료구조가 제공되기 때문에, BFS 알고리즘을 쉽게 구현할 수 있습니다.
BFS의 단점
- 메모리 소모: BFS 알고리즘은 큐를 사용하여 방문한 노드의 정보를 저장합니다. 그래프의 노드 수가 많아질수록 큐에 저장되는 노드의 수도 증가하므로, 메모리 소모가 크게 될 수 있습니다.
- 시간 복잡도: BFS는 그래프의 모든 노드와 간선을 방문하므로, 시간 복잡도는 O(|V|+|E|)가 됩니다. 여기서 |V|는 노드의 수, |E|는 간선의 수를 의미합니다. 그래프의 크기가 큰 경우 BFS 알고리즘의 수행 시간이 길어질 수 있습니다.
- 가중치가 있는 그래프에는 적합하지 않음: BFS 알고리즘은 가중치가 없는 그래프에서만 최단 경로를 찾을 수 있습니다. 가중치가 있는 그래프에서는 다른 알고리즘(예: 다익스트라 알고리즘, 벨만-포드 알고리즘)을 사용하여 최단 경로를 찾아야 합니다.
그래프 최단거리 찾기 알고리즘 소개
그래프에서 최단 경로를 찾는 알고리즘은 시작 노드로부터 목표 노드까지의 최단 경로를 찾는 문제에 사용됩니다. 이러한 알고리즘은 다양한 분야에서 활용되며, 그 중 다익스트라 알고리즘과 A* 알고리즘이 대표적입니다. 이제 각 알고리즘의 특징과 장단점에 대해 알아보겠습니다.
다익스트라 알고리즘 소개
다익스트라 알고리즘은 네덜란드 컴퓨터 과학자 에츠거 다익스트라(Edsger Dijkstra)가 개발한 그래프의 최단 경로 문제를 해결하는 유명한 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 시작 노드로부터 다른 노드까지의 최단 경로를 찾기 위해 사용됩니다. 다익스트라 알고리즘은 그리디 알고리즘의 한 종류로, 각 단계에서 가장 작은 가중치를 가진 노드를 선택하여 경로를 구성합니다.
다익스트라 알고리즘은 시작 노드에서 모든 노드까지의 거리를 무한대로 초기화한 후, 시작 노드의 거리를 0으로 설정합니다. 그 다음, 우선순위 큐를 사용하여 현재 노드로부터 가장 가까운 노드를 선택하고, 이를 방문하지 않은 인접 노드들의 거리를 업데이트합니다. 이 과정은 모든 노드를 방문할 때까지 반복됩니다.
수식으로 표현하면 다음과 같습니다.
- 시작 노드를
s라고 하면, 모든 노드v에 대해 거리 배열dist[v]를 초기화합니다.dist[s] = 0이고 나머지 노드들은dist[v] = ∞로 설정합니다. - 우선순위 큐
Q를 사용하여 거리가 가장 짧은 노드를 선택합니다. 즉,u = argmin(dist[v] for v in Q)입니다. - 선택한 노드
u와 인접한 모든 노드v에 대해,dist[u] + weight(u, v) < dist[v]가 성립하면dist[v]를 업데이트합니다. 여기서weight(u, v)는 노드u와v사이의 가중치를 나타냅니다. - 모든 노드를 방문할 때까지 위 과정을 반복합니다.
이제 다음과 같은 가중치가 있는 그래프를 가정하여 예제를 살펴봅시다.
A --1-- B --2-- C
| | |
4 3 5
| | |
D --6-- E --7-- F다익스트라 알고리즘을 이용하여 시작 노드 A에서 다른 노드들까지의 최단 경로를 찾아봅니다.
- 시작 노드 A의 거리를 0으로 설정합니다. 나머지 노드들의 거리는 무한대로 초기화합니다.
dist[A] = 0 dist[B] = dist[C] = dist[D] = dist[E] = dist[F] = ∞- 노드 A에서 인접한 노드 B와 D의 거리를 업데이트합니다.
dist[B] = 1 (dist[A] + weight(A, B)) dist[D] = 4 (dist[A] + weight(A, D))- 현재까지 방문하지 않은 노드 중 거리가 가장 짧은 노드 B를 선택합니다.
- 노드 B를 기준으로 인접한 노드 C와 E의 거리를 업데이트합니다.
dist[C] = 3 (dist[B] + weight(B, C)) dist[E] = 4 (dist[B] + weight(B, E))- 현재까지 방문하지 않은 노드 중 거리가 가장 짧은 노드 D를 선택합니다.
- 노드 D의 인접 노드 E의 거리를 업데이트합니다. 그러나, 이미 노드 B에서 노드 E로 가는 최단 거리가 4로 업데이트되었으므로, 노드 D를 거쳐서 가는 경우(거리 10)는 무시됩니다.
- 현재까지 방문하지 않은 노드 중 거리가 가장 짧은 노드 C를 선택합니다.
- 노드 C의 인접 노드 F의 거리를 업데이트합니다.
dist[F] = 8 (dist[C] + weight(C, F))- 현재까지 방문하지 않은 노드 중 거리가 가장 짧은 노드 E를 선택합니다.
- 노드 E의 인접 노드 F의 거리를 업데이트합니다. 이미 노드 C에서 노드 F로 가는 최단 거리가 8로 업데이트되었으므로, 노드 E를 거쳐서 가는 경우(거리 11)는 무시됩니다.
- 현재까지 방문하지 않은 노드 중 거리가 가장 짧은 노드 F를 선택하고, 모든 노드를 방문하였으므로 알고리즘을 종료합니다.
결과적으로 다익스트라 알고리즘을 사용하여 시작 노드 A에서 다른 노드들까지의 최단 경로는 다음과 같이 구해집니다.
dist[A] = 0
dist[B] = 1
dist[C] = 3
dist[D] = 4
dist[E] = 4
dist[F] = 8이처럼 다익스트라 알고리즘을 사용하면 가중치가 있는 그래프에서 시작 노드로부터 다른 노드까지의 최단 경로를 효율적으로 찾을 수 있습니다.
다익스트라 알고리즘의 응용 (교통망 최적화히기)
교통량을 가중치로 사용하여 신호등 시간을 조절하는 방법을 소개합니다. 이 방법은 신호등 시간을 변경하여 교통 흐름을 최적화하는 데 도움이 됩니다.
- 교차로와 도로를 그래프의 노드와 엣지로 간주합니다. 각 도로(엣지)의 가중치는 해당 도로에서의 교통량입니다.
- 교통량 데이터를 수집합니다. 이를 통해 각 도로(엣지)의 가중치를 결정할 수 있습니다. 가중치는 교통량에 비례하여 설정합니다. 예를 들어, 도로 A의 교통량이 도로 B의 교통량의 2배라면, 도로 A의 가중치는 도로 B의 가중치의 2배로 설정합니다.
- 다익스트라 알고리즘을 적용하여 시작 교차로에서 다른 교차로까지의 최단 시간을 계산합니다. 이때, 가중치는 각 엣지의 교통량입니다.
- 다익스트라 알고리즘이 종료되면, 시작 교차로로부터 다른 교차로까지의 최단 시간이 계산됩니다. 이 시간을 바탕으로 신호등의 변경 시간을 조절할 수 있습니다.
- 교통량이 많은 도로의 신호등 변경 시간을 줄여서 교통 흐름을 개선하고, 교통량이 적은 도로의 신호등 변경 시간을 늘려서 교통 흐름을 분산시킬 수 있습니다.
교통 최적화 문제에서 사용되는 공식 중 일부는 실제 교통량 데이터에 기반한 모델링을 통해 도출됩니다. 여기서 소개할 몇 가지 공식은 주로 교통공학 및 최적화 분야에서 사용되며, 이를 바탕으로 교통량 분산 전략을 설계할 수 있습니다.
- 프랭크-울프 알고리즘 (Frank-Wolfe Algorithm): 프랭크-울프 알고리즘은 교통분배 문제에 사용되는 최적화 기법입니다. 교통량이 주어진 경우, 이 알고리즘은 모든 도로의 통행 시간을 최소화합니다. 이 알고리즘의 목적 함수는 다음과 같이 주어집니다.여기서 $x_a$는 도로 $a$의 교통량이고, $t_a(s)$는 도로 $a$에서 교통량이 $s$일 때의 통행 시간입니다. 알고리즘은 목적 함수 $F(x)$를 최소화하는 교통량 $x$를 찾습니다.
- $[F(x) = \sum_{a \in A} \int_0^{x_a} t_a(s) ds]$
- 퓨의 교통 공식 (User Equilibrium, UE): 퓨의 교통 공식은 교통 네트워크에서 사용자 균형 상태를 설명합니다. 이 상태에서는 모든 사용자가 자신의 여행시간을 최소화하려고 시도하며, 다른 경로로 변경할 경우 여행시간이 증가합니다. 이를 수식으로 표현하면 다음과 같습니다.여기서 $t_p$와 $t_q$는 경로 $p$와 $q$의 여행시간이고, $P$는 모든 가능한 경로의 집합입니다.
- $[t_p = t_q \quad \forall p, q \in P]$
이러한 공식들은 교통 최적화 문제를 해결하기 위한 기반이 되며, 다익스트라 알고리즘과 함께 사용되어 교통량 분산 전략을 설계할 수 있습니다. 하지만 이러한 공식들은 복잡한 교통 네트워크와 실시간 교통량 데이터를 처리하기 위해 추가적인 최적화 기법 및 휴리스틱이 필요합니다.
다익스트라 알고리즘의 장점
- 최단 경로 보장: 다익스트라 알고리즘은 항상 최단 경로를 찾을 수 있습니다. 이 알고리즘은 그래프에서 음수 가중치가 없는 경우에만 사용할 수 있으며, 최단 경로를 찾는 데 정확하고 안정적입니다.
- 구현이 상대적으로 간단: 다익스트라 알고리즘은 우선순위 큐를 사용하여 구현할 수 있으며, 코드가 상대적으로 간결하고 이해하기 쉽습니다.
다익스트라 알고리즘의 단점
- 음수 가중치의 제한: 다익스트라 알고리즘은 음수 가중치가 없는 그래프에서만 작동합니다. 음수 가중치가 있는 그래프에서는 벨만-포드 알고리즘 등 다른 알고리즘을 사용해야 합니다.
- 성능: 다익스트라 알고리즘은 모든 노드를 방문해야 할 수도 있기 때문에, 탐색 과정에서 시간이 오래 걸릴 수 있습니다. 이는 특히 노드와 엣지의 수가 많은 대규모 그래프에서 두드러집니다. 이와 같은 경우에는 A* 알고리즘과 같은 효율적인 최단 경로 알고리즘을 사용할 수 있습니다.
- 실시간 탐색에 대한 한계: 다익스트라 알고리즘은 전체 경로를 찾아야 하므로, 동적 환경에서 실시간으로 빠르게 경로를 찾는 데 어려움이 있을 수 있습니다. 이 경우, 다른 알고리즘(예: D* Lite)을 사용해야 할 수도 있습니다.
A* 알고리즘 (A* Algorithm)소개
A* 알고리즘은 최단 경로를 찾는데 사용되는 휴리스틱 기반의 알고리즘이며, 다익스트라 알고리즘을 개선한 방식입니다. 다익스트라 알고리즘이 최단 경로를 찾기 위해 그래프의 모든 노드를 방문하는 반면, A* 알고리즘은 휴리스틱 함수를 사용하여 목적지에 더 가까운 노드를 우선적으로 방문하므로 더 빠르게 목표 지점에 도달할 수 있습니다. 휴리스틱 함수는 노드간의 거리를 추정하는 데 사용되며, 문제의 특성에 따라 다양한 형태로 정의될 수 있습니다. 일반적인 휴리스틱 함수로는 유클리디안 거리, 맨하탄 거리, 치킨택시 거리 등이 있습니다. 휴리스틱 함수는 목표 노드에 대한 정확한 거리를 알 수 없기 때문에, 추정 비용을 계산하는 데 사용됩니다.
A* 알고리즘 (A* Algorithm)원리 및 동작 방식
A* 알고리즘은 다익스트라 알고리즘과 유사한 방식으로 동작하지만, 목적지에 대한 추정 비용을 고려하여 노드를 선택합니다. 각 노드에 대해 두 가지 값이 계산됩니다.
- $g(n)$: 시작 노드로부터 노드 $n$까지의 실제 비용
- $h(n)$: 노드 $n$에서 목표 노드까지의 추정 비용 (휴리스틱 함수)
각 노드의 총 비용 $f(n)$은 다음과 같이 계산됩니다.
$f(n) = g(n) + h(n)$
A* 알고리즘은 총 비용 $f(n)$이 가장 낮은 노드를 선택하여 탐색을 계속합니다. 이 과정은 목표 노드에 도달하거나, 더 이상 방문할 노드가 없을 때까지 반복됩니다.
다음과 같은 그래프에서 시작점 A에서 목표점 F까지의 최단 경로를 A* 알고리즘을 사용하여 찾아봅시다.
A --1-- B --2-- C
| | |
4 3 5
| | |
D --6-- E --7-- FA* 알고리즘에서 사용되는 휴리스틱 함수 h(n)을 정의해야 합니다. 이 예시에서는 맨하탄 거리(Manhattan distance)를 사용하겠습니다.
$$h(n) = |x_{n} - x_{goal}| + |y_{n} - y_{goal}|$$
여기서, $(x_{n}, y_{n})$는 노드 n의 좌표이고, $(x_{goal}, y_{goal})$는 목표점 F의 좌표입니다.
알고리즘의 각 단계에서 f(n) 값을 계산합니다. f(n)은 다음과 같이 정의됩니다.
$$f(n) = g(n) + h(n)$$
여기서, g(n)은 시작점 A로부터 노드 n까지의 실제 비용이고, h(n)은 노드 n에서 목표점 F까지의 추정 비용입니다.
알고리즘의 동작은 다음과 같습니다:
- 시작점 A에서 시작합니다.
- 인접한 노드 B와 D를 조사합니다.
- 각 노드에 대해 f(n) 값을 계산합니다. 시작점 A의 g(n) 값은 0입니다.
- 노드 B: $f(B) = g(B) + h(B) = 1 + 2 = 3$
- 노드 D: $f(D) = g(D) + h(D) = 4 + 1 = 5$
- f(n) 값이 가장 작은 노드인 B를 선택하고 현재 위치로 설정합니다.
- 노드 B에서 인접한 노드 C와 E를 조사합니다.
- 노드 C: $f(C) = g(C) + h(C) = 3 + 1 = 4$
- 노드 E: $f(E) = g(E) + h(E) = 4 + 1 = 5$
- f(n) 값이 가장 작은 노드인 C를 선택하고 현재 위치로 설정합니다.
- 노드 C에서 인접한 노드 F를 조사합니다.
- 노드 F: $f(F) = g(F) + h(F) = 8 + 0 = 8$
- 현재 위치가 목표점 F이므로 알고리즘을 종료하고 찾은 경로를 반환합니다. 경로는 A → B → C → F이며, 비용은 8입니다.
A* 알고리즘의 장점
- 효율성: A* 알고리즘은 휴리스틱 함수를 사용하여 더 가까운 노드를 우선적으로 방문하므로, 다익스트라 알고리즘에 비해 더 빠르게 목표 노드에 도달할 수 있습니다.
- 최적성: 휴리스틱 함수가 목표 노드에 대한 거리를 과소평가하지 않는다면, A* 알고리즘은 최단 경로를 보장합니다. 이는 다익스트라 알고리즘과 같은 최적성을 가지며, 효율성이 향상된 알고리즘입니다.
- 유연성: 휴리스틱 함수를 선택하는 것은 사용자에게 달려 있으며, 문제의 특성에 따라 다양한 형태로 정의될 수 있습니다. 이를 통해 알고리즘의 성능을 최적화할 수 있습니다.
A* 알고리즘의 단점
- 메모리 사용량: A* 알고리즘은 노드를 우선순위 큐에 저장하며, 탐색 과정에서 큐의 크기가 커질 수 있습니다. 이로 인해 메모리 사용량이 상당히 높을 수 있습니다.
- 휴리스틱 함수의 선택: 효율적인 휴리스틱 함수를 선택하는 것은 사용자에게 달려 있습니다. 잘못된 휴리스틱 함수를 선택하면 알고리즘의 성능이 저하될 수 있으며, 최적 경로를 찾지 못할 수도 있습니다.
- 실시간 탐색에 대한 한계: A* 알고리즘은 목표 노드까지의 전체 경로를 찾아야 하므로, 동적 환경에서 실시간으로 빠르게 경로를 찾는 데 어려움이 있을 수 있습니다. 이 경우, 다른 알고리즘(예: D* Lite)을 사용해야 할 수도 있습니다.
미로 생성 실습 | python code
미로 생성
import random
import numpy as np
# 주의사항
# 1. 미로의 크기는 반드시 홀수여야 합니다
# 2. 행렬의 시작은 0,0부터 시작합니다
# 3. 따라서 마지막 행과 열은 크기에서 1을 뺀 값과 같습니다
# 4. 시작점은 가장자리에 위치합니다
# 미로의 출발점과 도착점을 입력합니다.
width, height = (21, 21)
start = (0, 1)
end = (width - 1, height - 2) # 빼기 뒤의 숫자를 수정합니다.
# 미로 생성
def create_maze(height, width, start, end):
while True:
maze = np.ones((height, width), dtype=np.int8)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def is_valid(x, y):
return 0 <= x < height and 0 <= y < width and maze[x][y] == 1
def depth_first_search(x, y):
maze[x][y] = 0
random.shuffle(directions)
for dx, dy in directions:
nx, ny = x + 2 * dx, y + 2 * dy
if is_valid(nx, ny) and maze[nx][ny] == 1:
maze[nx][ny] = 0
maze[x + dx][y + dy] = 0
depth_first_search(nx, ny)
depth_first_search(1, 1)
# 미로의 외곽에 벽을 생성합니다.
maze[0, :] = 1
maze[-1, :] = 1
maze[:, 0] = 1
maze[:, -1] = 1
# 시작점과 도착점을 0으로 변경합니다.
maze[start[0], start[1]] = 0
maze[end[0], end[1]] = 0
if is_valid_maze(maze, start, end):
break
return maze, start, end
def is_valid_maze(maze, start, end):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def is_valid(x, y):
return 0 <= x < height and 0 <= y < width
visited = set()
stack = [start]
while stack:
x, y = stack.pop()
visited.add((x, y))
if (x, y) == end:
return True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if is_valid(nx, ny) and maze[nx][ny] == 0 and (nx, ny) not in visited:
stack.append((nx, ny))
return False
maze, start, end = create_maze(height, width, start, end)
# 미로 출력
for i in range(height):
row = []
for j in range(width):
if (i, j) == start:
row.append("'S'")
elif (i, j) == end:
row.append("'E'")
else:
row.append(str(maze[i][j]))
# 각 요소를 콤마로 연결하여 한 행(row)을 문자열로 변환합니다.
row_str = ', '.join(row)
# 한 행(row)의 양끝에 대괄호를 추가합니다.
row_str = '[%s]' % row_str
# 마지막 행은 콤마를 붙이지 않습니다.
if i == height - 1:
print(row_str)
else:
print(row_str + ',')미로 그림 생성
import matplotlib.pyplot as plt
def draw_maze(maze_matrix):
rows, cols = len(maze_matrix), len(maze_matrix[0])
max_size = 10
fig_width = max_size * cols / max(rows, cols)
fig_height = max_size * rows / max(rows, cols)
plt.figure(figsize=(fig_width, fig_height))
for row in range(rows):
for col in range(cols):
if maze_matrix[row][col] == 1:
plt.fill_between([col, col+1], row, row+1, color='black')
elif maze_matrix[row][col] == 'S':
plt.fill_between([col, col+1], row, row+1, color='blue')
elif maze_matrix[row][col] == 'E':
plt.fill_between([col, col+1], row, row+1, color='red')
plt.xlim(0, cols)
plt.ylim(0, rows)
plt.gca().invert_yaxis()
plt.axis('off')
plt.show()
maze_matrix = [
# 미로 생성기에서 출력된 행렬 입력
]
draw_maze(maze_matrix)미로 그래프 만들기
import networkx as nx
import matplotlib.pyplot as plt
maze = [
# 미로 생성기에서 출력된 행렬 입력
]
# 그래프 생성
G = nx.Graph()
# 각 노드 추가
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] != 1:
if maze[i][j] == 'S':
G.add_node((i,j), color='blue')
elif maze[i][j] == 'E':
G.add_node((i,j), color='red')
else:
G.add_node((i,j), color='skyblue')
# 각 노드 사이의 연결 추가
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] != 1:
# 오른쪽 연결
if j < len(maze[i])-1 and maze[i][j+1] != 1:
G.add_edge((i,j), (i,j+1))
# 아래쪽 연결
if i < len(maze)-1 and maze[i+1][j] != 1:
G.add_edge((i,j), (i+1,j))
# 그림 크기 설정
fig = plt.figure(figsize=(10, 10))
# 그래프 그리기
pos = {n: (n[1], len(maze)-n[0]-1) for n in G.nodes()}
colors = [G.nodes[n]['color'] for n in G.nodes()]
nx.draw(G, pos, node_size=50, node_color=colors, with_labels=False)
plt.show()미로 그래프 단순화 하기
import networkx as nx
import matplotlib.pyplot as plt
maze = [
# 미로 생성기에서 출력된 행렬 입력
]
# 그래프 생성
G = nx.Graph()
# 각 노드 추가
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] != 1:
if maze[i][j] == 'S':
G.add_node((i,j), color='blue')
elif maze[i][j] == 'E':
G.add_node((i,j), color='green')
else:
G.add_node((i,j), color='skyblue')
# 각 노드 사이의 연결 추가
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] != 1:
# 오른쪽 연결
if j < len(maze[i])-1 and maze[i][j+1] != 1:
G.add_edge((i,j), (i,j+1))
# 아래쪽 연결
if i < len(maze)-1 and maze[i+1][j] != 1:
G.add_edge((i,j), (i+1,j))
# 차수가 2인 노드 찾기
nodes_to_remove = [n for n in G.nodes() if G.degree(n) == 2]
# 차수가 2인 노드 제거하고 선으로 연결
for node in nodes_to_remove:
neighbors = list(G.neighbors(node))
if len(neighbors) == 2:
G.add_edge(neighbors[0], neighbors[1])
G.remove_node(node)
# 출발점과 도착점 찾기
start = None
end = None
for n in G.nodes():
if G.nodes[n]['color'] == 'blue':
start = n
elif G.nodes[n]['color'] == 'green':
end = n
if start is not None and end is not None:
break
# 출발점에서 도착점까지의 최단 경로 찾기
shortest_path = nx.shortest_path(G, start, end)
# 최단 경로의 간선 목록 생성
shortest_path_edges = [(shortest_path[i], shortest_path[i+1]) for i in range(len(shortest_path)-1)]
# 그림 크기 설정
fig = plt.figure(figsize=(10, 10))
# 그래프 그리기
pos = {n: (n[1], len(maze) - n[0] - 1) for n in G.nodes()}
colors = [G.nodes[n]['color'] for n in G.nodes()]
nx.draw(G, pos, node_size=100, node_color=colors, with_labels=False)
# 최단 경로의 간선을 강조하기
nx.draw_networkx_edges(G, pos, edgelist=shortest_path_edges, edge_color='purple', width=4)
plt.show()미로 최종 (생성 + 그림 + 그래프 + 간소화)
import random
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import sys
sys.setrecursionlimit(10000) # 그래프가 생성되지 않으면 시도 횟수를 늘리세요
# 주의사항
# 1. 미로의 크기는 반드시 홀수여야 합니다
# 2. 행렬의 시작은 (0,0)부터 시작합니다
# 3. 따라서 마지막 행과 열은 미로의 크기에서 1을 뺀 값과 같습니다
# 4. 시작점은 가장자리에 위치합니다
# 미로의 크기, 출발점, 도착점을 입력합니다.
height, width = (51, 51)
start = (2, 0)
end = (height - 2, width - 1)
max_size = 10 # 출력되는 그림의 크기
# 미로 생성
def create_maze(height, width, start, end):
while True:
maze = np.ones((height, width), dtype=np.int8)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def is_valid(x, y):
return 0 <= x < height and 0 <= y < width and maze[x][y] == 1
def depth_first_search(x, y):
maze[x][y] = 0
random.shuffle(directions)
for dx, dy in directions:
nx, ny = x + 2 * dx, y + 2 * dy
if is_valid(nx, ny) and maze[nx][ny] == 1:
maze[nx][ny] = 0
maze[x + dx][y + dy] = 0
depth_first_search(nx, ny)
depth_first_search(1, 1)
# 미로의 외곽에 벽을 생성합니다.
maze[0, :] = 1
maze[-1, :] = 1
maze[:, 0] = 1
maze[:, -1] = 1
# 시작점과 도착점을 0으로 변경합니다.
maze[start[0], start[1]] = 0
maze[end[0], end[1]] = 0
if is_valid_maze(maze, start, end):
break
return maze, start, end
def is_valid_maze(maze, start, end):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
def is_valid(x, y):
return 0 <= x < height and 0 <= y < width
visited = set()
stack = [start]
while stack:
x, y = stack.pop()
visited.add((x, y))
if (x, y) == end:
return True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if is_valid(nx, ny) and maze[nx][ny] == 0 and (nx, ny) not in visited:
stack.append((nx, ny))
return False
maze, start, end = create_maze(height, width, start, end)
# 미로 그리기
def draw_maze(maze_matrix, start, end):
rows, cols = len(maze_matrix), len(maze_matrix[0])
fig_width = max_size * width / max(height, width)
fig_height = max_size * height / max(height, width)
plt.figure(figsize=(fig_width, fig_height))
for row in range(rows):
for col in range(cols):
if maze_matrix[row][col] == 1:
plt.fill_between([col, col+1], row, row+1, color='black')
elif (row, col) == start:
plt.fill_between([col, col+1], row, row+1, color='blue')
elif (row, col) == end:
plt.fill_between([col, col+1], row, row+1, color='red')
plt.xlim(0, cols)
plt.ylim(0, rows)
plt.gca().invert_yaxis()
plt.axis('off')
plt.title("Maze")
plt.show()
draw_maze(maze, start, end)
# 그래프 만들기
maze = maze.tolist()
for row in maze:
for idx, value in enumerate(row):
if value == 0:
row[idx] = ' '
maze[start[0]][start[1]] = 'S'
maze[end[0]][end[1]] = 'E'
G = nx.Graph()
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] != 1:
if maze[i][j] == 'S':
G.add_node((i,j), color='blue')
elif maze[i][j] == 'E':
G.add_node((i,j), color='red')
else:
G.add_node((i,j), color='skyblue')
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] != 1:
if j < len(maze[i])-1 and maze[i][j+1] != 1:
G.add_edge((i,j), (i,j+1))
if i < len(maze)-1 and maze[i+1][j] != 1:
G.add_edge((i,j), (i+1,j))
# 그래프 그리기
fig, ax = plt.subplots(figsize=(max_size, max_size))
pos = {n: (n[1], len(maze) - n[0] - 1) for n in G.nodes()}
colors = [G.nodes[n]['color'] for n in G.nodes()]
nx.draw(G, pos, node_size=30, node_color='skyblue', edge_color='black', width=1) # 그래프 그림 설정
plt.title("Maze Graph")
plt.show()
# 차수가 2인 노드를 제거하기
nodes_to_remove = [n for n in G.nodes() if G.degree(n) == 2]
for node in nodes_to_remove:
neighbors = list(G.neighbors(node))
if len(neighbors) == 2:
G.add_edge(neighbors[0], neighbors[1])
G.remove_node(node)
# 출발점과 도착점 찾기
start = None
end = None
for n in G.nodes():
if G.nodes[n]['color'] == 'blue':
start = n
elif G.nodes[n]['color'] == 'red':
end = n
if start is not None and end is not None:
break
shortest_path = nx.shortest_path(G, start, end)
shortest_path_edges = [(shortest_path[i], shortest_path[i+1]) for i in range(len(shortest_path)-1)]
for node in nodes_to_remove:
if G.has_node(node):
neighbors = list(G.neighbors(node))
if len(neighbors) == 2:
G.add_edge(neighbors[0], neighbors[1])
G.remove_node(node)
# 간소화된 그래프 그리기
fig, ax = plt.subplots(figsize=(max_size, max_size))
pos = {n: (n[1], len(maze) - n[0] - 1) for n in G.nodes()}
colors = [G.nodes[n]['color'] for n in G.nodes()]
nx.draw(G, pos, node_size=30, node_color='skyblue', edge_color='black', width=1) # 간소화 그래프 그림 설정
nx.draw_networkx_edges(G, pos, edgelist=shortest_path_edges, edge_color='purple', width=4)
plt.title("Simple Maze Graph")
plt.show()You know what's cooler than magic? Math.
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!
