Graph Search

Uninformed Vs Informed Search

Uninformed search algorithms are not provided with any information about the whereabouts of the goal, and thus search blindly. The only difference between different uninformed algorithms is the order in which they expand nodes. Several different types of uninformed algorithms are listed below:

• Breadth-first Search
• Depth-first Search
• Uniform Cost Search

Informed searches, on the other hand, are provided with information pertaining to the location of the goal. As a result, these search algorithms are able to evaluate some nodes to be more promising than others. This makes their search more efficient.

• A* Search

Terminology

Time Complexity

Assesses how long it takes an algorithm to generate a path, usually with respect to the number of nodes or dimensions present.

Space Complexity

Assesses how much memory it is required to execute the search.

Generality

Considers the type of problems that the algorithm can solve - is it limited to very specific types of problems, or will the algorithm perform well in a broad range of problems?