알고리즘/Path Finding

SMA* 알고리즘 - 메모리를 고려한 A* 알고리즘의 변형이 또 있네요!

Jㅐ둥이 2023. 4. 14. 07:53
반응형

안녕하세요. 오늘은 A* 알고리즘의 변형인 Simplified Memory bounded A*(SMA*) 알고리즘을 공부해보려고 해요!

  • Stuart Russell. 1992. Efficient memory-bounded search methods. In Proceedings of the 10th European conference on Artificial intelligence (ECAI '92). John Wiley & Sons, Inc., USA, 1–5.

 
메모리 사용량을 고려했다는 점에서 이전에 공부했던 RBSF 알고리즘과 비슷하다고 볼 수 있을 것 같습니다.

 
한번 자세히 알아볼까요?

1. SMA* 알고리즘과  A* 알고리즘의 차이점

Simplified Memory Bounded A* 알고리즘이 메모리 문제를 해결했다고 하는데 어떻게 해결했을까요?
 
정답은 바로 OPEN 리스트의 크기를 제한하는 것입니다.
노드를 탐색하다가 OPEN 리스트가 사용자가 정한 크기보다 커지면 가장 오래되고, f-value가 큰 노드를 삭제하는 것입니다.
 
"OPEN 리스트에서 노드를 삭제하면 최적성을 보장하지 못하는 거 아니야?"
이 생각이 떠오를텐데요. 아주 좋은 질문입니다!
 
SMA*를 구체적으로 설명하면서 궁금증을 해소시켜드리겠습니다.
 

2. SMA* 알고리즘 동작 방식

탐색 알고리즘

  1. OPEN 리스트의 최대 크기 B를 설정합니다.
  2. 시작 노드 s를 OPEN에 추가하고 USED 변수에 1을 저장합니다.
  3. OPEN에서 f ` 값이 가장 작은 노드 n을 추출합니다.
    • f ` 값이 최소인 노드들이 있다면 랜덤하게 아무 노드나 선택합니다.
    • 하지만 G에 포함된 노드가 있다면 해당 노드를 먼저 고릅니다.
    • 만약  OPEN이 비어있다면 탐색에 실패한 것입니다.
  4. Connected(n)에서 탐색되지 않은 노드 c를 하나씩 가져옵니다.
  5. g(c)+h`(c) 값을 계산하고, f`(n)과 비교하여 더 큰 값을 f`(c)에 저장합니다.
  6. 만약 Connected(n)의 노드들을 모두 탐색했다면 노드 n에 대해서 백업 알고리즘을 실행합니다.
  7. 만약 Connected(n)의 모든 노드들이 OPEN에 포함되어 있다면 노드 n을 OPEN에서 제거합니다.
  8. USED 변수에 1을 더합니다.
  9. 만약 USED가 B보다 클 경우, OPEN에서 가장 오래되고 f` 값이 큰 노드 d를 삭제합니다.
    1. 노드 d의 부모 노드가 있다면 부모 노드의 Connected에서 d를 제거합니다.
    2. 만약 f`(d)가 d의 부모 노드의 f`값보다 작다면 부모 노드의 f` 값을 f`(d)로 수정하고, 해당 부모 노드를 OPEN 리스트에 추가합니다.
    3. USED 변수에서 1을 뺍니다.
  10. 노드 c를 OPEN에 추가합니다.
  11. 3으로 돌아갑니다.

 

백업 알고리즘

  1. Connected(n)의 노드가 전부 탐색되지 않았거나, 노드 n의 부모 노드가 있지 않으면 백업 알고리즘을 종료합니다.
  2. f`(n)의 값을 Connected(n)들의 f`값 중 가장 작은 값으로 저장합니다.
  3. 만약 f`(n) 값이 변경되었다면 노드 n의 부모 노드에 대해서 백업 알고리즘을 실행합니다.

 

SMA* 알고리즘은 어떠셨나요?
알고리즘의 동작 방식 중 메모리가 꽉 찼을 때의 설명 쪽이 이해가 어려운 부분이 있어서 예제 코드 준비가 막히더라고요 ㅜ
준비되면 다시 업로드하도록 하겠습니다...!
 
이 알고리즘도 RBSF 알고리즘을 찾았던 PEA* 알고리즘 논문에서 찾게 되어 또 공부하게 되었습니다.
그런데 SMA* 알고리즘을 소개하는 논문에 다른 알고리즘들도 많더라고요...!
왜 논문을 읽으면 공부할 거리가 계속 생기는 걸까요?ㅎㅎㅎ...
논문 한편 읽기가 쉬운 일이 아닌 것 같습니다 ㅋㅋㅋㅋ
 
 

반응형