소소한 일상 블로그

휴리스틱 길찾기 알고리즘의 대표 / 너비탐색과 다익스트라 알고리즘의 확장판 A* 알고리즘입니다.

포스팅 순서는 아래와 같습니다.

• A* 알고리즘
  • 개요
  • 장단점
  • 구현방법
  • 사용예시

A* 알고리즘

• 개요
  • 노드간의 가중치 뿐 아니라 휴리스틱 함수라는 추정값을 기반으로 최단거리를 탐색하는 알고리즘
  • 공식으로는 f (x) = g(x) + h(x)
    
    • g(x) - 시작노드 부터 현재 노드까지의 가중치 합
    • h(x) - 현재 노드부터 도착 노드까지의 예상 가중치
      • 일반적으로 가중치를 노드 간 거리라 했을 때 도착 노드까지의 대략적인 거리를 의미.
      • 이때 대략적인 거리를 구하는 방식에 따라 또 결과가 달라집니다.
    • 휴리스틱이란? 쉽게 말해 그냥 추정값이라고 보면 됩니다. (대략 이정도 하겠다~ 정도)
      • 그래서 휴리스틱 함수라 하면 추정값을 구하는 방법을 의미합니다. 추정이기 때문에 여러 방법이 있겠죠.
      • 예를 들면, 현재노드에서 목적지까지의 대략적인 거리를 구하는 방법으로 줄자로 제어진 거리, 수학 공식으로 대략적으로 구한 거리, 좌표상으로 구한 거리 등
  • 쉽게 말해 등산하면서 산 위의 정상을 보고 어림짐작으로 가깝겠다 싶은 갈림길을 선택해 가는 겁니다.
  • 결국 A*는 이 휴리스틱 함수에 좌지우지됩니다.
    • 상황에 맞는 적절한 휴리스틱 함수를 결정해야만 좋은 효과를 볼 수 있습니다.

• 장단점
  • 장점
    
    • 올바른 휴리스틱 함수를 사용하면 보다 빠른 최단거리 길찾기가 가능하다.
    • 주변환경 또는 추정값이 반영된 실질적 최단거리를 찾기 용이하다.
  • 단점
    
    • 휴리스틱 함수 의존도가 강하다.
    • 최단경로를 결정 이후, 환경에 변동이 있을 시 유연하게 반응하기 힘들다.
• 구현방법
  • 우선순위 큐 사용 ( 우선순위 정렬요소는 f / 오름차순)
    
    1. 1. 시작노드를 우선순위 큐에 넣는다.
    2. 2. 우선순위 큐에서 다음 노드를 꺼내 현재 노드로 설정한다. 현재 노드는 지나간 노드 (close list)로 설정한다.
    3. 3. 현재 노드의 주변 노드를 탐색한다.
       • close list에 포함된 노드라면 무시.
       • 만약 우선순위 큐(open list)에 포함되지 않은 노드라면 f(x)값을 구하고, 현재 노드를 주변 노드의 부모로 설정하고, 우선순위 큐에 등록한다.
       • 만약 주변 노드가 이미 open list에 등록되어 있다면, 자신보다 G값이 적은 노드가 있는지 확인하여 해당 노드를 현재노드의 부모노드로 바꾸고 f(x)를 재계산한다. (G값이 크다면 무시)
    4. 4. 목표에 도달할 때까지 2~3을 반복한다.
    5. 5. 목표를 찾으면 거꾸로 부모노드를 쫒아 역정렬하면 최단거리 경로가 된다.

• 사용예시
  • 게임 AI의 길찾기, 미로찾기 등 기본적인 길찾기로 많이 사용.

여담

 * A* 알고리즘은 예전에 공부하면서도 느꼈지만, 결국 휴리스틱 함수가 핵심인 듯합니다. 일반적인 예시로 휴리스틱 함수를 최종 도착지까지의 추정 가중치라고하는데, 네비게이션과 같은 변수가 많은 쪽을 예시로 들면, 최종 도착지까지의 실제적인 거리 예상치는 큰 의미가 없을 수 있을 거 같습니다. 그보다는 교통체중, 신호등 갯수, 속도 제한 등이 더 유용해지기도 할 거 같아요. 상황에 따라 노드간 가중치와 휴리스틱 함수를 적절하게 응용할 수 있어야 하지 않을까 싶습니다.

 * 다음은 A*에서 확장된 LPA* 알고리즘을 포스팅하겠습니다.

