2021-01-13

에이스타(A*)

코드를 구현하면서 느낀 것은 BFS와 다익스트라를 섞어 놓은 느낌을 받았다. 실제 코드를 봐도 두 방법의 흔적이 많이 보인다.
written by

BFS와 다익스트라를 섞은 검색 방법

코드를 구현하면서 느낀 것은 BFS와 다익스트라를 섞어 놓은 느낌을 받았다. 실제 코드를 봐도 두 방법의 흔적이 많이 보인다.

BFS의 큐를 이용한 탐색과, 다익스트라의 우선순위 큐를 이용하여 매 시점의 최단 거리 순으로 방문하면서 값을 갱신하는 방식이 혼용되어 있다.

다익스트라는 모든 노드를 방문해야 결과를 알 수 있다. 다익스타라가 모든 지점을 방문해야 하는 이유는 매 시점에 목적지까지의 거리를 알 수 없기 때문이다. 패를 다 까보기 전에는 알 수가 없는 것이다.

반면 에이스타는 시작 지점과 목적지를 이용한 가중치를 이용해서 필요한 경로만 탐색할 수 있다. 매 시점에 목적지까지의 거리에 관한 정보가 제공되므로 모든 노드를 탐색할 필요가 없는 것이다. 가중치는 추정치이므로 최단 경로를 보장하는 것은 아니지만 최단 경로에 근접한 값을 제공하면서 매우 빠른 탐색 속도를 보여준다는 것에 의의가 있다.

Kotlin Code

import java.util.*
import kotlin.math.abs

// 1. List: 완전 불변, 추가X/수정X
// 2. Array: 조건부 가변, 추가X/수정O
// 3. MutableList: 완전 가변, 추가O/수정O
// + 초기값 선언: listOf(value, value2, ...) }
// + 초기값 선언식: List(size) { index -> expression }
// + mutableListOf<T>()로 선언문만으로 초기화 가능
// + 나머지는 반드시 초기값이 필요

// 0이면 통로, 1이면 벽으로 간주하는 맵.
// 가로는 열(col), 세로는 행(row), map[row][col]로 위치 표시.
val map = arrayOf(
    intArrayOf(0, 1, 0, 0, 1, 0),
    intArrayOf(0, 0, 0, 1, 0, 1),
    intArrayOf(0, 1, 0, 0, 0, 0),
    intArrayOf(1, 0, 0, 1, 0, 1),
    intArrayOf(1, 0, 0, 1, 0, 0),
)

// 해당 map 위치의 방문 여부를 의미한다.
// A* 알고리즘의 클로즈드 리스트에 해당한다.
val visit = arrayOf(
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
)

// 해당 map 위치의 가중치를 저장하는 이차원 배열.
// dijkstra 알고리즘과 유사하게, 최초에는 무한대의 값으로 저장하여 무조건 갱신하도록 한다.
// 가중치의 계산법은 현재 위치의 g 값과 현재 위치에서 다음 위치까지의 거리인 g 값을 더하고, 다음 위치에서 목적지까지의 거리인 h 값을 더한다.
// g 값은 수직과 수평에 대해서는 1, 대각선에 대해서는 1.4로 계산한다. 계산하기 편하도록 각각의 거리에 10씩 곱하도록 하자.
// 시작 위치는 g 값이 없으므로 h 값만 계산한다.
// 시작 위치가 [0, 0]이고 목적지가 [4, 5]라면 목적지까지의 거리는 9, 따라서 시작 위치의 가중치는 (4 + 5) * 10 = 90.
// 시작 위치에서 아래에 해당하는 [1, 0]인 위치의 가중치는 수직으로 한 칸 이동하므로 g 값은 10, h 값은 (4 + 4) * 10으로 가중치는 90.
// 시작 위치에서 대각선에 해당하는 [1, 1]인 위치의 가중치는 대각선으로 한 칸 이동하므로 g 값은 14, h 값은 (4 + 3) * 10으로 가중치는 84.
// [1, 1]에서 대각선에 해당하는 [2, 2]인 위치의 가중치는 대각선으로 한 칸 이동하므로 g 값은 14, [1, 1]의 g 값은 14, h 값은 (3 + 2) * 10으로 가중치는 78.
// 현재 위치가 변경되면 g 값은 변경될 수 있으므로 가중치가 변경되면 가중치는 갱신해 줘야 한다.
// 가중치가 커지는 경우라면 굳이 먼 길을 확인할 필요는 없으므로, 짧아지는 경우에만 갱신하고 우선순위 탐색 큐에 삽입하도록 한다.
val heuristic = arrayOf(
    intArrayOf(Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE),
    intArrayOf(Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE),
    intArrayOf(Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE),
    intArrayOf(Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE),
    intArrayOf(Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE, Int.MAX_VALUE),
)

// map 시작 지점 및 현재 위치와 도착 지점.
val currentPosition = intArrayOf(0, 0)
val goalPosition = intArrayOf(4, 5)

// 0시 방향으로부터 시계 방향으로 회전하면서 방문하기 위한 방향.
val directions = listOf(
    Pair(-1, 0),
    Pair(-1, 1),
    Pair(0, -1),
    Pair(0, 1),
    Pair(1, 1),
    Pair(1, 0),
    Pair(1, -1),
    Pair(-1, -1),
)

