April 11, 2024

에이스타 알고리즘(A*) 이해하기 C#,Python 예제코드 포함

에이스타 알고리즘 예제코드

안녕하세요, 오늘은 에이스타 알고리즘에 대해서 이야기 해보려고 합니다. 제가 Unity를 사용해서 게임 개발을 진행했을 당시 구현하는데에 어려움을 느꼈었던게 기억이 나서 여러분들께 쉽고 간단하게 소개해드리고 싶어서 준비해보았습니다. 자세히 함께 살펴보도록 하겠습니다.

우선 에이스타 알고리즘(A*)은 그래프 탐색과 경로 탐색 문제에서 사용되는 효율적인 알고리즘입니다. 이 알고리즘은 최선 우선 탐색(Best-First Search)의 한 형태로 현재 위치에서부터 목표까지의 최단 경로를 찾는 데 특히 유용합니다.

에이스타 알고리즘 동작 원리

시작 노드부터 목표 노드까지의 최단 경로를 찾기 위해 사용됩니다. 각 노드를 확장할 때, 알고리즘은 해당 노드까지의 실제 비용과 목표까지의 예상 비용을 고려합니다. 이를 통해 후보 경로 중에서 가장 유망한 경로를 선택하여 탐색을 진행하게 됩니다. 에이스타 알고리즘은 각 노드의 평가 지표 f(n) = g(n) + h(n) 값을 최소화하는 방향으로 탐색을 수행합니다.

에이스타 알고리즘 예제 코드

먼저 파이썬을 사용하여 에이스타 알고리즘을 구현한 간단한 예제 코드입니다.

def astar(graph, start, goal):
    open_set = {start}
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while open_set:
        current = min(open_set, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, current)

        open_set.remove(current)
        for neighbor in graph[current]:
            tentative_g_score = g_score[current] + graph[current][neighbor]
            if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                if neighbor not in open_set:
                    open_set.add(neighbor)
    return None

def heuristic(node, goal):
    # 예상 비용 함수
    pass

def reconstruct_path(came_from, current):
    # 최단 경로 재구성 함수
    pass

astar 함수는 그래프, 시작 노드, 목표 노드를 입력으로 받아 에이스타 알고리즘을 실행합니다.

heuristic 함수는 현재 노드에서 목표 노드까지의 예상 비용을 계산하는 함수입니다.

reconstruct_path 함수는 최단 경로를 재구성하는 함수입니다.

다음은 C#으로 작성한 알고리즘 예제코드를 설명해드리도록 하겠습니다.

using System;
using System.Collections.Generic;

public class AStar
{
    public static List<Node> FindPath(Dictionary<Node, Dictionary<Node, int>> graph, Node start, Node goal)
    {
        var openSet = new HashSet<Node> { start };
        var cameFrom = new Dictionary<Node, Node>();
        var gScore = new Dictionary<Node, int> { { start, 0 } };
        var fScore = new Dictionary<Node, int> { { start, Heuristic(start, goal) } };

        while (openSet.Count > 0)
        {
            var current = GetLowestFScoreNode(openSet, fScore);
            if (current == goal)
                return ReconstructPath(cameFrom, current);

            openSet.Remove(current);
            foreach (var neighbor in graph[current].Keys)
            {
                var tentativeGScore = gScore[current] + graph[current][neighbor];
                if (!gScore.ContainsKey(neighbor) || tentativeGScore < gScore[neighbor])
                {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeGScore;
                    fScore[neighbor] = tentativeGScore + Heuristic(neighbor, goal);
                    if (!openSet.Contains(neighbor))
                        openSet.Add(neighbor);
                }
            }
        }

        return null;
    }

    private static int Heuristic(Node node, Node goal)
    {
        // 예상 비용 함수
        return Math.Abs(node.X - goal.X) + Math.Abs(node.Y - goal.Y);
    }

    private static Node GetLowestFScoreNode(HashSet<Node> openSet, Dictionary<Node, int> fScore)
    {
        Node lowestNode = null;
        int lowestFScore = int.MaxValue;
        foreach (var node in openSet)
        {
            if (fScore.ContainsKey(node) && fScore[node] < lowestFScore)
            {
                lowestNode = node;
                lowestFScore = fScore[node];
            }
        }
        return lowestNode;
    }

    private static List<Node> ReconstructPath(Dictionary<Node, Node> cameFrom, Node current)
    {
        var path = new List<Node> { current };
        while (cameFrom.ContainsKey(current))
        {
            current = cameFrom[current];
            path.Insert(0, current);
        }
        return path;
    }
}

public class Node
{
    public int X { get; set; }
    public int Y { get; set; }

    public Node(int x, int y)
    {
        X = x;
        Y = y;
    }
}

class Program
{
    static void Main(string[] args)
    {
        // 그래프 초기화
        var graph = new Dictionary<Node, Dictionary<Node, int>>();
        // 그래프에 노드와 연결된 엣지 및 비용 추가
        // 예시: graph[node1] = new Dictionary<Node, int> { {node2, cost}, {node3, cost}, ... };
        
        // 시작 노드와 목표 노드 설정
        var start = new Node(0, 0);
        var goal = new Node(5, 5);

        // 최단 경로 찾기
        var path = AStar.FindPath(graph, start, goal);

        // 결과 출력
        if (path != null)
        {
            Console.WriteLine("최단 경로:");
            foreach (var node in path)
            {
                Console.WriteLine($"({node.X}, {node.Y})");
            }
        }
        else
        {
            Console.WriteLine("최단 경로를 찾을 수 없습니다.");
        }
    }
}

주어진 그래프에서 시작 노드와 목표 노드 간의 최단 경로를 찾습니다. 시작 노드와 목표 노드는 각각 Node 객체로 표현되며, 그래프는 Dictionary<Node, Dictionary<Node, int>>으로 표현됩니다. 알고리즘은 휴리스틱 함수 Heuristic를 사용하여 예상 비용을 계산하고, FindPath 메서드를 통해 최단 경로를 찾습니다.

에이스타 알고리즘의 장단점

에이스타 알고리즘은 많은 문제에서 효율적이고 신속한 최단 경로 탐색을 제공하지만, 예상 비용 함수의 품질에 따라 성능이 크게 달라집니다. 또한 알고리즘의 메모리와 계산 비용이 많이 들 수 있고 그래프의 크기와 예상 비용 함수의 정확성에 따라 성능이 달라질 수 있습니다.

어떤 분야에서 활용할 수 있을까 ?

에이스타 알고리즘은 다양한 분야에 응용됩니다. 주로 길 찾기, 로봇 경로 계획, 게임 개발 등에서 활용되며, 자율 주행 자동차의 경로 계획이나 실시간 게임에서 NPC의 움직임을 제어하는 데 사용됩니다. 또한 지리 정보 시스템(GIS)에서도 최적 경로 탐색에 활용됩니다.

오늘 내용이 여러분들에게 도움이 되었기를 바라며 포스팅을 마치도록 하겠습니다. 감사합니다 !

csharp