[알고리즘]#2_길 찾기 알고리즘

 

#1. 개념

 

1. 길 찾기 알고리즘

[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구성된 그래프에서 최단 경로 혹은 특정 조건을 만족하는(최소 신장 트리, etc) 경로를 찾는 데 사용됩니다. 다양한 종류의 길 찾기 알고리즘이 있으며, 알고리즘의 선택은 그래프의 크기, 가중치의 종류, 실행 시간 제약 등을 고려합니다. 따라서, 알고리즘의 특징과 제약 사항 등을 이해해야 주어진 문제에 가장 적합한 알고리즘을 선택할 수 있습니다.

[종류]
1. "단일 출발(single-source)" :  주어진 단일 노드 v로부터 다른 모든 노드 사이의 최단 경로를 찾는 문제 
2. "단일 쌍(single-pair)" : 주어진 노드 u와 v사이의 최단 경로를 찾는 문제입니다.
3. "전체 쌍(all-pair)" : 그래프 내 모든 노드 쌍들 사이의 최적의 경로를 찾는 문제입니다.

 

---

 

#2. BFS

 

1. 너비 우선 탐색

[자료구조]#6_그래프

너비 우선 탐색(BFS)은 그래프의 모든 노드를 탐색하는 방법 중 하나입니다.너비 우선 탐색은 현재 노드에서 가장 인접한 정점들을 먼저 탐색하는 방법입니다. 너비 우선 탐색은 선형 자료구조 중 큐를 활용하여, 정점의 방문여부를 체크하여 구현할 수 있습니다. 너비 우선 탐색은 가중치가 없는 그래프의 최단 경로 탐색을 위해 사용됩니다. 특히, 단일-쌍 최단 경로를 구하는 과정에서 그래프의 모든 간선들의 가중치가 없거나, 모두 동일할 경우에 사용됩니다!

 

2. 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Graph {
	vector<vector<int>> adjList;
};

vector<int> BFS(Graph& graph, int start, int end)
{
	int n = graph.adjList.size();

	vector<bool> visited(n, false);
	vector<int> parent(n, -1);
	queue<int> q;

	// #1. 큐에 출발 노드를 삽입합니다.
	visited[start] = true;
	q.push(start);

	while (!q.empty())
	{
		// #3. 큐의 첫 번째 항목 제거
		int cur = q.front();
		q.pop();

		// #4. 루프의 종료
		if (cur == end)
		{
			vector<int> v;
			while (cur != -1)
			{
				v.push_back(cur);
				cur = parent[cur];
			}
			reverse(v.begin(), v.end());
			return v;
		}

		// #5. BFS 정의
		for (auto adj : graph.adjList[cur])
		{
			if (!visited[adj])
			{
				visited[adj] = true;
				q.push(adj);
				parent[adj] = cur;
			}
		}
	}

	return {};
}

int main()
{

	int numNodes = 7;
	Graph graph;
	graph.adjList.resize(numNodes);

	graph.adjList[0] = { 1, 2 };
	graph.adjList[1] = { 0, 2, 3, 4 };
	graph.adjList[2] = { 0, 1, 4 };
	graph.adjList[3] = { 1, 4, 5 };
	graph.adjList[4] = { 1, 2, 3, 6 };
	graph.adjList[5] = { 3, 6 };
	graph.adjList[6] = { 4, 5 };

	int startNode = 0;
	int endNode = 6;

	vector<int> path = BFS(graph, startNode, endNode);

	if (path.empty()) {
		cout << "경로가 존재하지 않습니다.";
	}
	else {
		cout << "최단 경로: ";
		for (int node : path) {
			cout << node << " -> ";
		}
		cout << "도착지" << endl;
	}

	return 0;

}

 

---

 

#3. 다익스트라, 단일-출발

 

1.  개념

다익스트라 알고리즘은 일반적으로 양의 가중치를 갖는 그래프에서 최단 경로를 구하는 알고리즘입니다. 일반적으로, 다익스트라 알고리즘은 '단일-출발 최단 경로'를 구하는데 사용되며, 간선의 방향성 유무 + 우선순위 큐 + 최단 경로 목록을 기억해야합니다!

 

2. 동작 방식

1. C노드를 출발 노드로 설정합니다. 알고리즘이 진행되는 과정에서 모든 노드에 대해서 C노드로부터의 최단 경로를 측정해 나갑니다. 처음 시작 노드로 설정된 C노드의 "최단 경로 값/최소 가중치 값"은 '0'으로 설정하며, 그 외 다른 노드들은 모두 "무한대/아주 큰 수"로 시작합니다. 

2. 먼저 C를 방문합니다. 그리고, C와 연결된 다른 노드 사이의 가중치를 이용해 각 노드의 현재 최단 경로 값과 비교해 더 작은 값으로 수정합니다. 쉽게 말해, 각 노드가 기존에 갖고 있던 아주 큰 수(C로 시작해서 자기 자신에게 도달하는 최단 경로 값)와 C노드에서 시작해 본인에게 도달하기까지의 최단 경로 값을 비교해, 더 작은 값으로 본인의 최단 경로 값을 업데이트해 줍니다.

3. 이제 새롭게 방문할 노드를 선택합니다. 방문할 노드를 선택하는 기준은 아직 방문하지 않은 노드들 중 현재의 최단 경로 값이 가장 작은 노드를 선택하겠죠. 다음 방문할 노드는 A 노드입니다. 그리고, A와 연결되어 아직 방문하지 않은 노드(여기선 B 노드)의 최단 경로 값을 위와 같이 업데이트해 줍니다. 그리고, A노드도 방문 완료 노드로 체크합니다.

4. 이어서 차례대로 D 노드, 그리고 B 노드를 방문하여 위 과정들을 반복하고, 최종적으로 E노드에 방문하는 것으로 알고리즘을 종료합니다.

 

3. 성능

[자료구조]#7_우선순위 큐

 

[평균 시간 복잡도, O((|E| + |V|) log |V|)] : 우선순위 큐의 삽입/삭제의 시간 복잡도는 O(log V)입니다. (1) 다익스트라 알고리즘은 그래프의 각 노드를 한 번씩 우선순위 큐에 삽입합니다 - O(V log V). (2) 그리고, 각 노드마다 인접한 간선에 대한 검사를 수행합니다 - O(E). (3) 결과적으로, 우선순위 큐를 활용하는 다익스트라 알고리즘의 평균 시간 복잡도는 O((E+V) log V)입니다.

[최악 시간 복잡도, O(V² log V)] :  그래프가 완전 그래프일 경우 간선의 개수(E)는 ( V (V - 1) ) / 2입니다. 위 평균 시간 복잡도에서 E+v 부분은 ( V ( V - 1 ) / 2 ) * V로 대체되어 결국 최악 시간 복잡도는 O( V² log V )가 됩니다.

 

4. 코드(무방향 그래프, UG)

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// 그래프 자료구조의 총괄 구조체
struct Graph {
	vector<vector<int>> matrix;
	int NodeSize;
};

void Dijkstra(Graph* graph, int start)
{
	int n = graph->matrix.size();
	vector<int> distance(n, INT_MAX);
	vector<bool> visited(n, false);

	// #1. 출발 정점의 최단 경로 값 0으로 초기화
	distance[start] = 0;

	// #2. 우선 순위 큐 활용
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	pq.push({ 0, start });

	while (!pq.empty())
	{
		int cur_dist = pq.top().first;
		int cur_vertex = pq.top().second;

		pq.pop();

		// #3. 방문 여부 체크
		if (visited[cur_vertex])
			continue;

		visited[cur_vertex] = true;

		for (int next_vertex = 0; next_vertex < n; ++next_vertex)
		{
			int weight = graph->matrix[cur_vertex][next_vertex];
			if (weight == 0)
				continue;

			int new_dist = cur_dist + weight;

			// #4. 최단 경로 값 수정 여부
			if (new_dist <= distance[next_vertex])
			{
				distance[next_vertex] = new_dist;
				pq.push({ new_dist, next_vertex });
			}
		}
	}

	// 결과 출력
	for (int i = 0; i < n; i++) {
		cout << "Distance from start to vertex " << i << ": " << distance[i] << endl;
	}

}

 

5. 코드(유향 그래프, DG)

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int dest;
    int weight;
};

