프린지 검색

Fringe search
그래프 및 트리쉬
알고리즘
목록
관련 항목

컴퓨터 과학에서 프린지 검색은 주어진 초기 노드에서 하나의 목표 노드까지의 최소 비용 경로를 찾는 그래프 검색 알고리즘이다.

본질적으로, 프린지 검색은 A*와 반복적으로 심화되는 A* 변종(IDA*) 사이의 중간 지점이다.

g(x)가 첫 번째 노드에서 현재 노드로의 검색 경로 비용이고 h(x)가 현재 노드에서 목표에 이르는 비용의 경험적 접근 추정치라면, ƒ(x) = g(x) + h(x)이며 h*는 목표에 대한 실제 경로 비용이다.루트 노드에서 좌우 깊이 우선 재귀적 검색을 수행하는 IDA*를 고려하여 목표가 발견되거나 노드가 최대값 maximum에 도달하면 재귀 작업을 중지하십시오.첫 번째 임계값 ƒ에서 목표가 발견되지 않으면 임계값이 증가하고 알고리즘이 다시 검색한다.I.E. 문지방에 반복된다.

IDA*에는 세 가지 주요 비효율성이 있다.첫째, IDA*는 목표 노드에 대한 여러(때로는 최적화되지 않은) 경로가 있을 때 상태를 반복한다. 이는 종종 방문 상태의 캐시를 유지함으로써 해결된다.따라서 변경된 IDA*는 일부 스토리지를 사용하기 때문에 메모리 향상 IDA*(ME-IDA*)로 표시된다.또한 IDA*는 스토리지 없이 작동해야 하는 새로운 임계값에서 반복될 때 검색에서 모든 이전 작업을 반복한다.이전 반복의 리프 노드를 저장하고 다음 반복의 시작 위치로 사용함으로써 IDA*의 효율성이 크게 향상된다(그렇지 않으면 마지막 반복에서는 항상 트리의 모든 노드를 방문해야 한다).

프린지 검색은 검색 트리의 프런티어 또는 프린지 위에 반복할 수 있는 두 개 이상의 목록으로 구성된 데이터 구조를 사용하여 IDA*에서 이러한 개선을 실행한다.지금 한 리스트는 현재 반복을 저장하고, 다른 리스트는 나중에 바로 다음 반복을 저장한다.그래서 검색 트리의 루트 노드에서 지금은 루트가 되고 나중에는 비어 있게 된다.그런 다음 알고리즘은 다음 두 가지 작업 중 하나를 취한다.ƒ(head)이 현재 임계값보다 크면 지금부터 헤드를 제거한 후 나중의 끝에 추가한다. 즉, 다음 반복을 위해 헤드를 저장한다.그렇지 않으면 ƒ(머리)가 임계값보다 작거나 같으면 머리를 확장하고 머리를 폐기하고 자식을 고려하여 지금 시작에 추가한다.반복이 끝나면 임계값이 증가하고, 이후 목록이 현재 목록이 되며, 이후 목록이 비어 있다.

여기서 프린지와 A* 사이의 중요한 차이점은 프린지 목록의 내용이 반드시 정렬될 필요는 없다는 것이다. 즉, A*에 비해 상당한 이득이 된다는 것이다. 즉, 공개 목록에서 종종 값비싼 질서를 유지해야 한다.그러나 A*와 달리 프린지는 동일한 노드를 반복적으로 방문해야 하지만, 이러한 방문마다 비용이 A*에서 목록을 정렬하는 최악의 로그타임에 비해 일정하다.

가성음

현재 노드 앞에 있는 노드가 후순 부분이고 다른 모든 노드가 현재 목록인 두 개의 목록을 이중으로 연결된 목록으로 구현한다.그리드의 각 노드에 대해 목록에 미리 할당된 노드 배열을 사용하면 목록의 노드에 대한 액세스 시간이 상수로 감소한다.마찬가지로, 마커 배열을 통해 목록의 노드를 일정 시간에 조회할 수 있다.g는 해시 테이블로 저장되며, 마지막 마커 배열이 저장되어 이전에 노드를 방문한 적이 있는지 여부와 캐시 엔트리가 유효한지 여부를 일정 시간 조회한다. 

초기화하다(출발하다, 골을 넣다)     가장자리 F = s     캐쉬 C[출발하다] = (0, 무효의)     엷게 하다 = h(출발하다)     찾았다 = 거짓의      하는 동안에 (찾았다 == 거짓의) AND (F 아닌 텅 빈)         fmin = ∞         을 위해 마디를 짓다 에 F, 로부터 남겨진 로 맞다             (g, 부모) = C[마디를 짓다]             f = g + h(마디를 짓다)             만일 f > 엷게 하다                 fmin = 분(f, fmin)                 계속하다             만일 마디를 짓다 == 골을 넣다                 찾았다 = 진실의                 부숴뜨리다             을 위해 어린아이의 에 아이들.(마디를 짓다), 로부터 맞다 로 남겨진                 g_child = g + 비용이 들다(마디를 짓다, 어린아이의)                 만일 C[어린아이의] != 무효의                     (g_buy, 부모) = C[어린아이의]                     만일 g_child >= g_buy                         계속하다                 만일 어린아이의 에 F                     제거하다 어린아이의 로부터 F                 삽입하다 어린아이의 에 F 과거의 마디를 짓다                 C[어린아이의] = (g_child, 마디를 짓다)             제거하다 마디를 짓다 로부터 F         엷게 하다 = fmin      만일 도달한 == 진실의         역_경로(골을 넣다)

역 사이비 코드. 

역_경로(마디를 짓다)     (g, 부모) = C[마디를 짓다]     만일 부모 != 무효의         역_경로(부모)     인쇄하다 마디를 짓다

실험

컴퓨터 게임에서 흔히 볼 수 있는 장애물을 포함한 격자 기반 환경에서 테스트했을 때, 프린지는 타일이나 8진법의 사용에 따라 A*를 10%에서 40% 정도 능가했다.추가적인 개선에는 캐시에 더 쉽게 자신을 빌려주는 데이터 구조를 사용하는 것이 포함된다.

참조

외부 링크