AI Search Algorithms and Concepts

A collection of essential vocabulary terms and definitions related to AI search algorithms and concepts.

Agent

An entity that perceives its environment and acts upon it.

State Space

The set of all possible states in which a problem can exist.

Successor Function

A function that determines the possible actions from a given state and the resulting states.

Goal Test

A function to check if the current state satisfies the goal conditions.

Action Cost Function

A function that assigns a cost to each action taken from a current state.

Optimal Solution

A solution that has the lowest cost among all possible solutions.

Depth-First Search (DFS)

A search algorithm that expands the deepest node first.

Breadth-First Search (BFS)

A search algorithm that expands the shallowest node first.

Greedy Search

A search strategy that selects nodes based on the lowest estimated cost to reach a goal.

A* Search

An informed search algorithm that uses both the cost to reach a node and the estimated cost from that node to the goal.

Heuristic Function

A function that estimates the cost of the cheapest path from a given state to a goal state.

Completeness

A measure of whether an algorithm is guaranteed to find a solution if one exists.

Time Complexity

A measure of how long it takes to find a solution, typically expressed in terms of the size of the input.

Space Complexity

A measure of how much memory is needed to perform the search.

Informed Search

A type of search that uses domain-specific knowledge to reduce the search space.

Uninformed Search

A search that does not use any domain-specific knowledge, exploring the search space blindly.

Transition Model

Describes what state results from taking a specific action in a given state.

Fringe

The set of all leaf nodes that are generated but not yet expanded.