Generic Search Algorithm
All searches essentially follow the same algorithm:
1. create an empty list called "closedset"; this list will contain states that have been visited 2. create a list called "openset" that contains just the starting state; this list contains states that have not been visited but are known to exist 3. create an empty map (key/value pairs) called "parents"; this map contains the previous state of each state that has been visited, as well as the direction that was taken to get to that state 4. while the openset is not empty: a. grab a state from the openset (and remove it) b. if that state is the goal, hey we're done! i. return a reconstructed path from the goal state to the start state (this is easy: recursively grab parent states from the "parents" map) c. if this state is not in the closed set: i. add this state to the closed set ii. for each successor that is accessible from here: 1. put the successor in the openset 2. if this successor doesn't have a parent recorded, record parent 3. else record parent if cost is lower than current parent of this successor 5. if the openset is empty and we never found the goal, oops!
(credit to Joshua Eckroth)