배열을 사용한 C 구현의 스타 알고리즘?

Question

이곳은 새로운 곳입니다. 나 혼자서 C로 A-Star 알고리즘을 구현하려고한다. 나는 Hashmaps 나 Lists를 사용하는 법을 모르지만 배열을 사용하기 때문에 목록이 너무 길다.

문제는 간단합니다. NxN 배열이 있습니다. 위/아래 또는 왼쪽/오른쪽으로 이동할 수 있으며 대각선으로 갈 수 없습니다. 수평 이동은 수직 이동보다 (비용이 적게 = 5) (높은 비용 = 10).

장애물 셀이 있습니다. 자유 셀은 NxN 배열에서 숫자 0으로 표시되고 장애물 셀은 9로 표시됩니다. 장애 셀은 테이블 영역의 비율로 발생합니다 (예 : 테이블이 10 * 10이고 각각의 셀의 장애는 표에 약 109의있을 것, 0.1. 시작점 표시되는 2 및 3 개의 최종 목표로, G1과 G2를 이동 번호 1

.

#include<stdio.h> 
#include <stdlib.h> 

int main(void) { 
    //create a NxN array 

    int N, sX, sY, g1X,g1Y,g2X,g2Y,i,j,w; 
    double p; 
    float r; 
    printf("Give N\n"); 
    scanf("%d",&N); 
    printf("Give p\n"); 
    scanf("%lf",&p); 
    printf("Give S x k y\n"); 
    scanf("%d",&sX); 
    scanf("%d",&sY); 
    printf("Give G1 x & y\n"); 
    scanf("%d",&g1X); 
    scanf("%d",&g1Y); 
    printf("Give G2 x & y\n"); 
    scanf("%d",&g2X); 
    scanf("%d",&g2Y); 

    int table[N][N]; 

    for(i=0; i<N; i++){ 
     for (j=0; j<N; j++){ 

      r=(float)(rand() % 10)/10; // [0,1) 
      // printf("%f",&r); 
      if (sX==i && sY==j){ 
       table[i][j]=1; 
       //  printf("1"); 
      } 
      else if(g1X==i && g1Y==j){ 
       table[i][j]=2; 
       // printf("2"); 
      } 
      else if(g2X==i && g2Y==j){ 
       table[i][j]=3; 
       // printf("3"); 
      } 
      else if (p>=0 && r<=p){ 
       table[i][j]=9; 
       //  printf("9"); 
      } 
      else{ 
       table[i][j]=0; 
       // printf("0"); 
      } 


      printf("%d ",table[i][j]); 

     } 

     printf("\n"); 

    } 

    // Create the open list 


    int cX=sX, cY=sY; 

    while (cX!=g1X && cY!=g1Y) 
    { 
     int openList[4][2]; 
     //TOP 
     if(cX>0 && table[cX-1][cY]!=9){ 
      openList[0][0]=(cX-1); 
      openList[0][1]=cY; 
     } 
     else{ 
      openList[0][0]=-1; 
      openList[0][1]=-1; 
     } 

     //BOTTOM 
     if(cX+1<N && table[cX+1][cY]!=9){ 
      openList[1][0]=(cX+1); 
      openList[1][1]=cY; 
     } 
     else{ 
      openList[1][0]=-1; 
      openList[1][1]=-1; 
     } 
     //RIGHT 
     if(cY+1<N && table[cX][cY+1]!=9){ 
      openList[2][0]=cX; 
      openList[2][1]=(cY+1); 
     } 
     else{ 
      openList[2][0]=-1; 
      openList[2][1]=-1; 
     } 
     //LEFT 
     if(cY>0 && table[cX][cY-1]!=9){ 
      openList[3][0]=cX; 
      openList[3][1]=(cY-1); 
     } 
     else{ 
      openList[3][0]=-1; 
      openList[3][1]=-1; 
     } 

     printf("Open List of current cell:%d,%d\n",&cX, &cY); 
     for (i=0;i<4;i++){ 
      printf("%d , %d\n",openList[i][0],openList[i][1]); 

      cX=g1X; cY=g2Y; 
     } 
    } 
    return 0; 
} 

질문 :

나는 아래이 시도

1. 아직 열린 목록에 현재 셀을 추가하지 않았다는 것을 알고 있습니다. 나는 그것을 올바르게 추가해야합니까?

2. 공개 목록과 폐쇄 목록은 모두 해시 맵이어야합니까?

3. 어떻게 내가 선택한 셀의 부모와 연결을 유지해야한다고 생각합니까?

Answer 1

공개 목록은 우선 순위 큐 여야합니다. 그것은 새로운 참가자가 우선 순위 나 중요성에 따라 "밀어 넣을"수있는 대기열이지만 우리는 항상 전면에서 가져 와서 축소합니다. 이제 배열을 사용하여 각 삽입에 대해 순진하게 정렬 할 수 있지만 느려질 것입니다. 연결된 목록은별로 도움이되지 않습니다 (연결된 목록의 캐시 성능이 매우 나쁜 경우). 실제로는 메모리에 가능한 한 많이 유지하는 특수하게 작성된 우선 순위 대기열이 필요합니다.