void Dijkstra(vector<vector<Edge>>& graph, int start) {
    int n = graph.size();
    vector<int> distance(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    distance[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int cur_vertex = pq.top().second;
        int cur_dist = pq.top().first;
        pq.pop();

        if (distance[cur_vertex] < cur_dist)
            continue;

        for (auto& edge : graph[cur_vertex]) {
            int next_vertex = edge.dest;
            int weight = edge.weight;
            int new_dist = cur_dist + weight;

            if (new_dist < distance[next_vertex]) {
                distance[next_vertex] = new_dist;
                pq.push({new_dist, next_vertex});
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << "Distance from start to vertex " << i << ": " << distance[i] << endl;
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> graph(n);

    for (int i = 0; i < m; i++) {
        int start, end, weight;
        cin >> start >> end >> weight;
        graph[start].push_back({end, weight});
    }

    Dijkstra(graph, 0);

    return 0;
}

 

Details

 

1. 먼저, 각 정점의 최단 경로 값을 'INT_MAX'로 초기화합니다. 그리고, 우선순위 큐는 pair <현재 최단 경로 값, 도착 정점> 형식의 최단 경로 값 기준 '최소 힙'을 구성해 줍니다.
2. 다음으로, 임의의 시작 정점의 방문 여부를 체크합니다.
3. 마지막으로, 해당 정점의 인접 정점 목록을 순회하며 각 인접 정점의 최단 경로 값을 경신하고, 인접 정점의 최단경로 값과 인접 정점을 pair 형식으로 묶어 우선순위 큐에 삽입합니다.
3. 위 과정을 반복하며, 최종적으로 시작 정점을 기준으로 다른 모든 노드의 최단 경로 값을 구합니다.

* 주의할 점 : '무향 그래프'는 모든 간선이 양방향으로 동작하므로, 어떤 노드에서 다른 노드로 이동한 후에도 이전 노드로 돌아가는 것이 비교적 쉽습니다. 따라서, 다익스트라 알고리즘 수행과정에서 해당 정점을 방문했다고 기록하여도 무방합니다. 반면, '유향 그래프'는 모든 간선에 방향성이 있으므로, 어떤 노드에서 다른 노드로 이동한 후에도 이전 노드로 돌아가는 것이 항상 가능한 것은 아닙니다. 따라서, 해당 정점을 방문했다고 기록할 경우, 해당 노드를 통한 다른 노드로 접근하는 가능성을 완전히 제거합니다. 따라서, 무향 그래프는 방문 여부를 체크하고, 유향 그래프는 해당 정점의 최소 거리 비용 갱신 여부를 확인합니다. 

 

4. 정리

 

---

 

#4. 벨만 포드, 단일-출발 or 단일-쌍

 

1. 개념

[정의] : 벨만-포드 알고리즘은 "음의 가중치"를 포함하는 그래프에서 '단일 출발 최단 경로'를 찾는 알고리즘입니다. 벨만-포드 알고리즘은 단일 출발뿐만 아니라 단일 쌍 최단 경로 알고리즘 모두 해결할 수 있는 최단 경로 알고리즘입니다.

[특징] : 벨만-포드 알고리즘의 "음의 가중치"에 대한 처리란, 그래프 내 사이클을 형성함과 동시에 해당 순환 경로에 존재하는 가중치들의 합이 음수인 "음수 사이클"을 탐지하는 보조적인 작업을 병행합니다. 벨만-포드 알고리즘이 모든 간선들을 순회하며 최단 경로 값을 업데이트하는 과정에서 "음수 사이클"의 존재는 최단 경로 값을 무한히 작은 수로 계속해서 업데이트시키는 오류를 발생시킵니다.

[성능] : 벨만-포드 알고리즘의 평균 시간 복잡도는 O(|E| x |V|), 상수 시간입니다. 우선, 벨만-포드 알고리즘은 모든 간선을 한 번씩 순회하며 최단 경로 값을 업데이트합니다. 벨만-포드 알고리즘의 최악 시간 복잡도는 O(|E| x |V|), 상수 시간입니다. 최악의 경우, 벨만-포드 알고리즘은 그래프 내 최단 경로가 V-1개, 즉  최단 경로가 가질 수 있는 최대 개수의 간선을 업데이트해야 할 경우 최악 시간 복잡도의 성능을 보여줍니다.

[다익스트라 vs 벨만-포드] : 벨만-포드 알고리즘은 다익스트라 알고리즘(O(E log V)보다 비효율적입니다. 하지만, 벨만-포드 알고리즘은 "음수 가중치"를 갖는 간선을 처리할 수 있어 "음수 사이클"을 탐지할 수 있는 보조 장치가 존재합니다. 따라서, "음수 가중치"를 포함한 그래프에서 최단 경로 알고리즘을 수행할 때 벨만-포드 알고리즘이 유용하게 사용됩니다.

[벨만-포드 vs 플로이드-워셜] : 벨만-포드(음수 가중치, 단일-쌍 혹은 단일-출발, N-1과 N번째, N번째 사이클 검사), 플로이드-워셜(음수 가중치, 전체-쌍, 3개의 For문, dist[i][i] 업데이트 여부 사이클 검사)

 

 

2. 동작 방식(N-1번과 N번)

0. 가장 먼저, 간선 목록을 구성합니다.

1. C노드를 출발 노드로 설정합니다. 처음 시작 노드로 설정된 C노드의 "최단 경로 값/최소 가중치 값"은 '0'으로 설정하며, 그 외 다른 노드들은 모두 "무한대/아주 큰 수(INF)"로 시작합니다.

2. 먼저, 그래프의 모든 간선을 순회합니다. 방문한 간선(, v)이 갖고 있는 기존의 최단 경로 값(distance [v])과 정점 u를 거쳐가는 경로 값이(distance [u] + weight(u, v)) 더 짧을 경우, 정점 v까지의 최단 경로 값(distance [v] = distance [u] + weight(u, v))을 새롭게 업데이트해줍니다. 핵심적인 내용은 해당 작업을 N-1번 반복하는 것입니다.

3. 다음으로, 위 작업을 N-1번 반복한 후에 N번째 작업은 그래프의 간선들을 한번 더 순회하며 "음수 사이클"의 존재 여부를 확인하는 작업입니다. 어떤 간선(u, v)에 대해 distance [u] + weight(u, v) 값이 distance [v] 값보다 작다면, 음의 가중치 순환이 존재하는 증명입니다!

 

3. 순환 여부(Cycle)

[BOJ알고리즘, C++]#11657_타임 머신, 길 찾기, 최단 경로 알고리즘, 벨만-포드, 음수 가중치, 음수 사

'벨만-포드' 알고리즘은 음수 가중치를 포함한 그래프에서 순환 여부를 감지합니다. '벨만-포드' 알고리즘은 'N-1' 번 간선 목록을 전체 순회하며, 주어진 출발 정점으로부터 다른 모든 정점까지의 최단 경로 값을 업데이트합니다. 이때, 마지막 N번 순회에서 어떤 정점이든 업데이트가 발생할 경우, 해당 그래프에 음수 사이클이 존재하는 것으로 판단할 수 있습니다!

 

4. 코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge
{
	int from, to, weight;
};

pair<vector<int>, bool> BellmanFord(int size, int start, const vector<Edge>& edges)
{
	// #1. 최단 경로 값 초기화
	vector<int> dist(size + 1, INT_MAX);
	dist[start] = 0;

	for (int i = 1; i <= size-1; i++)
	{
		for (const auto& edge : edges)
		{
			int u = edge.from;
			int v = edge.to;
			int weight = edge.weight;

			// #3. 최단 경로 값 업데이트
			if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
				dist[v] = dist[u] + weight;
		}
	}

	bool HasNegativeCycle = false;
	for (const auto& edge : edges)
	{
		int u = edge.from;
		int v = edge.to;
		int weight = edge.weight;

		// #4. 음수 사이클 여부 체크
		if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
		{
			HasNegativeCycle = true;
			break;
		}
	}
	
	return make_pair(dist, HasNegativeCycle);

}

int main()
{

	int n = 5, m = 6; 
	int s = 1; 

	vector<Edge> edges = {
		{1, 2, 10},
		{1, 3, 5},
		{2, 4, 1},
		{3, 4, 9},
		{3, 5, 2},
		{4, 5, 4}
	};

	auto result = BellmanFord(n, s, edges);

	vector<int> dist = result.first;
	bool has_negative_cycle = result.second;

	// 결과 출력
	if (has_negative_cycle)
	{
		cout << "The graph contains a negative weight cycle." << endl;
	}
	else
	{
		for (int i = 1; i <= n; ++i)
		{
			if (dist[i] == INT_MAX)
			{
				cout << "No path from " << s << " to " << i << endl;
			}
			else
			{
				cout << "Shortest path from " << s << " to " << i << " is: " << dist[i] << endl;
			}
		}
	}

	return 0;
}

 

---

 

#5. 플로이드 워셜, 전체-쌍

 

1. 개념

[정의] : 플로이드 워셜 알고리즘은 '음수 가중치'를 포함하는 가중치 그래프의 "전체-쌍 최단 경로"를 구하는 알고리즘입니다. 특히, '경유 정점'에 대한 개념이 강조될 경우 '플로이드-워셜' 알고리즘 활용 가능성이 높다고 볼 수 있습니다!

[특징] : 플로이드 워셜 알고리즘은 DP를 활용하여, 총 3번의 중첩 for문을 통해 각 정점의 최단 경로 값을 구합니다. 

[성능] : 플로이드 워셜 알고리즘의 평균/최악 시간 복잡도는 모두 O(n³)입니다.

 

2. 과정

1. 플로이드 워셜 알고리즘은 총 세 개의 중첩 반복문을 활용합니다. 먼저, 첫 번째 반복문은 "경유"하는 k 정점을 가리키는 반복문입니다.
2. 두 번째 반복문은 "출발"하는 u 정점을 가리키는 반복문입니다. 세 번째 반복문은 "도착"하는 v 정점을 가리키는 반복문입니다.
3. 최종적으로 Distance [u][v]가 Distance [u][k] + Distance [k][v] 보다 클 경우, Distance [u][v] 값을 Distance [u][k] + Distance [k][v] 값으로 최단 경로 값을 업데이트해 줍니다.  

 

3. 순환 여부(Cycle)

[BOJ알고리즘, C++]#1956_운동, 최단 경로, 플로이드, 플로이드 워셜

플로이드-워셜 알고리즘은 음수 가중치를 포함하는 그래프의 음수 사이클 여부를 감지합니다. '플로이드-워셜' 알고리즘은 3개의 중점 for문을 활용하여 "시작 정점 - 경유 정점 - 도착 정점"을 통해 최단 경로 값을 업데이트합니다. 이후, dist [i][i]와 같이 어느 한 정점에 대하여 자신을 출발 정점과 도착 정점으로 하는 최단 경로 값이 업데이트되었다면, 해당 그래프는 음수 사이클이 존재한다고 판단할 수 있습니다.

 

4. 코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Graph
{
	vector<vector<int>> adjMatrix;
	int NodeSize;
};

void Floyd(Graph& graph)
{
	int size = graph.NodeSize;
	// #1. DP 활용
	vector<vector<int>> DP(graph.adjMatrix);

	// #2. 첫 번째 반복문 : "경우"하는 정점 목록
	for (int k = 1; k <= size; k++)
	{
		// #3. 두 번째 반복문 : "출발"하는 정점 목록
		for (int u = 1; u <= size; u++)
		{
			// #4. 세 번째 반복분 : "도착"하는 정점 목록
			for (int v = 1; v <= size; v++)
			{
				// #5. DP + 최단 경로 업데이트
				if (DP[u][k] != INT_MAX && DP[k][v] != INT_MAX 
                && (DP[u][v] == INT_MAX || DP[u][v] > DP[u][k] + DP[k][v]))
					DP[u][v] = DP[u][k] + DP[k][v];
			}
		}
	}

	for (int i = 1; i <= size; i++) {
		for (int j = 1; j <= size; j++) {
			if (DP[i][j] == INT_MAX) cout << "INF ";
			else cout << DP[i][j] << " ";
		}
		cout << '\n';
	}

}

int main()
{

	int num = 4;
	Graph graph;
	graph.NodeSize = num;

	graph.adjMatrix.resize(num + 1, vector<int>(num + 1, INT_MAX));
	for (int i = 1; i <= graph.NodeSize; i++) graph.adjMatrix[i][i] = 0;

	graph.adjMatrix[1][2] = 8;
	graph.adjMatrix[1][3] = 10;
	graph.adjMatrix[2][4] = 5;
	graph.adjMatrix[3][2] = 4;
	graph.adjMatrix[3][4] = 3;

	Floyd(graph);

	return 0;

}

 

---

 

#6. A* 알고리즘 

 

1. 정의

F(n) = G(n) + H(n) // 전체 비용 = 현재 노드까지의 비용 + 현재 노드부터 도착 노드까지의 추정 비용

[정의] : A* 알고리즘은 전체-쌍 혹은 단일 출발 최단 경로 알고리즘이며, 다익스트라 알고리즘을 기반으로 휴리스틱 함수를 추가적으로 활용하는 최단 경로 알고리즘입니다.

[휴리스틱 함수] : 휴리스틱 알고리즘은 현재 노드와 도착 노드까지 예상되는 거리를 추정하는 데 사용됩니다. 이는 곧 노드 선택의 우선순위를 결정하는데 도움을 주며, 최적해에 가까운 다음 정점을 빠르게 찾아 알고리즘의 성능 향상에 도움을 줍니다.

[특징] : A* 알고리즘에서 n을 현재 노드라고 할 때, F(n)을 현재 노드를 포함하는 전체 비용을 의미하며, G(n)은 출발 노드로부터 현재 노드에 이르기까지의 실제 비용, 그리고 H(n)은 현재 노드로부터 도착 노드까지 예상되는 추정 비용을 의미합니다. 결과적으로, A* 알고리즘에서 우리는 F(n) 함숫값을 통해 단일-쌍 최단 경로 알고리즘 과정에서 현재노드(n)가 어느 정도 유망한 지를 평가하는 기준이 됩니다. 그리고, 인접한 노드들의 F(n) 값을 통해 그래프의 최단 경로 알고리즘에서 가장 최적해에 가까운 노드를 찾아 탐색 방향을 결정합니다.

 

2. 휴리스틱 함수

[정의] : 휴리스틱 함수는 문제 해결 과정에서 관측되지 않은 미래의 정보에 대한 예상 비용 또는 예상 거리를 추정하는 함수입니다. 따라서, 휴리스틱 함수는 경로 탐색 문제에서 다음 노드의 우선순위를 결정하거나, 최단 경로 알고리즘에서 다음으로 확장할 노드를 선택하는 데 사용됩니다.

 

3. 휴리스틱 함수의 조건

1. 적극성 : 휴리스틱 함수는 항상 목표 노드까지의 실제 비용보다 작거나 같은 값을 가져야 알고리즘의 최적성을 보장합니다. 왜냐하면, 휴리스틱 함수는 A* 알고리즘이 최적해를 찾을 수 있도록 보장해야 하기 때문입니다. 적극적인 휴리스틱은 실제 비용보다 큰 값을 추정하지 않으므로, 알고리즘이 탐색 과정에서 최적해보다 나쁜 경로를 선택할 가능성을 최소화할 수 있습니다.

2. 일관성 : 모든 노드 쌍에 대해, 두 노드 사이의 실제 비용은 휴리스틱 함수의 값보다 항상 크거나 같아야 합니다. 위와 같은 이유입니다. 결과적으로, 적극성을 만족하는 휴리스틱은 더불어 일관성 또한 만족합니다.

 

4. 동작 식(단일-쌍 기준)

[자료구조]#5_트리

1. 먼저, GScore(시작 노드로부터 현재 노드까지의 비용)과 HScore(현재 노드로부터 도착 노드까지의 추정 비용)를 저장할 데이터 목록이 필요합니다. 그리고, GScore+HScore 값을 기준으로 다음 정점 선택의 우선순위를 정하기 위해 우리는 우선순위 큐를 활용합니다. 마지막으로, 방문 여부를 체크하기 위한 데이터 목록 또한 필요합니다. 이때, 평가 비용(GScore + HScore)은 적을수록 노드 선택의 우선순위가 높아지며, 관련 값들을 저장하는 데이터 목록들은 모두 INT_MAX로 초기화해 줍니다.

2. 그래프의 너비 우선 탐색과 동일하게, start 정점의 GScore 값은 0으로, HScore 값은 heuristic(start, goal)으로 초기화해 주어 우선순위 큐에 삽입합니다.

3. 우선순위 큐에 대해 반복문을 수행합니다. 반복문 내에선 가장 우선순위가 높은, 즉 GScore+HScore 값이 가장 작은 정점을 꺼내 현재 노드로 설정합니다. 그리고, 현재 노드에 대한 평가을 포함하는 다음 과정은 다익스트라 알고리즘과 동일합니다. 

 

5. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std; 

struct Graph
{
	int NodeSize;
	vector<vector<int>> adjMatrix;
};

struct Node
{
	int Key, GScore, HScore;

	Node(int Key, int GScore, int HScore)
	{
		this->Key = Key;
		this->GScore = GScore;
		this->HScore = HScore;
	}

	bool operator>(const Node& Other)
	{
		return GScore + HScore > Other.GScore + Other.HScore;
	}
};


int Heuristic(int current, int goal)
{
	int dx = abs(current % 10 - goal % 10);
	int dy = abs(current / 10 - goal / 10);
	return dx + dy;
}

vector<int> AStar(const Graph& graph, int start, int goal)
{
	
	vector<bool> visited(graph.NodeSize, false);
	vector<int> parent(graph.NodeSize);
	vector<int> GScores(graph.NodeSize, INT_MAX);
	vector<int> HScores(graph.NodeSize, INT_MAX);

	priority_queue<Node, vector<Node>, greater<Node>> pq;

	for (int i = 0; i < graph.NodeSize; i++)
	{
		parent[i] = i;
	}

	GScores[start] = 0;
	HScores[start] = Heuristic(start, goal);
	pq.push({ start, GScores[start], HScores[start] });

	while (!pq.empty())
	{
		Node cur = pq.top();
		pq.pop();

		if (cur.Key == goal)
		{
			vector<int> v;

			int cur_Key = cur.Key;
			while (cur_Key != -1)
			{
				v.push_back(cur_Key);
				cur_Key = parent[cur_Key];
			}

			return v;
		}

		visited[cur.Key] = true;

		for (int neighbor = 0; neighbor < graph.NodeSize; neighbor++)
		{
			if (graph.adjMatrix[cur.Key][neighbor] != 0 && !visited[neighbor])
			{
				int new_neighborGScore = GScores[cur.Key] + graph.adjMatrix[cur.Key][neighbor];

				if (new_neighborGScore < GScores[neighbor])
				{
					parent[neighbor] = cur.Key;
					GScores[neighbor] = new_neighborGScore;
					HScores[neighbor] = Heuristic(neighbor, goal);

					pq.push({ neighbor, GScores[neighbor], HScores[neighbor] });
				}
			}
		}
	}

	return {};

}

 

---

 

#7. 내비게이션 메시

 

1. 개념

[정의] : 내비게이션 메시는 길 찾기 알고리즘에서 사용되는 고급 기술로, 이동 가능한 영역을 표현하고 이를 기반으로 길 찾기를 수행합니다. 내비게이션 메시는 2D 또는 3D 공간을 작은 메시들로 분할하여 이동 가능한 영역을 표현합니다. 이렇게 분할된 메시들은 네비게이션 그래프 형태로 구성되어 이동 가능한 경로를 찾아줍니다. 이때, 공간을 적절한 크기의 충분히 작은 영역으로 분할하는 과정은 메시 분할 알고리즘을 통해 진행하고, 메시들 간의 연결 정보를 효율적으로 저장하고 관리하는 작업은 네비게이션 그래프 자료구조를 활용합니다.네비게이션 메시는 복잡한 장애물과 다양한 지형을 고려하여 실시간으로 이동 가능한 경로를 계산할 수 있습니다. 정리하면, 네비게이션 메시는 메시 분할 알고리즘을 통해 3D공간을 충분히 작은 조각으로 분할하여 네비게이션 그래프를 구성하고, 이를 바탕으로 경로 탐색과 이동 가능한 영역 판단 등 다양한 네비게이션 기능을 제공합니다.

 

2. 메시 분할 알고리즘

메시 분할 알고리즘은 공간을 분할하는 방법을 결정합니다. 메시 분할은 컴퓨터 그래픽스와 게임 개발에서 사용되는 기법으로, 3D 공간을 작은 조각으로 분할하여 처리하는 방법입니다. 이를 통해, 복잡한 3D 모델이나 환경을 효율적으로 다룰 수 있습니다. 일반적으로, 메시 분할은 해당 공간을 격자 형태로 분할하여 관리하거나, 공간을 계층적으로 분할하는 방식 등 다양한 방법을 사용할 수 있습니다. 이때, 충분히 작게 분할한 공간들은 "메시 노드" 또는 타일로 표현되어, 그래프 자료구조의 정점에 해당됩니다. 

 

3. 네비게이션 그래프

내비게이션 그래프는 메시 분할 알고리즘을 통해 분할된 메시들을 통해 경로 탐색과 이동 가능한 영역을 판단합니다.메시 분할 알고리즘을 통해 충분히 작게 분할된 메시 노드들을 "정점"으로 두어 출발지와 목적지 사이의 최적 경로를 찾아냅니다. 이때, 이동 가능한 경로를 찾기 위해 네비게이션 그래프는 주로 "A* 알고리즘"등의 최단 경로 알고리즘을 활용합니다. 

 

---