Uninformed Search Strategies Practice Flashcards

These flashcards cover key terminology and concepts from the lecture on uninformed search strategies, including Breadth First Search (BFS), Uniform Cost Search (UCS), and Depth First Search (DFS).

State Space

The representation of a problem, often as a graph, through which an algorithm searches for a solution.

Search Tree

A structure superimposed on the state space used to record the progress and trace of a search strategy.

Start Node

The initial state where the problem begins.

Explored Nodes

Nodes that have already been checked by the algorithm to determine if they satisfy the goal condition.

Frontier

A data structure that records all the nodes the algorithm plans to explore in the future.

Breadth First Search (BFS)

A systematic search strategy that explores all nodes at a given depth level before moving to the next deeper level.

Queue

A first-in, first-out (FIFO) data structure used as the frontier in Breadth First Search.

Completeness

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

Admissibility

The property of an algorithm that allows it to find the shortest path; for BFS, this is guaranteed only if all arcs have the same cost.

Branching Factor ($b$)

The number of children or neighbors that every node in the search tree has.

Time Complexity (BFS)

The maximum amount of time an algorithm takes to find a solution; for BFS, it is $O(b^d)$, where $b$ is the branching factor and $d$ is the depth.

Space Complexity (BFS)

The amount of memory required by the algorithm; for BFS, it is $O(b^d)$ because all nodes at the same level must be stored in the frontier.

Uniform Cost Search (UCS)

A search algorithm that expands nodes based on their path cost using a priority queue, rather than just depth.

Priority Queue

A data structure used as the frontier for Uniform Cost Search where nodes are ranked by their path cost.

Path Cost

The sum of all costs associated with the arcs that constitute a specific path from the start node to a goal node.

Depth First Search (DFS)

A search strategy that expands the first node in the frontier to go as far as possible down a branch before backtracking.

Stack

A last-in, first-out (LIFO) data structure used as the frontier for Depth First Search.