a star algorithm

 

 

추정경로 = 휴리스틱

삼각형의 밑변 구하는 방법과 같은 방식으로

추정잔여거리를 구함

테이블에 나와있는 경우도 있음

A를 openlist 에 삽입함

openlist = 우선순위 queue 의미

pop==> 비용평가를 한다

b,c,d에 대란 첫번째스텝에서의 비용평가

g = 현재까지의 비용

b 의 추정치 = 10

최소비용쪽으로 간다(d로 간다)

처음시작시 q,h가 0,0
외부 if 내부 for 문
목표노드가 만나게되면 바깥 종료

평가한노드를 리턴(마지막노드만날 때까지)

에이스타는 출발도착지점이멀어지면 급격하게 속도가 느려진다

그래서 1000배빠른 알고리즘은 무엇일까...?

jps (방사형 , 노드를 최우선 큐에 넣음)

open list --> 0 이 갈 수 있는 노드 1, 3
휴리스틱 

노드 3번에서 갈 수 있는 노드 2, 5

노드 0 번 지워버림 

6.8+5.6 = 12.4

6.8+ 6.5 = 13.3

( G score )

closed list

open list

작은 F score 로 갖는 애로 바꿔준다