Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

A* Algorithm

pseudocode

  • Please log in to reply
6 replies to this topic

#1 Tonchi

Tonchi

    Helping the world with programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1249 posts
  • Location:Zagreb
  • Programming Language:C#, Others
  • Learning:C, C++, Python, JavaScript, Transact-SQL, Assembly

Posted 14 August 2012 - 01:20 AM

I want to learn this algorithm. First my question is, where I can use it? For what kind of problems?
And can someone explain me this pseudocode:

function A*(start,goal)
	 closedset := the empty set    // The set of nodes already evaluated.
	 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
	 came_from := the empty map    // The map of navigated nodes.

	 g_score[start] := 0    // Cost from start along best known path.
	 // Estimated total cost from start to goal through y.
	 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

	 while openset is not empty
		 current := the node in openset having the lowest f_score[] value
		 if current = goal
			 return reconstruct_path(came_from, goal)

		 remove current from openset
		 add current to closedset
		 for each neighbor in neighbor_nodes(current)
			 if neighbor in closedset
				 continue
			 tentative_g_score := g_score[current] + dist_between(current,neighbor)

			 if neighbor not in openset or tentative_g_score < g_score[neighbor]
				 add neighbor to openset
				 came_from[neighbor] := current
				 g_score[neighbor] := tentative_g_score
				 f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)

	 return failure

function reconstruct_path(came_from, current_node)
	 if came_from[current_node] is set
		 p := reconstruct_path(came_from, came_from[current_node])
		 return (p + current_node)
	 else
		 return current_node

  • 0

Microsoft Student Partner, Microsoft Certified Professional


#2 VNFox

VNFox

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 648 posts
  • Programming Language:C#, PHP
  • Learning:Assembly

Posted 14 August 2012 - 09:39 AM

I remember doing this while I was in school. Basically A* Algorithm is pretty helpful for CHESS program, or FLIGHT program, you want to find your TARGET position with lower cost and fast.

So for chess program, each move you make is a cost, so you want to make the best move as possible. So A* would give you all the possible moves and give you the best move possible.

For the Flight system ... find the best paths with the lowest cost.

hope this helps
  • 0

www.pickmike.com
I don't just develop software. I find solutions to your business needs.


#3 Tonchi

Tonchi

    Helping the world with programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1249 posts
  • Location:Zagreb
  • Programming Language:C#, Others
  • Learning:C, C++, Python, JavaScript, Transact-SQL, Assembly

Posted 14 August 2012 - 01:40 PM

Can you give me most simple example of A* algorithm. Just to learn the basics.
  • 0

Microsoft Student Partner, Microsoft Certified Professional


#4 VNFox

VNFox

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 648 posts
  • Programming Language:C#, PHP
  • Learning:Assembly

Posted 14 August 2012 - 02:06 PM

There are couple examples here at this site:
http://www.policyalm...tarTutorial.htm

and this:
http://stackoverflow...e-is-it-correct
  • 0

www.pickmike.com
I don't just develop software. I find solutions to your business needs.


#5 Tonchi

Tonchi

    Helping the world with programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1249 posts
  • Location:Zagreb
  • Programming Language:C#, Others
  • Learning:C, C++, Python, JavaScript, Transact-SQL, Assembly

Posted 14 August 2012 - 02:19 PM

This is all theoretic. Non of this is good if there is no practic example :)
  • 0

Microsoft Student Partner, Microsoft Certified Professional


#6 VNFox

VNFox

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 648 posts
  • Programming Language:C#, PHP
  • Learning:Assembly

Posted 14 August 2012 - 02:44 PM

I thought I already give you a practical example.

Give all possible solutions for a flight from LAX to DCA with all connections. Now find the lowest cost flight with low connections from LAX to DCA.
  • 0

www.pickmike.com
I don't just develop software. I find solutions to your business needs.


#7 Zer033x

Zer033x

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 50 posts
  • Programming Language:C++, C#, Lua
  • Learning:C++, C#, JavaScript, Lua, Others

Posted 14 August 2012 - 06:01 PM

You need to figure out what your points are for what you are using A* for, what I mean is if it is tile based or node based or pixel based whatever your unit of travel is will be the points you'll have in your lists. The idea is that you'll analyze all possible points adjacent to your current point then choose the lowest cost to travel that is also getting you closer to your goal. Once you reach your new point you will do the same thing except you'll add the already traveled point to another list of points to not look at. It'll keep traversing these lists and analyzing whatever type of cost conditions you give and choosing the lowest cost while not revisiting the same points until finally you are at your goal.
  • 0





Also tagged with one or more of these keywords: pseudocode

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download