A*알고리즘 천천히 이해하기
A*알고리즘 천천히 이해하기 — #정보처리기사 #개발자의도구들 #LOC기법 #LOC예측치 컴퓨터공학과 학사과정 중 공부한 내용을 정리...
#정보처리기사 #개발자의도구들 #LOC기법 #LOC예측치
컴퓨터공학과 학사과정 중 공부한 내용을 정리하였습니다.
\* 본글은 PC버전에 최적화 되어있습니다.
더 정확한 탐색 알고리즘
이전글을 통해 그리디 알고리즘과, 휴리스틱 개념을 배웠습니다. 하지만, 그리디 알고리즘은 현재 상태의 정보만을 고려하기 때문에, 최적해를 구하지 못하는 경우가 있었습니다.
이를 보완하기 위해 그리디 알고리즘과 더불어 실측거리까지 고려하는 A\*알고리즘을 사용할 수 있습니다.
A\* 알고리즘
A\*서치는 다음 탐색경로를 결정할때, 실측거리와 휴리스틱 값을 함께 고려합니다.
실측거리와 유클리드 직선거리의 합이 가장 짧은 경로가, 다음 경로로 선택되는 것이지요. 따러서 A\*서치로 탐색되는 경로는 아래 그림과 같습니다.
\* 여기서 실측러리에 사용되는 알고리즘은 uniform cost search로, Dijksta처럼 최단 거리를 갱신하며 이동하는 알고리즘으로 보시면 됩니다. == 시작 노드에서 현재노드까지 걸린비용.
A\*: g(n) + h(n) = 16, 17, 14, 20, -> goal
하지만 ,이 경로의 실측거리는 35로, 최적해를 구하지는 못했습니다. A\* 알고리즘 역시 비확정적인 결론을 도출하지만, 속도는 빠르며, 단순 그리디 알고리즘을 사용하는 것보다 더 좋은 결과를 도출합니다.
아래는 optimal, 그리디 알고리즘, A\*의 결과 비교입니다.
optimal | Greedy | A\*
실측: 32(최적), 그리디: 36, A\*: 35
실측을 완벽하게 구하면 좋겠지만, 현실세계의 문제들은 모든 변수를 고려하여 결과를 도출할 수 없습니다. 할 수 있다고 해도 시간이 너무 오래걸려, 답이 나오는 시점에서는 더 이상 필요없는 답이 될 수 있습니다.
하지만, A\*서치를 사용하면, 현재까지 측정된 거리와 휴리스틱이라는 정보를 참고하기에, 필요없는 탐색 경로를 크게 줄여나갈 수 있습니다.
휴리스틱의 기준
휴리스틱은 실제로 의사결정, 심리학, 경영학 등에서 많이 사용되는 용어인데, negative한 이미지가 강합니다. 이유는 이성적인 판단보다는, 직관이나, 경험과 같은 감정적인 영역에서의 의사결정을 내리기 때문입니다. 혹자는 휴리스틱을 "자기 마음대로 결정하는 것"이라고 표현하기도 합니다.
큰 개념에서 보면, 이 말은 일리가 있는 말입니다. 위 사례에서 우리는 휴리스틱으로 유클리드 거리를 계사용하였습니다. 하지만, 이는 100% 옳은 정답이 아니라, 우리가 "유클리드 거리를 사용하면 좋겠다"는 직관이 들어간 결정이었습니다.
실제로 도시와 도시를 이동하려면, 너무나 많은 변수가 존재합니다. 예를들어 교통량이나, 신호등 갯수, 혹은 도심 지역인지, 도로가 잘 정비되어 있는 곳인지, 산지인지, 평지인지 등 수 많은 변수가 존재합니다.이 많은 변수들을 모두 계산할 수 없기 때문에, 우리는 직관적으로, "더 좋은 결정일 것이다"라는 믿음으로 휴리스틱을 설계하여 A\*서치 알고리즘을 완성시킵니다.
하지만, 무작정 휴리스틱 알고리즘을 만든다면, 오히려 실측거리를 계산하는 것보다 더 비효율적으로 탐색이 가능할 수 있습니다. 극단적인 예시를 아래 보여드리겠습니다.
\* 파란글씨는, 휴리스틱 추정치인데, 이웃노드에 대한 추정치가 아닌, 각 노드에서의 목표까지의 추정치를 나타낸 것입니다. 처음 제가 작성할때 잘 못이해하여, 각 이웃 노드까지의 추정거리로 생각하여 그림을 그렸습니다. 하지만, 문제를 이해하는데 큰 문제는 없을 것 입니다.
실시간 교통량을 h(n)으로 두어 경로를 설정하였습니다. 현재 까지는 별 무리 없이 잘 가고 있습니다. 이제 다음 경로를 선택해야하는데, 원래대로라면, 우측 f(n) = 18로 가는것이 맞습니다.
그런데 갑자기 우측길로가는 통행량이 소폭 증가해 f(n)이 변경될 수 있습니다. 이때는 f(n)이 가장적은 경로를 선택하여 다시 처음지점인 A로 돌아오게 되었습니다.
이때 g(n)의 값이 극단적으로 변경되게 되는데, 처음 A->C의 비용은 2였으나, 한바퀴를 순회하면서 무려 31로 증가하게됩니다. 현재 시점에서 갈 수 있는 경로는 C, B, D 이므로 다시 f(n)을 구하면 D로 내려가게 될 것입니다.
하지만, 이 마저도 교통량이 변화하면 다시 C로 가게되는 상황이 생겨버립니다. 이 처럼 h(n), 즉 휴리스틱을 잘못 설정하게 된다면, 탐색 알고리즘은 실제 전체 측정가능 시간 보다 훨씬 오래걸리거나, 사이클을 형성하여 영원히 멈추지 않을 수 도 있습니다.
따라서, 휴리스틱은 보통 고정된 값을 사용하며, 그 기준역시, 충분히 합리적이도록 설정할 필요가 있습니다. 아래는 휴리스틱 선정 기준에 대한 설명입니다.
허용가능한 휴리스틱 알고리즘
admissible heuristic
- 허용되는 휴리스틱은 실제 비용을 넘어서는 안됩니다.
- 문제 해결에 필요한 연산을 줄여 나가야 합니다.
허용가능한 알고리즘은 문제에 대한 최적해를 보장합니다.
반면에, 허용되지 않는 휴리스틱은 최적해를 보장하지 않습니다. 오히려 실제 해보다 비용이 크거나, 오래 걸릴 수 잇습니다.
+ 추가 도움될 내용 정리
Heuristic search algorithms have the following properties:
- Admissible Condition: If an algorithm produces an optimal result, it is considered admissible.
- Completeness: If an algorithm ends with a solution, it is considered complete.
- Dominance Property: If A1 and A2 are two heuristic algorithms and have h1 and h2 heuristic functions, respectively, then A1 Will dominate A2 if h1 is superior to h2 for all possible values of node n.
- Optimality Property: If an algorithm is thorough, allowable, and dominates the other algorithms, that'll be the optimal one and will unquestionably produce an optimal result.
출처: https://www.simplilearn.com/tutorials/artificial-intelligence-tutorial/heuristic-function-in-ai
휴리스틱 일관성
휴리스틱 h가 일관적이라는 것은 모든 노드 n과 그 이웃 m에 대해 다음의 조건을 만족합니다.
이는 아래의 식으로 변형이 가능합니다.
n까지 휴리스틱 추정 비용 - m까지 휴리스틱 추정비용은 n에서 m까지의 실제 이동비용보다 작거나 같다. 이는, h가 목표노드에 접근함에 따라, 그 비용이 증가하지않으며, 실제 이동 비용을 초과하지 않음을 듯합니다.
위 사례에서는 A에서의 휴리스틱 추정치가 15인데, B를 거쳐 이동하는 실측 값과, B에서의 휴리스틱 추정치의 합보다 큰 값입니다.
이를 좀 더 직관적으로 이해하려면, 삼각형의 세변의 길이를 떠올리시면 됩니다. 위의 케이스의 경우에는 2(a) + 12(c) < 15(b)가 되는 경우가 될 것 입니다. (이해를 위한 예시일 뿐입니다)