3

Hey, I'm AI Student and gonna try my homework that is implementation of A* algorithm in order to traversal a graph. i use c++ codes and what i made for now is below code which is only a Graph class + insertedge and vertices functions. but now i'm confused of how to define cost function (f= h(n) + g(n)) ...

also any code refrence or explain of how A* works for graphs would help me . what i found in google was about pathfinding via a* and it has nothing with traversal graph.

#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;
}
1
  • 1
    IMHO the only response this deserves is "STFW". Since you mention you did google, the "W" means "Wikipedia". Their articles on Dijkstra and A* are quite comprehensive (no code, but the algorithm descriptions are good). As for obvious omissions in your code above, you don't have any data to base your heuristics (h(n)) on, so you can't define it. Also visited is not enough, you need to store f(n) and you need a queue with tentative distances.
    – Jan Hudec
    May 3, 2011 at 10:12

1 Answer 1

5

What you have is only a graph search algorithm.

You forgot the essence of the A* algorithm, that is the h(n) cost, that comes from an heuristic calculation.

You have to implement a method, the h(n) that will calculate, based on yours heuritics, the possible cost from actual path to the final path, and this value will be used to calculate the walking cost:

f'(n) = g(n) + h'(n), being the g(n) the already know cost, at your case, the x->cost.

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.

So, what you have to do:

  • Implement a method heuristic_cost(actual_node, final_node);
  • Use this value together with the actual cost, like the equation before, by example: min_cost=t->next->cost + heuristic_cost(t->next, final_node) ;

I really like the explanation here: Link , cleaner than wikipedia's explanation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.