3. Uninformed Search

There are multiple graph search algorithms we can use to search for elements in a graph, these do not consider any information we may have about the graph.

Properties of Algorithms

• Completeness: is the algorithm guaranteed to find a solution when there is one
• Optimality: does the algorithm find the optimal solution
• Time complexity: how long does it take to find a solution
• Space complexity: how much memory is needed to perform the search

Uninformed Search Algorithms

Breadth First Search

It is:

• Complete
• Optimal if all actions have the same cost
• Complexity is measured based on a branching factor $b$, If the goal is at level $d$ then the number of nodes is $b+b^2+b^3+\dots +b^d$. This means the time and space complexity is exponential.

Breadth First Search (Algorithm)

$\text{BFS}(G)$:

1. Select root vertex and add to a Queue (ADT)
2. While queue is not empty:
   1. Inspect first element $u$ in queue
   2. Add unvisited neighbours of $u$ to queue
   3. Remove $u$ from queue

Link to original

Depth First Search

Depth First Search (Algorithm)

$\text{DFS}(G)$:

1. Select root vertex and add to a Stack (ADT)
2. While stack is not-empty:
   1. Inspect top element $u$ on the stack
   2. Add any unvisited neighbours of $u$ to the stack
   3. Remove $u$ from the stack

Link to original

Bidirectional Search

Bidirectional Search is when we search from the initial and goal state at the same time and meet somewhere in the middle.