The first search algorithm I implemented was Depth-First Search (DFS). DFS is an uninformed search method, that will return a solution if one exists, but does not guarantee said solution to be optimal. DFS explores a search tree by traversing the first available child node until the max depth of the tree is reached; from there it moves adjacently to the next available node and repeats the search until a solution is found. While the memory required to run DFS is minimal compared to other search methods, it can take a long time for the algorithm to find a solution, which may be suboptimal. I implemented Depth-First Search to juxtapose its performance to informed search methods.

My next algorithm was Breadth-First Search (BFS). In contrast to Depth-First Search, BFS explores every node at each level of a search tree before increasing the search depth. As a result, BFS needs a lot of memory and time to run, but an optimal solution is guaranteed if one exists in the problem. A good way to think about this is that the maze-solving agent will look at every adjacent space and see if one of the tiles next to it is its goal. This idea of looking and exploring all adjacent tiles is repeated for all positions until the goal is found. Due to the thorough nature of this algorithm, the first solution found is guaranteed to be optimal. Like DFS, Breadth-First Search was primarily implemented to show the difference between uninformed and informed search methods.

A-Star (A*) was the first of the informed search methods I implemented. Rather than blindly exploring all nodes of a problem space, A* makes informed decisions about how to progress through a search tree. For each node, A* tracks the actual cost/distance (g(n)) to reach that point from the root/starting position. It also computes a heuristic (estimation) function (h(n)) at each node to estimate the remaining distance/cost to reach the goal. Each node to be expanded is ordered by its evaluation function, f(n) = g(n) + h(n), in ascending order and A* expands the node with the smallest f(n) value. This algorithm allows an agent to explore all possible optimal paths, without wasting time traversing through obviously suboptimal solutions. A significant problem I ran into while implementing A* was that while it was more efficient than either Depth-First Search or Breadth-First Search, it still took significant time to find an optimal solution. So, after some further research into search algorithm optimization, I realized I could prune my search tree. Resulting in a noticeable decrease in runtime. Upon seeing this improvement, I went back and implemented pruning into my DFS and BFS algorithms further increasing their runtime quality.

The last search method I implemented was Iterative-Deepening A-Star (IDA*). IDA* works similarly to A*, except that there is a cost (f(n) = g(n) + h(n)) limit. If a node’s total cost is greater than the cost limit, it is not expanded. If all nodes with a cost less than the limit have been expanded and no solution has been found, the cost limit will increase, and the algorithm will start over. This does lead to some node reopening which increases runtime, but with large problem spaces, this added time is relatively insignificant. Where IDA* improves upon A* is in its space complexity (memory requirement). Where A* must keep the entire search tree in memory, IDA* must only keep the current branch (path) from root node to the current node in memory.