UNKNOWN //************************************** // Name: A Star algorithm // Description:This program demonstrates the working of A Star algorithm which uses heuristics search in state space. // By: Puneet Jindal // // // Inputs:None // // Returns:None // //Assumes:None // //Side Effects:None //This code is copyrighted and has limited warranties. //Please see http://www.Planet-Source-Code.com/xq/ASP/txtCodeId.13834/lngWId.3/qx/vb/scripts/ShowCode.htm //for details. //************************************** #include<iostream> #include<vector> #include<cstring> #include<cmath> class Vertex; using namespace std; class Edge { public: int a,b; int cost; Edge(int c = 0) { a = b = -1; cost = c; } bool operator ==(Edge &e) { return a == e.a && b == e.b;} }; class Vertex { public: float x,y; vector<int> edge; char label; char status;// Degree is size of edge float gn,fn; string path; Vertex(char ch = '-') { x = y = 0.0; gn = fn = 0.0; label = ch; status = 'u'; path = ""; } bool operator == (Vertex &v) {return (label == v.label && x == v.x && y == v.y);} void Display() { //cout<<"x,y ->"<<x<<","<<y<<endl; //cout<<"Label ->"<<label<<endl; //cout<<"Status ->"<<status<<endl; //cout<<"Path ->"<<path<<endl; //cout<<"gn and fn ->"<<gn<<"\t"<<fn<<endl; } }; class Graph { public: vector<Vertex> Vertices; vector<Edge> Edges; Graph(){} int Find(char ch = '-') { for(int i = 0 ; i < Vertices.size() ; ++i) if(ch == Vertices[i].label) return i; cerr<<"Unknown vertex encountered"<<endl; return -1; } void Draw() { //cout<<"Enter label of the vertices and their co-ordinates.Press '.' to stop entering vertices"<<endl; while(true) { char label = ' '; //cout<<"Label ->"; cin>>label; if(label == '.') break; //cout<<"Co-ordinates(x,y) ->"; float x = 0, y = 0; cin>>x>>y; Vertex v(label); v.x = x; v.y = y; Vertices.push_back(v); } for(int i = 0 ; i < Vertices.size() ; ++i) { //cout<<"Enter adjacent vertices to the vertex '"<<Vertices[i].label<<"' one by one. Press '.' to stop entering."<<endl; while(1) { //cout<<"Adjacent vertex ->"; char other = '.'; cin>>other; if(other == '.') break; else { //cout<<"Enter cost of edge ("<<Vertices[i].label<<","<<other<<")"<<endl; int cost = 0; cin>>cost; Edge curr_edge(cost); curr_edge.a = i; cost = Find(other); curr_edge.b = cost; Edges.push_back(curr_edge); Vertices[i].edge.push_back(Edges.size()-1); Vertices[cost].edge.push_back(Edges.size()-1); } } } }// Graph drawn }; float Calculate(Vertex &start, Vertex &goal) { return sqrt( (start.x - goal.x)*(start.x - goal.x) + (start.y - goal.y)*(start.y - goal.y)); } int Min_fn_from_Open(Graph &g) { int min = 0; for(int i = 0 ; i < g.Vertices.size() ; ++i) if(g.Vertices[i].status == 'o' && g.Vertices[i].fn < g.Vertices[min].fn) min = i; return min; } bool OpenEmpty(Graph &g) { for(int i = 0 ; i < g.Vertices.size() ; ++i) if(g.Vertices[i].status == 'o') return false; return true; } string astar(Vertex &start, Vertex &goal, Graph &g) { start.gn = 0; start.fn = Calculate(start, goal); start.status = 'o'; start.path = start.label; do { int curr_state_index = Min_fn_from_Open(g); g.Vertices[curr_state_index].status = 'c'; g.Vertices[curr_state_index].Display(); if(g.Vertices[curr_state_index] == goal) { //cout<<"Goal found"<<endl; return g.Vertices[curr_state_index].path; } for(int i = g.Vertices[curr_state_index].edge.size()-1 ; i >= 0 ; --i) { int new_gn = g.Vertices[curr_state_index].gn + g.Edges[g.Vertices[curr_state_index].edge[i]].cost; g.Vertices[curr_state_index].fn = Calculate(g.Vertices[curr_state_index], goal); int descendent_index = -1; if(g.Vertices[g.Edges[g.Vertices[curr_state_index].edge[i]].a] == g.Vertices[curr_state_index]) descendent_index = g.Edges[g.Vertices[curr_state_index].edge[i]].b; else descendent_index = g.Edges[g.Vertices[curr_state_index].edge[i]].a; g.Vertices[descendent_index].Display(); if(g.Vertices[descendent_index].status == 'c' && new_gn < g.Vertices[descendent_index].gn) { g.Vertices[curr_state_index].status = 'u'; g.Vertices[descendent_index].status = 'o'; g.Vertices[descendent_index].path = g.Vertices[curr_state_index].path + g.Vertices[descendent_index].label; g.Vertices[descendent_index].gn = new_gn; // Common } else if(g.Vertices[descendent_index].status == 'o' && new_gn < g.Vertices[descendent_index].gn) { g.Vertices[descendent_index].path = g.Vertices[curr_state_index].path + g.Vertices[descendent_index].label; g.Vertices[descendent_index].gn = new_gn; // Common } else if(g.Vertices[descendent_index].status != 'o') { g.Vertices[descendent_index].path = g.Vertices[curr_state_index].path + g.Vertices[descendent_index].label; g.Vertices[descendent_index].status = 'o'; g.Vertices[descendent_index].gn = new_gn; // Common } g.Vertices[descendent_index].fn = Calculate(g.Vertices[descendent_index], goal); } }while(OpenEmpty(g) == false); return ""; } int main() { Graph G; G.Draw(); char s,g; cin>>s>>g; cout<<astar(G.Vertices[G.Find(s)], G.Vertices[G.Find(g)],G)<<endl; return 0; }