使用A*算法进行图遍历

Question

嘿，我是AI学生，打算尝试我的作业，实现A*算法以遍历图形。我使用c++代码，目前为止我所做的只有一个图形类+插入边缘和顶点函数的代码。

但现在我对如何定义成本函数（f=h(n)+g(n)）感到困惑...

此外，任何关于A*在图形中如何工作的代码参考或解释都会有所帮助。我在谷歌上找到的是关于通过A*进行路径查找的内容，与图形遍历无关。

#include <iostream>
using namespace std;

class Graph;
class node {
    friend class Graph;
private:
    char data;
    int cost;
    node *next;
    node *vlist;
    bool goal;
    bool visited;
public:
    node(char d,int c, bool g){
        cost = c;
        goal = g;
        next = NULL;
        data = d;
        vlist = NULL;
        visited = false;
    }
};

class Graph {
private:
    node *Headnodes;
    char n;
public:
    Graph ()
    {
        Headnodes = NULL;
    }
    void InsertVertex(char n, int c, bool g);
    void InsertEdge(char n, char m, int c);
    void PrintVertices();
    void Expand(char n);
};

/////////////////
//  INSERTION  //
/////////////////
void Graph::InsertVertex(char n, int c, bool g){
    node *temp = new node(n,c,g);
    if(Headnodes==NULL)
    {
        Headnodes=temp;
        return;
    }

    node *t=Headnodes;
    while(t->vlist!=NULL)
        t=t->vlist;
    t->vlist=temp;
}

void Graph::InsertEdge(char n, char m, int c){
    int temp_cost = 0;
    if(Headnodes==NULL)
        return;

    node *x=Headnodes;
    while(x!=NULL){
        if(x->data==m)
            temp_cost = (x->cost+c);
        x = x->vlist;
    }
    node *t=Headnodes;
    node *temp=new node(m,temp_cost,false);

    while(t!=NULL){
        if(t->data==n){
            node *s=t;
            while(s->next!=NULL)
                s=s->next;
            s->next=temp;
        }
        t=t->vlist;
    }
}

int min_cost = 1000;
bool enough = false;
void Graph::PrintVertices(){
    node *t=Headnodes;
    while(t!=NULL){
        cout<<t->data<<"\t";
        t=t->vlist;
    }
}

void Graph::Expand(char n){
    cout << n << "\t";
    char temp_min;
    node *t=Headnodes;
    while(t!=NULL){
        if(t->data==n && t->visited == false){
            t->visited = true;
            if (t->goal)
                return;
            while(t->next!=NULL){
                if (t->next->cost <= min_cost){
                    min_cost=t->next->cost;
                    temp_min = t->next->data;
                }
                t = t->next;
            }
        }
        t=t->vlist;
    }
    Expand(temp_min);
}

int main(){
    Graph g;
    g.InsertVertex('A',5,false);
    g.InsertVertex('B',1,false);
    g.InsertVertex('C',9,false);
    g.InsertVertex('D',5,false);
    g.InsertVertex('E',1,false);
    g.InsertVertex('F',3,false);
    g.InsertVertex('G',2,false);
    g.InsertVertex('J',1,false);
    g.InsertVertex('K',0,true);

    g.InsertEdge('A','B',2);
    g.InsertEdge('A','C',1);
    g.InsertEdge('B','A',2);
    g.InsertEdge('B','D',1);
    g.InsertEdge('B','E',1);
    g.InsertEdge('C','A',1);
    g.InsertEdge('C','F',1);
    g.InsertEdge('C','G',1);
    g.InsertEdge('E','J',3);
    g.InsertEdge('E','K',3);

    g.PrintVertices();

    cout<<"\n\n";
    g.Expand('A');

    return 0;
}

- Mohammad H

---

在我看来，这个问题唯一值得回答的是“请搜索一下”。既然你提到已经用谷歌搜索过了，“W”代表“维基百科”。他们有关Dijkstra和A*的文章非常详尽（没有代码，但算法描述很好）。至于你上面的代码中明显遗漏的部分，你没有任何数据可供启发函数（h(n)）的定义，因此无法定义它。另外，visited不足以满足要求，你需要存储f(n)并且需要一个带有暂定距离的队列。 - Jan Hudec

Answer 1

你所拥有的只是一个图搜索算法。

你忘记了A*算法的本质，即h(n)成本，它来自启发式计算。

你需要实现一个方法h(n)，根据你的启发式方法计算从实际路径到最终路径的可能成本，这个值将用于计算步行成本： f'(n) = g(n) + h'(n)，其中g(n)是已知的成本，在你的情况下，是x->cost。

g(n)是从起始位置到当前位置所需的总距离成本。

h'(n)是从当前位置到目标目的地/状态的估计距离成本。启发式函数用于创建这个估计值，以便知道达到目标状态需要多长时间。

f'(n)是g(n)和h'(n)之和。这是当前估计的最短路径。f(n)是真正的最短路径，直到A*算法完成才会发现。

所以，你需要做的是：

• 实现一个方法 heuristic_cost(actual_node, final_node);
• 将该值与实际成本一起使用，例如：min_cost=t->next->cost + heuristic_cost(t->next, final_node) ;

我真的很喜欢这里的解释: 链接 ，比维基百科的解释更清晰。

- Pih