Important alert: (current site time 5/21/2013 11:31:05 AM EDT) Brand new: recommended reading for every programming language on the site | revamped discussion board | 7 Source Code CDs

# A Star algorithm

Email
 Submitted on: 9/4/2012 3:11:52 PM By: Puneet Jindal Level: Advanced User Rating: Unrated Compatibility: C++ (general), UNIX C++ Views: 1903

This program demonstrates the working of A Star algorithm which uses heuristics search in state space.

code:
Can't Copy and Paste this?
 Terms of Agreement:    By using this code, you agree to the following terms...    You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge. You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.    You may link to this code from another website, but ONLY if it is not wrapped in a frame.  You will abide by any additional copyright restrictions which the author may have placed in the code or code's description. ``` //************************************** // Name: A Star algorithm // Description:This program demonstrates the working of A Star algorithm which uses heuristics search in state space. // By: Puneet Jindal // //This code is copyrighted and has// limited warranties.Please see http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=13834&lngWId=3//for details.//************************************** #include #include #include #include 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 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 ->"<"<"<"<"< Vertices; vector 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"<"; 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 '"<"; char other = '.'; cin>>other; if(other == '.') break; else { //cout<<"Enter cost of edge ("<>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"<= 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<

Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

What do you think of this code (in the Advanced category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)