c - A* 在 C 中搜索 : implementation and performance on graph map

Question

我正在为一门类(class)编写一个“游戏”项目，使用图形的“隐式”表示:我有一个像这样定义的 N*M 项矩阵:。

typedef struct {
    int x;
    int y;
    int k;      //value of the position
    int ID;
    bool path;  //temporary field used to print the path
} VCOORD;

typedef struct gObj {
    //numero vertici
    int             vNum;           //number of vertices

    VCOORD  **      maze;           //pointer to implicit maze
    int             width;          //width of the maze
    int             height;         //height of the maze

    //function pointers
    struct gObj *   ( *build)           ( struct gObj *, int );
    Set *           ( *getAdjList )     ( struct gObj *graph, int u );

    void            ( *insertEdge )     ( struct gObj *, int , int , int  );
    void            ( *insertVertex )   ( struct gObj *graph );

    int             ( *getWeight )      ( struct gObj *, int, int );
    int             ( *transpose )      ( struct gObj *graph );
    int         *   ( *path)            ( struct gObj *, int , int );
} GRAPHOBJ;

我已经实现了:

BFS，Dijkstra，A*

BFS 和 Dijkstra 工作正常，但我对 A* 有一些问题

A*(一星)

int *a_star ( GRAPHOBJ *graph, int s, int t ) {
    int x, y, i;
    int cost;
    bool found = false;
    void    *   tmp;                    //used to store Heap first element
    Set     *   AdjList     = NULL;     //Adjiacence list implemented as queue
    Set     *   closed      = NULL;     //Closed set implemented as queue
    Heap    *   open        = NULL;     //Open set implemented as Heap
    int     *   pred        = ( int *) malloc ( graph->vNum * sizeof ( int ) );

    int g[graph->vNum];                 //g distance function
    int f[graph->vNum];                 //f distance function

    //initialization
    for ( i = 0; i < graph->vNum; i++ ) {
        f[i]        = INFINITE;
        g[i]        = 0;
        pred[i]     = NIL;
    }
    f[s] = heuristic ( graph, s, t );
    open = initializeHeap ( minHeapify );
    insert ( open, new_HeapData ( s, 0 ) );

    while ( !isHeapEmpty ( open ) && found == false ) {

        //extracting the first Object of the Heap ( Open )
        tmp     = extractFirst ( open );
        //pushing the node into the Closed set
        push ( closed , setInt ( x ) );
        //get the int number from the extracted Object
        x       = getData ( tmp );
        //get the ditance f from the extracted Object
        f[x]    = getKey ( tmp );

        //debug
        if ( PRINTALL ) graph->maze[getCoord ( graph, x )->y][getCoord ( graph, x )->x].path = true;
        //printf ("x: %d ", x);
        if ( x == t ) {
            found = true;
        } else {

            AdjList = graph->getAdjList ( graph, x );

            while ( !isEmpty ( AdjList ) ) {
                //getting the first element of the adj. list
                y               = getInt ( getFront ( AdjList ) );
                //graph->getWeight refers to getMatrixWeight
                g[y]            = g[x] + graph->getWeight ( graph, x, y );
                cost            = g[y] + heuristic ( graph, y, t );

                //checking if y is in the open set
                bool yInOpen    = heapIntSearch ( open, y );
                //checking if y is in the closed set
                bool yInClosed  = intSearch ( closed , y );

                if ( yInOpen && cost < f[y] ) { // case 1
                    decreaseKey ( open, y, cost );
                } 

                else if (  yInClosed && cost < f[y] ) { // case 2
                    deleteFromSet ( closed, y );
                    insert ( open, new_HeapData ( y, cost ) );
                }

                else if ( !yInClosed && !yInOpen ) { // case 3
                    insert ( open, new_HeapData ( y, cost ) );
                }
                AdjList = dequeue ( AdjList );
                if ( pred[y] == NIL )
                    pred[y] = x;
            }
        }           
    }
    pred[s] = NIL;
    printf ("\n\n");
    return pred;
}

启发式函数，具有欧几里得/曼哈顿距离:

