Now we know how informed search works we can begin to look at how we can use it in different ways to satisfy the various criteria inherent in each of the problems that we face. For instance, in a modelling problem where we are trying to optimise the model based on the inputs and outputs, we are looking for the shortest route through something. If this is the case then the best method to use would be a method called A* (A star).

A* simply takes the algorithm from our informed search framework and tweaks it slightly for the purpose of finding the shortest AND most cost effective route possible. It does this is firstly by sorting the openList by a combined “distance to goal” and “cost” heuristic value, and then moving the value of the next item from that working list to the initialise the next candidate solution value to be considered.

A similar algorithm called Dijkstra is used to find the shortest possible path between two points and is a lot like the A* method mentioned above, only Dijkstra doesn’t account for the heuristic cost involved in achieving a goal. Dijkstra does have additional functionality however, that checks to see (immediately after a candidate solution has been generated and tested) if the neighboring node is on the list of nodes that we need to check through and if it is, it updates a heuristic value in the openList (the distance that that node is to the start). This informs us, as we move through the landscape, how many steps it takes from each node to get back to the start, allowing us to select the optimal route between two points.

Pseudocode for Dijkstra & A* Search Algorithims

Variables workingCandidate, openList, closedList
SET workingCandidate = StartSolution
Evaluate (workingCandidate)
SET goalReached = CheckIfAtGoal(workingCandidate)
	WHILE (! goalReached AND Openlist not empty) DO
		// These lines generate new candidates
		Foreach (1-step neighbor)
			neighbour = ApplyMoveOperator(workingCandidate)

// This line tests the solution

			Evaluate(neighbor)

// These two lines of code are used to implement a "Dijkstra" algorithm (not used in A*).
 
			IF (neighbor is already on openList)
			UPDATE(neighbor.dist_to_start on openList)


// These lines update working memory //

			ELSE IF (neighbor is feasible) // We can go there
				ADD( neighbor to end of openList)
			ELSE // If we're at a dead end
				ADD( neighbor to end of closedList)
			COPY (working candidate to closedList)

// For A*: sort by combined distance to goal and cost.
// For Dijkstra: sort by distance to goal and ignore cost.

			SORT(OpenList)

// End update working memory //

			MOVE (first item from openList to working candidate)
			SET goalReached = CheckIfAtGoal(workingCandidate)
	OD //End loop
OUTPUT (goalReached, workingCandidate)

Leave a Comment

Your email address will not be published. Required fields are marked *