A* 에이스타 (Best First Search)와 발견적 탐색(휴리스틱 서치, Heuristic)

휴리스틱 탐색 (발견적 탐색)

Informed Search 현재 위치에서 목적까지 가는데 유용한 서치

휴리스틱이라고도 부른다. 휴리스틱 탐색의 예시로서

교수님께서는 딱 하나만 설명을 해주셨다. A* 에이스타 이다.

노드 확장의 순서가 주요 요지이다.

평가 함수를 가지고 제일 좋은 평가를 통해 갈 경로를 선택 : 만약 현재 상태가 g와 h 사이에 존재한다면 g와 h의 비용을 각각 계산해서 더 좋은 경로를 선택하게 된다.

이러한 f를 계속 반복해서 진행을 시켜주는 것이 Best first Seach 즉 에이스타 알고리즘이다.

이러한 f라는 함수를 지정해주기 때문에 인위적을 지정해주는 휴리스틱 함수가 포인트가 된다. 그외에도 그리디 탐색법도 설명해 주셨다.

Greedy best-first search

- 현재 상황에서 가장 좋은 것만을 찾기 때문에 최적화는 안된다.

- 한부분에서만 빠질 수 있기에 완전성은 없다.

- 시간복잡도는 DFS의 최악의 케이스지만 휴리스틱을 잘 쓰면 드라마틱하게 잘 찾게 된다.

- 공간복잡도는 모든 노드들을 다 들고 있어야 해서 크다.

- 시간, 공간 : O(b^m)

A *

각각 휴리스틱 함수인 F(n)을 전반적으로 다 돌려보고 최적을 찾아간다.

그리디와는 다르게 확장을 더 많이 해서 점프를 통해 다른 브랜치까지 왔다갔다하면서 전반적으로 추정되는 가중치를 다 고려한다.

현 시점에서 도착점 까지의 가중치를 매번 계산해서 추정치를 휴리스틱하게 계산한 후에 탐색하는 방법이다.

에이스타의 한계

에이스타의 경우에는 퀄리티를 보장하지는 않는다. addmisable (자격이 있어야)해야 나오기 때문이다.

만약 특정 점이 더 최적이고 그걸 거친 이후에 가는 결과인 optimal goal G가 있고 좀 더 비싸지만 먼 나중에 갑자기 추가가 된 suboptimal goal G2가 있다면 일단 규칙에 따라 특정 점으로만 가기 때문에 이런 경우에는 퀄리티가 보장이 되지 않는다. G2위의 단계가 있다면 거기서 고려가 되겠지만 그렇지 않다면 고려가 되지 않는다.

* 여기서 sub optimal goal 이란? 차선의 선택 값을 의미한다. 차선책을 더 빨리 선택할 수 있는 상황이라면? 중간 경로가 없다면 무조건 최선책만 탐색이 되게 된다.

해결책

여기에 따른 해결책은 2가지가 있다.

1. Extra Book Keeping : 현재 상태를 고려할 때 나중에 추가 된 것을 Extra book keeping을 통해서 같이 탐색하는 방법.

2. Consistency : 선택적 함수(휴리스틱 함수)를 만들 때 지속성을 보고 판단한다. 휴리스틱이 지속적이면 된다. 

그럼 Consistency는 무엇일까? 이는 삼각형 정의와 유사한 수식이 하나 있는데

중간에 n'를 거쳐가는 길이 있고 바로 가는 길이 있다고 했을 때 
중간에 거쳐가는 비용이 무조건 더 크다. (삼각형에서 거쳐가는 거리는 직선거리보다 짧을 수 없다는 것과 동일한 이치)

이 경우 지속성이 있다고 한다. 그럴 때 A*s는 그래프 서치를 해도 항상 최적의 선택을 하게 된다.

이렇게 되면 중간에 다른 선택지가 생기게 되면 이걸 그냥 날리는 식으로 처리하는 것이다.

결론 

Admissable 과 Consisitency가 중요 개념

Consistent하면 Admissable한 것은 100%다.

그러나 그 반대의 경우는 100%는 아니다.

하지만 대부분의 경우에서는 Admissable 할 경우에는 지속성이 보장되는 경우가 많다고 한다.

이에 따라서 pathmax eqation을 쓰면 증진 될 수 있는데 이는 결국 휴리스틱 함수를 만들 때 양쪽 (중간 지점 포함된, 포함 안된 경로) 사이를 자체적인 계산을 통해서 최대한 비슷하게 맞춰주는 것을 의미힌다.

만약 그것조차 안되는 상황이라면 Extra Book Keeping을 해주어야 한다.

완전성 : O

최적 : O => optimally efficient : 쓸데 없는 일은 하지 않는다는 의미에서 최적이 성립니다. 

시간 복잡도 :  A*를 써도 exponential 한 시간 복잡도를 가진다.

공간복잡도 : 메모리에 모든 노드들 다 저장해서 사실상 가장 큰 단점이다.

결국 에이스타는 휴리스틱 알고리즘을 잘 짠다면 매우 빠르고 좋지만 문제는 메모리를 많이 잡아먹으므로 메모리에 여유가 많을 때 쓰는 것이 좋다. 또한 최적 경로가 100% 보장이라기 보다는 효율성을 기준으로 봤을때는 최적을 잘 찾아주는 느낌이다.

가중치가 부여된 A* 탐색

일반적인 휴리스틱 함수에 가중치를 두어서 하는 것인데 당연히 상황에 따라 가중치를 준다면 다른 결과가 나오게 되며 더 좋은 결과가 나올 수도 있다. 그러나 역시 여기서의 문제는 메모리 사용양이 더 늘게 된다.

그래서 RBFS와 같은 메모리의 한계를 극복하려는 여러 알고리즘이 더 나오고 있다고 한다.