int heuristic ( GRAPHOBJ *graph, int s, int t ) {
    VCOORD *    start       = getCoord ( graph, s );
    VCOORD *    target      = getCoord ( graph, t );
    /*manhattan*/return ( abs ( start->x - target->x ) + abs ( start->y - target->y ) );
    /*euclidian*///return pow ( pow ( ( target->x - start->x ), 2 ) + pow ( ( target->y - start->y ), 2 ), 0.5 );
}

边权重函数:

int getMatrixWeight ( GRAPHOBJ *graph, int u, int v ) {
    int weight = 1;
    return weight;
}

邻接列表实现(NORTH、SOUTH 等是减少/增加坐标的宏:

Set *getAdjList ( struct gObj *graph, int u ) {
    Set *Adj = NULL;
    int x = u % graph->width;
    int y = u / graph->width;
    int neighbor;

    if ( NORTH(y) > 0 && graph->maze[NORTH(y)][x].k != 9 ) {
    //if ( NORTH(y) > 0 ) {
        neighbor = graph->width * ( NORTH(y) ) + ( x );
        Adj = enqueue ( Adj, setInt ( neighbor ) );
    }
    if ( EAST(x) < graph->width && graph->maze[y][EAST(x)].k != 9  ) {
    //if ( EAST(x) < graph->width  ) {
        neighbor = graph->width * ( y ) + ( EAST(x) );      
        Adj = enqueue ( Adj, setInt ( neighbor ) );
    }
    if ( SOUTH(y) < graph->height && graph->maze[SOUTH(y)][x].k != 9 ) {
    //if ( SOUTH(y) < graph->height ) {
        neighbor = graph->width * ( SOUTH(y) ) + ( x );     
        Adj = enqueue ( Adj, setInt ( neighbor ) );
    }
    if ( WEST(x) > 0 && graph->maze[y][WEST(x)].k != 9 ) {
    //if ( WEST(x) > 0 ) {
        neighbor = graph->width * ( y ) + ( WEST(x) );      
        Adj = enqueue ( Adj, setInt ( neighbor ) );
    }

    return Adj;
}

问题:

1. 如果边的权重等于 1(如 getMatrixWeight 函数中声明的那样)，A* 会采取奇怪的路径，如下所示: /image/Z80GM.png 如果边的权重 > 1，A* 可以正常工作(并非始终如此，但 99%)

2. 如果目标无法到达，A* 似乎会陷入循环。 BFS 和 Dijkstra 没问题。

3. 我实现了一些“实用程序”来监控脚本的性能。 BFS 和 Dijkstra 工作得很好(BFS 比 Dijkstra 快一点，但我认为这可能取决于堆实现)。 但从图中可以看出，A* 似乎慢了 10 到 30 倍!所以我认为实现上有问题，但我找不到问题所在(也许它与第2点:循环有关)!

我认为其他函数(集合和堆实现、邻居实现)工作得很好，因为 BFS 和 Dijkstra 没有问题。

如果您想查看其余代码，请访问:repo: https://bitbucket.org/ozeta86/labirinto/src

Answer 1

首先，您会遇到初始化问题，因为您 push ( close , setInt ( x ) ); 但第一次执行此操作时 x 并未初始化。但这不是问题的原因。

阅读您的代码，我了解到您的 A* 实现如下:

• f[i] 是节点 i 的最佳估计成本。
• g[i] 是通往节点 i 的路径的累积距离
• 通过添加额外的权重来计算 g[y]，即从 x 到 y 的路径的延长。
• 然后通过使用路径的累积距离加上到目标的剩余启发式来计算该成本。

问题是你的 g[] 累积的不是一条路径的距离，而是所有探索的路径的距离。如果多个路径使用同一个节点，则 g 将毫无意义。

换句话说，对于您尝试扩展的任何到达 i 的路径，g[i] 将不包含到 i 的路径的唯一距离(需要 A* 才能计算有意义的成本)，而是包含不可预测的值这取决于之前探索的路径。

因此出现了不稳定的结果。

您必须更改数据结构，以便将路径的距离与路径一起存储在堆上，以便在下次尝试扩展它时，您将使用与该路径相对应的实际距离。