Artificial Intelligence - Search Techniques & Problem Solving

Vocabulary practice flashcards covering Chapter 3: Search Techniques & Problem Solving, including agent types, problem formulation, search tree mechanics, and uninformed search strategies (BFS, DFS, DLS, IDS, UCS, and Bidirectional Search).

Simple-reflex Agent

An agent that directly maps states to actions and cannot operate well in environments where the mapping is too large to store or takes too long to learn.

Goal-based Agent

An agent that succeeds by considering future actions and the desirability of their outcomes.

Problem-solving Agent

A goal-based agent that decides what to do by finding sequences of actions that lead to desirable states.

Search Problem

A formulation consisting of a state space, a successor function (with actions and costs), a start state, and a goal test.

Successor Function

A transition model in a search problem that specifies which state results from performing a given action in a given state.

Solution (Search Problem)

A sequence of actions (a plan) that forms a path transforming the start state into a goal state.

Optimal Solution

A solution path connecting the initial node to a goal node that achieves the minimum total cost.

Path Cost

The sum of the individual nonnegative step or arc costs along a given path.

Depth of a Node

The length of the path from the root to node $N$, where the root has a depth of $0$.

Node Expansion

The process of evaluating the successor function on $\text{STATE}(N)$ and generating a child of $N$ for each state returned by the function.

Fringe

The set of all search nodes generated in the search tree that have not yet been expanded, typically managed as a priority queue.

Search Strategy

The specific ordering of nodes inside the fringe that dictates the order in which nodes are expanded.

Branching Factor ($b$)

The maximum number of successor states generated by any state in the search tree.

Completeness

The search evaluation criterion measuring whether an algorithm is guaranteed to find a solution if one exists.

Optimality

The search evaluation criterion measuring whether an algorithm guarantees finding the lowest-cost solution.

Breadth-First Search (BFS)

An uninformed search strategy implemented with a FIFO queue that expands the shallowest unexpanded node first, achieving a time and space complexity of $O(b^d)$.

Depth-First Search (DFS)

An uninformed search strategy implemented with a LIFO queue (stack) that expands the deepest unexpanded node first, having a worst-case time complexity of $O(b^m)$ and space complexity of $O(b m)$.

Depth-Limited Search (DLS)

A variant of depth-first search that prevents exploring paths deeper than a fixed limit $l$, giving nodes at depth $l$ no successors.

Cutoff

One of the three possible outcomes of Depth-Limited Search (alongside solution and failure), indicating that no goal was found within the predetermined depth cutoff limit $l$.

Iterative Deepening Search (IDS)

A search technique that combines the benefits of BFS and DFS by running Depth-Limited Search repeatedly with increasing cutoff limits ($k = 0, 1, 2, \dots$), using $O(b d)$ space and $O(b^d)$ time.

Uniform Cost Search (UCS)

An uninformed search algorithm (Dijkstra, 1959) that expands the node with the lowest cumulative path cost first using a priority queue ordered by path cost.

Bidirectional Search

A search strategy that executes two searches simultaneously—one forward from the initial state and one backward from the goal state—stopping when the two frontiers intersect.

Intersection Node

The specific state where the forward search frontier originating from the root and the backward search frontier originating from the goal meet in Bidirectional Search.