* 포스팅내에 잘못된 내용이나, 문의사항 있으시면 언제든 댓글로 지적해주시면 감사하겠습니다.

많은 탐색 / 길찾기 알고리즘의 기본이 되는 너비탐색과 깊이탐색입니다. 

특히 너비탐색의 경우에는 최단경로 길찾기의 기본적인 탐색 알고리즘입니다. 앞으로 진행할 길찾기 알고리즘 포스팅을 위해 먼저 정리할 목적으로 포스팅을 합니다.

너비탐색과 깊이탐색은 탐색 방법이고, 이를 통해 다양한 길찾기 알고리즘이 파생됩니다. (다익스트라, A* 등)

포스팅 순서는 아래와 같습니다.

1. 너비탐색
   • 개요
   • 장단점
   • 구현방법
   • 사용예시
2. 깊이탐색
   • 개요
   • 장단점
   • 구현방법
   • 사용예시

1. 너비탐색 (BFS)

• 개요
  • 시작 정점으로부터 인접한 거리순으로 주변으로 넓게 퍼지는 탐색
    • 종이에 먹물이 퍼지는 것과 같음.
• 장단점
  • 장점
    • 로직이 단순하다.
    • 최초 발견 루트를 최단경로라고 보장할 수 있다.
    • 언제나 같은 거리 결과값을 얻을 수 있다.
  • 단점
    • 비교적 많은 저장공간이 필요하다.
• 구현방법
  • 큐를 활용하여 구현 ( 선입선출 )
    • 1. 시작 노드를 현재 노드로 설정.
    • 2. 현재 노드를 탐색된 노드로 저장.
    • 3. 현재 노드의 주변 노드 중 탐색되지 않은 노드를 탐색
    • 4. 3번의 노드를 큐에 저장. / 탐색된 노드로 저장.
    • 5. 현재 노드의 주변 노드가 모두 탐색된 노드가 될 때까지 3~4 반복
    • 6. 큐에서 다음 노드를 꺼내 현재 노드로 설정. 
    • 7. 목표에 도착할 때까지 5~6 반복. (전체탐색의 경우, 큐가 빌 때까지 진행.)
• 예시
  • 최단경로 판별에 유용
  • 길찾기의 기본으로 유용

2. 깊이탐색 (DFS)

• 개요
• 시작 정점으로부터 각 분기 / 방향 별로 깊게(완전하게) 탐색하고 다음 분기 / 방향으로 넘어가는 탐색
  • 미로찾기와 같음.
• 장단점
• 장점
  • 로직이 단순하다.
  • 비교적 적은 저장공간
• 단점
  • 최초로 구해지는 길이 최단이라는 보장을 할 수 없다.
    • 최단경로 길찾기에 적합하지 않음.
  • 적절한 제한을 두지 않는다면 한쪽 분기에 과도하게 깊이 빠질 수 있음.
    • 재귀함수의 경우 stack overflow 우려 (깊이 제한 필요)
  • 탐색하는 방향 우선순위에 따라 결과가 다르게 나올 수 있다.
• 구현방법
• 스택 또는 재귀함수로 구현 (후입선출) 
  • 1. 시작 노드를 현재 노드로 설정.
  • 2. 현재 노드를 탐색된 노드로 저장.
  • 3. 현재 노드의 주변 노드 중 탐색되지 않은 노드 탐색 
  • 4. 3번의 노드를 스택에 저장 / 탐색된 노드로 저장.
  • 5. 현재 노드의 주변노드가 모두 탐색될 때까지 3~4 반복
  • 6. 스택에서 다음 노드 (최근에 들어간) 를 꺼내 현재 노드로 설정.
  • 7. 목표에 도착 또는 전체 순회를 할 때까지 5~6 반복. (전체 탐색의 경우 스택이 빌 때까지 진행)