// A* 방문을 위한 우선순위 탐색 큐.
// A* 알고리즘의 오픈 리스트에 해당한다.
// 우선순위는 heuristic 값으로 판별한다.
// 시작점의 가중치는 목적지까지의 거리만 계산한다.
// 가중치가 설정된 시작점을 우선순위 탐색 큐에 삽입한다.
val aStarQueue = PriorityQueue<Triple<Int, Int, Int>>(compareBy { it.third }).apply {
    heuristic[currentPosition[0]][currentPosition[1]] = ((abs(currentPosition[0] - goalPosition[0]) + abs(currentPosition[1] - goalPosition[1])) * 10)
    add(Triple(currentPosition[0], currentPosition[1], heuristic[currentPosition[0]][currentPosition[1]]))
}

// 도착 지점에 도착할 때까지 탐색한다.
// 우선순위 탐색 큐가 다 비어도 도착 지점을 찾지 못하면, 경로가 없다.
while (aStarQueue.isNotEmpty()) {

    // 우선순위 탐색 큐에서 탐색 중인 위치를 현재 위치로 저장한다.
    // 방문한 곳은 클로즈드 리스트에 삽입하는데, 여기서는 visit[a][b] = true.
    currentPosition[0] = aStarQueue.element().first
    currentPosition[1] = aStarQueue.element().second
    visit[currentPosition[0]][currentPosition[1]] = true

    // 맵을 출력한다.
    printMap(map, currentPosition)

    // 우선순위 탐색 큐에서 제거하여 탐색을 진행.
    aStarQueue.poll()

    // 현재 위치가 목적지라면 탐색을 종료.
    if (currentPosition.contentEquals(goalPosition)) {
        break
    }

    // 아니라면 모든 방향으로 방문이 가능한지 판별해서 오픈 리스트에 넣어준다.
    // 우선순위 큐에 따라 가중치가 작은 곳을 우선으로 방문하도록 한다.
    directions.forEach { direction ->

        // 다음으로 이동할 row, col
        val movePositionRow = currentPosition[0] + direction.first
        val movePositionCol = currentPosition[1] + direction.second

        // 다음으로 이동할 위치가 맵을 벗어나지 않는지 확인한다.
        if (movePositionRow >= 0 && movePositionRow < map.size && movePositionCol >= 0 && movePositionCol < map[0].size) {

            // 다음으로 이동할 위치가 벽이 아니고, 클로즈드 리스트에 있는지 확인한 후에,
            // 해당 위치의 가중치가 갱신이 가능한 상태라면, 가중치를 갱신하면서 우선순위 탐색 큐에 삽입.
            if (map[movePositionRow][movePositionCol] == 0 && !visit[movePositionRow][movePositionCol]) {
                if (heuristic[movePositionRow][movePositionCol] >= getHeuristicPoint(intArrayOf(movePositionRow, movePositionCol))) {
                    heuristic[movePositionRow][movePositionCol] = getHeuristicPoint(intArrayOf(movePositionRow, movePositionCol))
                    aStarQueue.add(Triple(movePositionRow, movePositionCol, heuristic[movePositionRow][movePositionCol]))
                }
            }
        }
    }
}

// 가중치를 계산하는 함수.
// 이전의 가중치에서 h 값만 뺀 후에, 새로 g 값과 h 값을 계산해서 넣는 방식으로 간단하게 구현함.
// 효율적으로 하기 위해서는 g 값과 h 값을 따로 저장하는 것이 좋다.
// 여기서는 가중치를 하나의 값으로 저장하기 위해서 그냥 조금 더 계산하도록 하였음.
fun getHeuristicPoint(targetPosition: IntArray): Int =
    (heuristic[currentPosition[0]][currentPosition[1]]) +
    (if ((currentPosition[0] - targetPosition[0]) != 0 && (currentPosition[1] - targetPosition[1]) != 0) 14 else 10) +
    ((abs(targetPosition[0] - goalPosition[0]) + abs(targetPosition[1] - goalPosition[1])) * 10) -
    ((abs(currentPosition[0] - goalPosition[0]) + abs(currentPosition[1] - goalPosition[1])) * 10)

// 맵을 문자로 표현하여 출력하는 함수.
// 벽은 X, 통로는 빈 문자, 현재 위치는 *로 표시한다.
fun printMap(map: Array<IntArray>, currentPosition: IntArray) {
    Array(map.size) { i ->
        Array(map[i].size) { j ->
            when {
                map[i][j] == 0 -> "[ ]"
                else -> "[X]"
            }
        }
    }.apply {
        this[currentPosition[0]][currentPosition[1]] = "[*]"
    }.run {
        println("--------------------")
        forEach { eachRow ->
            eachRow.forEach { eachCell ->
                print(eachCell)
            }.run { println("") }
        }
        println("--------------------")
    }
}

Result

--------------------
[*][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][*][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][*][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][*][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][*][X]
[X][ ][ ][X][ ][ ]
--------------------
--------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][*]
--------------------
2021 © Cinntiq's Studio