Search Strategies Lecture Flashcards

This set of vocabulary flashcards covers key concepts from the lecture on uninformed and informed search strategies, including specific algorithms, complexity properties, and heuristics.

Uninformed Search Strategies

Search algorithms that only use information provided by the graph itself, such as breadth first search and uniform cost search.

Informed Search Strategies

Search algorithms that use problem-specific knowledge, such as a heuristic, to guide the search toward the goal state.

Depth First Search (DFS)

A search strategy where the frontier is implemented as a stack and the freshly generated nodes are explored first.

Heuristic ($h(n)$)

A function that estimates how close a state is to the goal, often described as a 'rule of thumb' or the cost of a solution to a relaxed problem.

Greedy Search

An informed search strategy that uses a priority queue to prioritize the node with the lowest heuristic value ($h(n)$).

Complete

A property of a search algorithm that guarantees it will find a solution if one exists.

Admissible

A property of a search algorithm that guarantees it will find an optimal solution, meaning the shortest path from the start state to the goal state.

Manhattan Distance

A heuristic function calculated by summing the differences of the coordinates of two points.

Euclidean Distance

A heuristic function that calculates the straight-line distance between two points.

Space Complexity of DFS

A linear complexity that depends on the branching factor ($b$) and the maximum depth ($m$) of the search tree, typically denoted as $O(b \times m)$.

Uniform Cost Search (UCS)

An uninformed search strategy that is both complete and optimal, prioritizing the lowest path cost ($g(n)$).

Frontier

The set of newly generated states or nodes that are waiting to be explored by the search algorithm.