• 예시
  • 자동 미로 생성기

여담

• 너비탐색과 깊이탐색의 구현방법의 차이는 사실상 큐와 스택입니다. 그 외 돌아가는 기본 로직은 비슷합니다. 
• 앞으로 4~5 포스팅 동안 길찾기 알고리즘을 시리즈로 할 생각입니다. 최종적으로는 D* lite 알고리즘까지 가는 것이 목표이며, 이를 위해 하나씩 과정을 밟아갈 예정입니다.
  • 하여 이후 길찾기 알고리즘의 순서는 A*, LPA*, D* lite 알고리즘 순으로 포스팅 할 예정입니다.

* 포스팅내에 잘못된 내용이나, 문의사항 있으시면 언제든 댓글로 지적해주시면 감사하겠습니다.

제목에는 정렬계의 노답 삼형제라고 적었지만, 다 쓸모가 있기에 존재하겠죠... (라고 말했지만 노답 삼형제 맞는거 같은데, 쓰기 쉽단거 빼면...)

1. 버블 정렬

정렬되는게 거품이 보글보글 올라오는 것과 같아서 버블 정렬이라고 합니다. 정렬해라 했을 때 가장 직관적으로 생각하기 쉬운 알고리즘이죠. 쉬운만큼 비효율적이기도 하고요.

 동작방식은 집합 내의 이웃 요소들끼리 비교하여 교환을 통해 정렬됩니다. 쉽게 말해 키순으로 정렬했을 때 내 앞에 있는 애가 나보다 키가 작으면 자리를 바꿔가며 키가 가장 큰 애를 맨 앞까지 오게 하는 거죠.

동작 예시 :

 백마디 말보다 예를 들어 보죠.

 자 밑에 3,2,4,1 의 정렬되지 않은 숫자가 있습니다.

버블정렬을 통해 오름차순으로 정렬해보죠. (뒤에 나올 정렬들도 동일한 수로 하겠습니다.)

빨간 네모는 비교를 의미합니다.

[1싸이클]

3을 기준으로 이웃한 2와 비교하여 3이 더 크므로 교환.

3을 기준으로 이웃한 4와 비교하여 4가 더 크므로 교환되지 않습니다.

1싸이클의 마지막으로 4와 이웃한 1을 비교하여 맨 마지막 요소에 4가 확정됩니다.

1싸이클을 통해 마지막은 4가 확정됬으므로 다음 싸이클부터는 4는 제외해도 되겠네요.

[2싸이클]

이미 이웃한 3이 더 크므로 교환하지 않습니다.

3이 이웃한 1보다 크므로 교환.

2싸이믈을 마지막을 확정된 3 역시 이후 부터는 제외됩니다.

[3싸이클]

마지막으로 2와 1을 비교하여 정렬을 마무리합니다.

총 3싸이클이 돌고, 비교연산은 6번, 교환은 4번 있었네요. 

최악의 경우 즉, 만약 역으로 정렬되어있었다면, 비교는 언제나 6번이고, 교환은 비교연산 할 때마다 일어나겠죠 (6번)

장점 : 

만들기 쉽다...

단점 :

비교 연산도 교환 연산도 많다.

시간복잡도 : O(n^2)

활용:

언제나 중요한 건 "그래서 이걸 어따 써먹을수 있는데?" 라고 생각합니다. 이게 곧 배우는 이유니까요.

 버블 정렬은 비효율의 대명사죠...

실제로 대학교에서 버블정렬을 접할 때, 이걸 배우는 이유는 비효율을 알아야 효율을 알 수 있기때문에 배우는거라고도 교수님이 그러셨죠.

