algorithm => * 길 찾기

A * 소개

A * (별표)는 한 노드에서 다른 노드로 경로를 찾는 데 사용되는 검색 알고리즘입니다. 그래서 이것은 Breadth First Search 또는 Dijkstra의 알고리즘 , Depth First Search 또는 Best First Search와 비교 될 수 있습니다. A * 알고리즘은 그래프 전처리가 옵션이 아닌 효율성과 정확도가 더 뛰어나다 고하는 그래프 검색에 널리 사용됩니다.

A *는 Best First Search의 전문 분야로, 평가 f 의 기능이 특정 방식으로 정의됩니다.

f (n) = g (n) + h (n) 은 초기 노드가 사고 노드 n 으로 가도록 조건화 된 목표들에 대한 최소 비용이다.

g (n) 은 초기 노드에서 n 까지의 최소 비용입니다.

H (n)은 N으로부터 N에 가장 가까운 목적으로 최소 비용

A *는 정보에 입각 한 검색 알고리즘으로 가능한 최소 시간 ( 가능한 추론을 사용하는 경우)에서 가장 작은 경로 (최소 비용의 경로)를 항상 보장합니다. 그래서 그것은 완전 하고 최적 입니다. 다음 애니메이션은 A * search-

A * 알고리즘을 이용한 8- 퍼즐 문제 해결

문제 정의 :

8 개의 퍼즐은 3 x 3 격자 (9 개의 사각형 포함)로 구성된 간단한 게임입니다. 사각형 중 하나가 비어 있습니다. 목표는 여러 위치로 정사각형으로 이동하고 "목표 상태"에 숫자가 표시되도록하는 것입니다.

8- 퍼즐 게임의 초기 상태와 최종 상태에 도달하면 초기 상태에서 최종 상태에 도달하는 데 가장 비용 효율적인 경로를 찾습니다.

초기 상태 :

_ 1 3
4 2 5
7 8 6

최종 상태 :

1 2 3
4 5 6
7 8 _

가정되는 추론 :

이 문제에 대한 발견 적 발견으로서 현재와 최종 상태 사이의 맨해튼 거리를 고려해 보자.

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

총 비용 함수 :

따라서 전체 비용 함수 f(n) 는 다음과 같이 주어진다.

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

예제 문제의 해결책 :

먼저 초기 상태에서 최종 상태에 도달하는 데 필요한 휴리스틱 값을 찾습니다. 비용 함수, g (n) = 0, 초기 상태에 있음

h(n) = 8

로서 상기 값이 얻어지고, 1 의 현재 상태가 1 개 수평 거리 거리보다 1 최종 상태이다. 2 , 5 , 6 마찬가지예요. _ 는 2 개의 수평 거리와 2 개의 수직 거리에 있습니다. 따라서 h(n) 총 가치는 1 + 1 + 1 + 2 + 2 = 8입니다. 총 비용 함수 f(n) 는 8 + 0 = 8과 같습니다.

이제는 초기 상태에서 도달 할 수있는 상태가 발견되며 _ 을 오른쪽 또는 아래로 이동할 수 있습니다.

따라서 이러한 움직임을 이동 한 후에 얻은 상태는 다음과 같습니다.

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

다시 총 비용 함수는 위에 설명 된 방법을 사용하여 이러한 상태에 대해 계산되며 각각 6 및 7로 나타납니다. 우리는 상태 (1) 인 최소 비용으로 상태를 선택했습니다. 다음 가능한 이동은 왼쪽, 오른쪽 또는 아래로 이동할 수 있습니다. 이전에 우리가 그 상태에 있었기 때문에 우리는 좌로 이동하지 않을 것입니다. 오른쪽 또는 아래로 이동할 수 있습니다.

다시 우리는 (1)에서 얻은 상태를 찾는다.

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

(3)은 비용 함수를 6으로 유도하고 (4)는 4로 이끈다. 또한 (2)는 비용 함수가 7이되기 전에 얻은 것을 고려할 것이다. 그것들로부터 최소값을 선택하면 (4)가된다. 다음 가능한 이동은 왼쪽 또는 오른쪽 또는 아래로 이동할 수 있습니다. 우리는 주를 얻는다 :

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

(5), (6), (7)에 대한 비용은 각각 5, 2, 4와 같습니다. 또한, 이전의 상태 (3)과 (2)는 각각 6과 7입니다. 우리는 (6) 인 최소 비용 상태를 선택했다. 다음 가능한 움직임은 위 (Up), 아래 (Down)이고 명확히 아래로 내려 가면 우리는 마지막 상태로 나아가며 경험적 함수 값은 0이됩니다.

A * 장애물이없는 미로를 통한 길 찾기

다음 4x4 격자가 있다고 가정 해 봅시다.

이것이 미로 라고 가정합시다. 그러나 벽 / 장애물은 없습니다. 출발점 (녹색 사각형)과 끝점 (빨간색 사각형) 만 있습니다. 초록색에서 붉은 색으로 가려면 대각선으로 이동할 수 없다고 가정 해 봅시다. 그래서 녹색 사각형에서 시작하여 우리가 이동할 수있는 사각형을 확인하고 파란색으로 강조 표시합니다.