c++ - 用A*算法遍历图

Question

嘿，我是 AI 学生，我要尝试我的作业，即实现 A* 算法以遍历图形。我使用 C++ 代码，我现在所做的是下面的代码，它只是一个 Graph 类 + insertedge 和顶点函数。 但现在我对如何定义成本函数感到困惑 (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;
}

Answer 1

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

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

你必须实现一个方法，h(n) 将根据你的启发式计算从实际路径到最终路径的可能成本，这个值将用于计算步行成本:

f'(n) = g(n) + h'(n)，作为已知成本的 g(n)，在您的情况下， x->成本。

g(n) is the total distance cost it has taken to get from the starting position to the current location.

h'(n) is the estimated distance cost from the current position to the goal destination/state. A heuristic function is used to create this estimate on how far away it will take to reach the goal state.

f'(n) is the sum of g(n) and h'(n). This is the current estimated shortest path. f(n) is the true shortest path which is not discovered until the A* algorithm is finished.

那么，你必须做的:

• 实现方法 heuristic_cost(actual_node, final_node);
• 将此值与实际成本一起使用，如前面的等式，例如:min_cost=t->next->cost + heuristic_cost(t->next, final_node) ;

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