2. 선택 정렬

 선택 정렬은 정렬되지 않은 집합 내 요소 중 가장 크거나 작은 것을 선택해 차례로 맨 앞이나 뒤로 보내 정렬하는 알고리즘입니다.

  쉽게 생각해서 포커나 고스톱을 칠 때, 카드를 다 받고나면 뒤죽박죽 섞여있잖아요. 그 때 카드들을 작은 것부터 뽑아서 앞으로 옮기면서 보기 좋게 바꾸죠. (버블 정렬처럼 옆으로 차례차례 옮기진 안잖아요?) 그런 방식을 생각하면 됩니다.

동작 예시:

빨간 네모는 최소값으로 선택된 요소입니다.

[1싸이클]

각 요소들의 최소값을 판별하면 1이 최소값인걸 알 수 있죠.

선택된 최소값인 1을 맨 앞으로 이동시킵니다.

[2싸이클]

[3싸이클]

3싸이클에 비교연산은 총 6번, 교환은 2번 일어났네요.

최악의 경우엔, 비교는 동일하고 (매번 동일하겠죠), 교환은 3번 일어날겁니다.

장점 :

버블에 비해 교환 연산이 적다. (최대 n번)

단점 :

안정성을 보장하지 않는다.

(같은 값이 있을 때 상대적으로 같은 위치에 있을거라 보장하지 못한다. 즉 정렬 후에는 순서가 뒤바껴 있을 수 있다.)

비교연산이 많다. (매번 최소값을 구해야하므로)

위와 같은 이유로 집합이 클수록 속도가 크게 느려진다.

시간복잡도 : O(n^2)

활용:

집합이 작은 정렬  + 안정성이 보장될 필요 없는 경우 

3. 삽입 정렬

 삽입 정렬은 정렬이 필요한 요소를 뽑아 적당한 곳에 삽입하는 정렬입니다. 적당히라는 말이 들어가있네요. 가장 어려운 말이죠.... 좀 더 풀어 설명하죠. 정렬되지 않은 요소를 순서대로 뽑아 이미 정렬되어 있는 집합 내 올바른 위치에 삽입하는 정렬입니다. 그렇기 때문에 우선 맨 앞의 요소를 정렬된 집합으로 취급하여 두 번째 요소부터 비교가 진행되죠. 

 바닥에 흩어진 트럼프 카드를 주우며 정렬하고자 할 때, 이 방법이 쓰이겠네요. 한 장씩 주우면서 이미 정렬되어 내 손에 쥐어진 카드에 올바른 위치에 넣는 식으로 정렬을 하겠죠.

동작 예시:

빨간 네모는 비교대상

빨간 선은 비교입니다.

[1싸이클]

3은 이미 정렬된 집합으로 판단하고, 두 번째 요소인 2와 비교해 정렬된 집합 내에 맨 앞으로 이동됩니다.

[2싸이클]

4를 이미 정렬된 집합의 맨 마지막과 먼저 비교하여 4보다 큰 수가 없으므로 맨 뒤에 정렬됩니다.  

[3싸이클]

1을 이미 정렬된 집합의 맨 앞의 2와 비교했을 때. 1일 작으므로 바로 맨 앞으로 이동시킨다.

이로써 싸이클 종료.

3싸이클에 비교연산은 총 3번, 교환은 2번 일어났네요.

최악의 경우엔? 4,1,2,3가 될거 같네요. 비교 6번에 교환은 3번 일어납니다.

장점 :

교환 연산이 비교적 적다. (최대 n번)

이미 일부 정렬된 상태라면 비교연산이 줄어 속도가 빠르다.

단점 :

정렬상태에 따라 속도가 민감하다.

시간복잡도 : O(n^2)

활용:

이미 일정부분 정렬되어 있는 집합.

정렬된 요소에 새 요소의 추가가 빈번할 때.

*항상 선택정렬하고, 삽입정렬하고 헷갈린다... 선택정렬은 최소값이나 최대값을 선택하여 정렬하고, 삽입정렬은 앞에서부터 순서대로 삽입하면서 정렬한다라고는 생각하지만... 아마 한 달 뒤면 또 헷갈리겠지... (삽입과 선택이라는 단어가 바꾸고자 하면 충분히 바꿀 수가 있는지라....)