SMA*
SMA* |
 | 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다.(2009년 11월)(이를 과 시기 |
| 그래프 및 트리쉬 알고리즘 |
|---|
| 목록 |
| 관련 항목 |
SMA* 또는 Simplified Memory Bounded A*는 A* 알고리즘을 기반으로 한 최단 경로 알고리즘이다.SMA*의 주요 장점은 경계 메모리를 사용하는 반면, A* 알고리즘은 지수 메모리를 필요로 할 수 있다는 것이다.SMA*의 다른 모든 특성은 A*로부터 물려받은 것이다.
과정
특성.
SMA*의 속성은 다음과 같다.
- A*와 마찬가지로 휴리스틱과 함께 작동한다.
- 허용된 메모리가 가장 얕은 용액을 저장할 수 있을 정도로 높으면 완료된다.
- 허용된 메모리가 가장 얕은 최적의 솔루션을 저장할 수 있을 정도로 높을 경우 최적이며, 그렇지 않을 경우 허용된 메모리에 맞는 최적의 솔루션을 반환할 것이다.
- 메모리 바인딩이 허용하는 한 반복된 상태를 피한다.
- 사용 가능한 모든 메모리를 사용함
- 알고리즘의 메모리 바인딩을 확대하면 계산 속도만 빨라진다.
- 전체 검색 트리를 포함하기에 충분한 메모리를 사용할 수 있는 경우 계산 속도가 최적임
실행
SMA*의 구현은 A*와 매우 유사하다. 유일한 차이점은 f-cost가 가장 높은 노드는 남는 공간이 없을 때 대기열에서 제거된다는 것이다.이러한 노드가 삭제되기 때문에 SMA*는 상위 노드에서 가장 잘 잊혀진 하위 노드의 f-cost를 기억해야 한다.모든 탐색된 경로가 그런 잊혀진 경로보다 더 나쁜 것처럼 보일 때, 그 경로는 재생된다.[1]
유사 코드:
기능을 하다 SMA-별을 뜨다(문제): 경로 줄을 서다: 세트 의 노드들, 주문된 에 의해 f-비용이 들다; 시작되다 줄을 서다.삽입하다(문제.뿌리를 내리다-마디를 짓다); 하는 동안에 진실의 하다 시작되다 만일 줄을 서다.텅 빈() 그때 돌아오다 실패하다; // 주어진 메모리에 맞는 솔루션이 없음 마디를 짓다 := 줄을 서다.시작되다(); // 최소-f-비용 노드 만일 문제.이다-골을 넣다(마디를 짓다) 그때 돌아오다 성공; s := 다음에-후계자(마디를 짓다) 만일 !문제.이다-골을 넣다(s) && 깊이(s) == max_deep 그때 f(s) := 바 조로; // s를 지나갈 메모리가 남아 있지 않기 때문에 전체 경로가 무용지물이다. 다른 f(s) := 맥스.(f(마디를 짓다), g(s) + h(s)); // 후임자의 f-값은 최대값이다. // 상위 및 상위 항목의 f-값 // 후계자에 대한 휴리스틱 + 후계자에 대한 경로 길이 엔디프 만일 아니요. 더 많은 후계자 그때 갱신하다 f-비용이 들다 의 마디를 짓다 그리고 그것들의 의 그것의 조상 만일 필요했다 만일 마디를 짓다.후계자 ⊆ 줄을 서다 그때 줄을 서다.제거하다(마디를 짓다); // 모든 아이들이 더 짧은 방법을 통해 이미 대기열에 추가됨 만일 기억력 이다 가득 찬 그때 시작되다 badNode := 가장 얕은 마디를 짓다 와 함께 가장 높은 f-비용이 들다; 을 위해 부모 에 badNode.부모님 하다 시작되다 부모.후계자.제거하다(badNode); 만일 필요했다 그때 줄을 서다.삽입하다(부모); 끝맺다 엔디프 줄을 서다.삽입하다(s); 도중에 끝나다 종지부를 찍다 참조
- ^ Russell, S. (1992). "Efficient memory-bounded search methods". In Neumann, B. (ed.). Proceedings of the 10th European Conference on Artificial intelligence. Vienna, Austria: John Wiley & Sons, New York, NY. pp. 1–5. CiteSeerX 10.1.1.105.7839.
