최적 경로 찾기 #2 - 에이스타(A*) 알고리즘, 자바 코드 구현 포함

에이스타(A*) 알고리즘

에이스타 알고리즘은 순서대로 정점을 검사하는 수학적 접근 방식과 특정 정보를 활용하여 계산 효율성을 향상하는 휴리스틱 접근 방식을 사용하여 비용을 계산하는 알고리즘이다. 경로 탐색 중 후보 정점을 조회할 때 간선의 가중치뿐만 아니라 정점의 휴리스틱 정보를 통해 방문할 다음 정점을 결정하므로 간선의 가중치만을 고려하는 기존의 다른 알고리즘보다 적은 수의 정점을 탐색한다. 따라서 저장공간과 수행 시간이 타 알고리즘보다 적게 기대되나 휴리스틱 정보를 참고하므로 항상 최단 경로를 보장하지는 않는다. 

에이스타 알고리즘은 간선의 가중치와 휴리스틱 기대값을 통해 방문할 다음 정점의 순서를 결정하기 때문에 목적지까지의 연산이 비교적 빨리 끝날 가능성이 있으나 휴리스틱 기대값에 큰 영향을 받기 때문에 휴리스틱 값이 굉장히 중요하다.

 

에이스타 알고리즘에서 비용을 계산하는 함수 수식은 다음과 같다. f(n) = g(n) + h(n) 

g는 시작노드에서 현재 n번째 노드까지의 경로 비용이며 

h는 n번째 노드에서 목표 노드까지의 경로 비용(휴리스틱 기대값)이다.

 

A* 알고리즘 의사코드

 

기본 개념

 

1. 시작 정점(v) 선택

2. 시작 정점과 인접한 정점(1세대) 수집

3. 인접한 정점(1세대)의 g, h, f 계산 후 방문 리스트에 등록

4. 방문 리스트를 f를 기준으로 값이 작은 순서대로 정렬

5. 인접한 정점(1세대)의 인접한 정점(2세대) 수집

6. 인접한 정점(1세대)의 g, h, f 계산 후 방문 리스트에 등록

7. 방문 리스트를 f를 기준으로 값이 작은 순서대로 정렬

8. 목적지에 도착할 때 까지 위의 과정 순회

 

코드 구현

public class SampleCode {

    private static final int[][] coordinate = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; //{-1, -1}, {-1, 1}, {1, -1}, {1, 1}

    private int n, m = 0; //최대 x, y 좌표
    private final Queue<SampleCode.Node> queue = new PriorityQueue<>();
    private final char[][] map;

    private final List<Node> open_list = new ArrayList<>();
    private final List<Node> closed_list = new ArrayList<>();

    public SampleCode2(char[][] map){
        this.map = map;
        this.n = map.length;
        this.m = map[0].length;
    }

    public void astar(int start_x, int start_y, int end_x, int end_y){

        Node start_node = new Node(start_x, start_y);
        start_node.setHeuristics(0, 0);

        open_list.add(start_node);

        while (!open_list.isEmpty()) {

            
            Node current_node = open_list.get(0);
            int current_index = 0;

            for (int i = 0; i < open_list.size(); i++) {
                if (open_list.get(i).F < current_node.F) {
                    current_node = open_list.get(i);
                    current_index = i;
                }
            }

            // 방문 완료 리스트에 추가
            open_list.remove(current_index);
            closed_list.add(current_node);

            // 목적지에 도착했을 때
            if(current_node.x == end_x && current_node.y == end_y){
                Node current = current_node;
                while(current != null){
                    if(map[current.x][current.y] == '0'){
                        map[current.x][current.y] = '*';
                        current = current.parent;
                    }
                }
                print();
                return;
            }

            List<Node> children = new ArrayList<>();
            //********인접 정점 수집 영역*************/
            for (int[] new_position : coordinate) {
                int[] node_position = {current_node.x + new_position[0], current_node.y + new_position[1]};

                //유효 범위를 이탈했으면 스킵
                if (node_position[0] < 0|| node_position[0] >= n || node_position[1] < 0 || node_position[1] >= m) {
                    continue;
                }

                //진행 불가능한 구역이면 스킵
                if(map[node_position[0]][node_position[1]] == '1'){
                    continue;
                }

                Node new_node = new Node(current_node, node_position);
                children.add(new_node);

                for(Node child : children){

                    // 탐색이 끝난 노드인지 확인
                    for(Node c2 : closed_list){
                        if(child == c2){
                            continue;
                        }
                    }

                    // G, H, F 값 생성
                    child.G = current_node.G + 1;
                    child.H = (int) (Math.pow(child.x - end_x, 2) + Math.pow(child.y - end_y, 2));
                    child.F = child.G + child.H;

                    for(Node node : open_list){
                        if(child == node){
                            if(child.G > node.G){
                                continue;
                            }
                        }
                    }

                    open_list.add(child);

                }
            }
        }
    }

    public void print(){
        for(char[] row: map){
            for (char col : row) {
                System.out.print(col + " ");
            }
            System.out.println();
        }
    }

    static class Node implements Comparable<Node> {

        private Node parent;
        private int x;
        private int y;

        private int G;
        private int H;
        private int F;

        public Node(Node parent, int[] coord) {
            this.parent = parent;
            this.x = coord[0];
            this.y = coord[1];
        }

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public void setHeuristics(int G, int H){
            this.G = G;
            this.H = H;
            this.F = G+H;
        }


        @Override
        public int compareTo(Node o) {
            if(F == o.F){
                return H > o.H ? 1 : -1;
            }else{
                return F > o.F ? 1 : -1;
            }
        }
    }

    public static void main(String[] args) {
        char[][] map =   {{'0', '0', '1', '0', '0', '0', '0', '0', '0', '0'}
                        , {'0', '0', '1', '0', '0', '0', '0', '0', '0', '0'}
                        , {'0', '0', '1', '0', '0', '0', '0', '0', '0', '0'}
                        , {'0', '0', '1', '0', '0', '1', '1', '1', '1', '1'}
                        , {'0', '0', '1', '0', '0', '1', '0', '0', '0', '0'}
                        , {'0', '0', '1', '0', '0', '0', '0', '1', '0', '0'}
                        , {'0', '0', '1', '0', '0', '0', '0', '1', '0', '0'}
                        , {'0', '0', '0', '0', '1', '0', '0', '1', '0', '0'}
                        , {'0', '0', '0', '0', '1', '0', '0', '0', '0', '0'}
                        , {'0', '0', '0', '0', '1', '0', '0', '0', '0', '0'}};

        SampleCode sample = new SampleCode(map);
        sample.astar(1, 1, 8, 8);
    }
}

 

 

Reference.

이창규. "대피경로 도출을 위한 최적 네트워크 구조 및 알고리즘 선정 연구." 국내석사학위논문 경희대학교 대학원, 2021. 서울

chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://mat.uab.cat/~alseda/MasterOpt/AStar-Algorithm.pdf

https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2