A*길 찾기 알고리즘 에 대한 인식

최근 에 학교 앱 대회 에 참가 하려 고 하 는데 저희 팀 은 3D 미궁의 작은 앱 을 만 들 었 습 니 다.저 는 미궁의 생 성과 길 찾기 를 맡 았 습 니 다.
길 찾기 알고리즘 은 A*길 찾기 알고리즘 을 선 택 했 고 구체 적 으로 다음 블 로 그 를 참고 했다.
본 고 는 주로 자신 이 A*알고리즘 에 대한 이해,구체 적 인 세부 사항,위의 링크 와 상세 하 게 이야기 했다.
http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html
A*알고리즘 의 실현 에 대해 저 는 광범 위 하 게 검색 하 는 흔 한 실현 모델 입 니 다.
 
그렇다면 이 둘 사이 의 관 계 는 어 떨 까?
개인 적 으로 A*알고리즘 은 경로 정 보 를 가 진 전략 적 인 범위 우선 검색 입 니 다.저 희 는 평소에 사용 하 는 범위 우선 검색 이 고 경로 정보 가 없 으 며 검색 할 때 맹목적 인 검색 입 니 다.
예 를 들 어 길 을 찾 아 A 노드 에 이 르 렀 을 때 다음 단 계 는 A 를 중심 으로 A 주변의 8 개의 점 을 각각 테스트 하고 이 를 중심 으로 계속 밖으로 확산 시 켜 찾 아야 할 점 을 찾 도록 한다.
이러한 검색 은 맹목성 을 가지 고 대량의 무효 점 을 테스트 했다.
 
A*알고리즘 은 각 노드 에 경로 정 보 를 추가 합 니 다.
F:현재 점 의 경로 정 보 는 현재 점 에서 출발점 과 종점 까지 의 정 보 를 포함 합 니 다.(F=G+H）
G:현재 점 에서 유일한 출발점 까지 의 경로 정보 입 니 다.
H:현재 지점 에서 지정 한 종점 까지 의 거리 정보.
 
그러면 우 리 는 어떻게 이런 지 정 된 경로 정 보 를 통 해 광범 위 한 검색 이 다음 경로 점 을 맹목적 으로 선택 하지 않도록 최소 경 로 를 얻 을 수 있 습 니까? 
사실 우 리 는 이것 을 가장 작은 경로 의 감염 문제 로 볼 수 있다.
F B C D
E A G H
I  N K L
위의 그림 과 같이:
먼저 위의 블 로 그 를 참조 하면 수평 방향 으로 한 칸 을 이동 하 는 경 로 는 10 이 고 경사 방향 으로 한 칸 을 이동 하 는 경 로 는 14 이다.
기점 A 의 G 값 이 0 으로 초기 화 되 었 습 니 다.물론 자신 이 자신의 거리 까지 는 0 입 니 다.다른 점 의 G 가 INT 로 초기 화 됨MAX；A 에 대한 광범 위 한 검색 을 통 해 각 노드 의 G 값 과 부모 노드 를 설정 합 니 다.
예:A 의 8 개 방향,FBCEGINK 는 F 의 가장 작은 점 을 선택 하여 G 로 가정 한다.
     G 의 8 개 방향,BCDAHNCL 에 대해 우 리 는 이 8 개 방향의 G 값 과 부모 노드 를 설정 해 야 한다.이들 8 개 방향 중 A 와 겹 치 는 곳 은 BCNK 다.
     중첩 은 두 가지 경로 가 있다 는 것 을 의미 하 며 K 에 게 는 A->K 일 수도 있 고 A->G->K 일 수도 있다.
그러면 어떻게 선택 할 까요?
이때 우 리 는 G 의 값 을 판단 해 야 한다.어떤 경로 가 G 의 값 을 최소 화 하 는 지 판단 하려 면 우 리 는 그것 을 선택한다.
G 의 값 은 출발점 A 에서 본 노드 까지 의 경로 길이 입 니 다.이것 은 누 적 된 값 입 니 다.앞의 각 G 가 누적(감염)된 것 입 니 다.현재 의 경 로 를 대표 합 니 다.우리 가 선택 한 것 은 K 의 G 를 최소 화 하 는 것 입 니 다.그러면 전체 최소 경로 에 유리 합 니 다.계속 감염 할 수 있 기 때 문 입 니 다.
그러면 H 의 역할 은 어디 에 있 을까요?
H 는 경로 방향 에 대한 대체적인 판단 일 뿐이다.위의 그림 에서 종점 이 A 의 오른쪽 에 지정 되면 EFI 는 선택 되 지 않 을 것 이다.그러면 맹목적 으로 8 개 방향 을 판단 하지 않 아 도 된다.
 
마지막 으로 말 한 것:
G 와 H 의 역할 은 F 에 공통 적 으로 나타난다.매번 에 우 리 는 광범 위 한 검색 에서 F 의 가장 작은 점 을 찾 은 다음 에 G 의 값 에 따라 다음 광범 위 한 검색 에서 노드 의 부모 노드 를 설정한다.부모 노드 는 항상 하위 노드 의 G 값 을 가장 작 게 한다.(기점 A 까지 의 경로 가 가장 짧다).
 
자신 이 쓴 A*의 핵심 함수 코드 는 curr 노드 의 주변 8 개의 노드 를 테스트 하고 경로 와 부모 노드 정 보 를 설정 하 며 나머지 부분 은 넓 은 검색 을 우선 하 는 프레임 워 크 입 니 다.여 기 는 쓰 지 않 습 니 다.
 

 1 void getSurrroundPoints(point& curr, list<point>& result)  2 {  3     int x = curr.m_x;                              //curr    

 4     int y = curr.m_y;  5     

 6     for (int i = x-1;i <= x+1; i++)  7  {  8         for (int j = y - 1; j <= y + 1; j++)       //8   

 9  { 10             if (i == x && j == y)                  //     ，      

11                 continue; 12 

13             if ( find_if(closeList.begin(), closeList.end(), pointEqualLocation(i, j)) == closeList.end()  //           

14                 &&canReach(i, j))                                                                          //         

15  { 16                 if (x == i || y == j)      //         g=10

17  { 18                     if ((curr.m_g + 10) >= point_ptr[i][j].m_g) 19  { 20                                           //start (i,j)      curr 21                                           //     ，             

22  } 23                     else

24                     {                    //start (i,j)    curr      25                                          //            

26                         point_ptr[i][j].m_g = curr.m_g + 10;      //      G 

27                         point_ptr[i][j].m_fx = curr.m_x;          //     

28                         point_ptr[i][j].m_fy = curr.m_y; 29 

30  } 31  } 32                 else                     //    g=14;

33  { 34                     if ((curr.m_g + 14) >= point_ptr[i][j].m_g) 35  { 36                                         //start (i,j)      curr 37                                         //     ，             

38  } 39                     else

40                     {                    //start (i,j)    curr      41                                           //            

42                         point_ptr[i][j].m_g = curr.m_g + 14;    //      G 

43                         point_ptr[i][j].m_fx = curr.m_x;        //     

44                         point_ptr[i][j].m_fy = curr.m_y; 45 

46  } 47  } 48                 point_ptr[i][j].m_h = abs(endPoint_x - i) + abs(endPoint_y - j);  //        

49                 point_ptr[i][j].m_f = point_ptr[i][j].m_g + point_ptr[i][j].m_h;  //F=G+H

50 

51                 result.push_back(point_ptr[i][j]);                  //             

52  } 53  } 54  } 55 }