数组C实现中的星型算法？

Question

我对这里一无所知。我正在尝试用C实现A星算法.我不知道如何使用Hashmap或List(但我也是开放的，只要它们对我来说足够简单)，所以我使用数组。

问题很简单:有一个NxN数组。你可以上/下，也可以左/右，不能对角。水平移动(低成本=5)优于垂直移动(高cost=10)。

有一些障碍-细胞。自由单元在NxN阵列中由0表示，而障碍物单元以数字9表示。障碍单元以表中面积的比例出现(例如，如果表为10*10，且每个单元中设置障碍的独立可能性为0.1，则表中大约有109个。

用数字1表示起点，用2和3表示两个最终目标，G1和G2。

我尝试了以下几点：

#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. 开放列表和封闭列表都应该是Hashmap吗？
3. 您认为我应该如何与选定单元格的父单元保持连接？

Answer 1

打开的列表需要是优先级队列。这是一个队列，允许新进入者“推入”根据他们的优先次序或重要性，但我们总是缩小从前面。现在，您可以天真地使用数组并对每个插入进行排序，但这将是缓慢的。链接列表不会有多大帮助(链接列表的缓存性能非常差)。实际上，您需要一个专门编写的优先级队列，它尽可能多地保存在内存中。