AI Search Algorithms and Problem-Solving

Vocabulary flashcards based on AI search algorithms and problem-solving techniques.

Search (in AI)

Systematically exploring states and actions to find a path from an initial state to a goal state.

State (in search)

An atomic representation of the world with no visible internal structure to algorithms.

Goal Formulation

Defining the objectives to meet, represented as goal states.

Problem Formulation

Choosing actions and states that lead to achieving the goal.

Assumptions in Classical Search

Observable, discrete, deterministic environment.

Components of a Search Problem

Initial state, Actions, Cost, Transition model, Goal predicate.

Transition Model

A function that gives the result of an action applied to a state.

Goal Predicate

A function that checks if a state meets the goal.

Solution (in search)

A path that leads to a goal; optimal solution is the least-cost path.

Examples of Toy Problems

N-puzzle, N-queens.

Goal of the N-Queens Problem

Place N queens on an NxN board so no two attack each other.

Good Problem Design (in search)

One that restricts the state space intelligently.

Actions in Vacuum World

Left, Right, and Suck.

Goal in Vacuum World

All squares must be clean.

Components of the 8-Puzzle

State of tiles, actions (move blank), transition model, goal test.

Examples of Real-World Search Problems

Route-finding, touring, traveling salesperson, layout, navigation.

Search Tree

Tree of nodes representing states and transitions.

Frontier Set

Leaf nodes available for expansion, also called the open list.

Causes of Redundant Paths

Multiple paths to the same state, or cycles.

How to Avoid Cycles

Use explored set or restrict problem formulation.

Tree Search

Search algorithm without explored set.

Graph Search

Search algorithm with an explored set.

Node (in a search tree)

Includes state, parent, action, path cost.

Path Cost g(n)

Cost from initial state to node n.

Frontier Queue

A queue holding nodes to be expanded; can be FIFO, LIFO, or priority.

Priority Queue

Queue that returns the element with the highest priority.

f(n) in A* Search

Estimated total cost: g(n) + h(n).

Completeness (in search)

Guarantee to find a solution if one exists.

Optimality (in search)

Guarantee to find the least-cost solution.

Uninformed Search

Search with no information about state quality.

Breadth-First Search (BFS)

Expands the shallowest unexpanded node.

BFS Guarantees

Complete and optimal if cost is a nondecreasing function of depth.

Uniform-Cost Search

Expands nodes with lowest path cost; optimal solution.

Depth-First Search (DFS)

Expands the deepest node first; incomplete and non-optimal.

Iterative Deepening

DFS with increasing depth limits to prevent infinite loops.

Informed Search

Uses a heuristic to estimate cost to goal.

Heuristic h(n)

An estimate of cost from n to goal.

Greedy Best-First Search

Chooses node with smallest heuristic h(n).

A* Search

Uses both path cost g(n) and heuristic h(n): f(n) = g(n) + h(n).

Admissible Heuristic

Never overestimates the true cost to reach the goal.

Consistent Heuristic

Satisfies: h(n) ≤ cost(n, a, n') + h(n')

When is A* Optimal?

When heuristic is admissible (tree) or consistent (graph).

Limitation of A*

High memory usage due to frontier and explored sets.

Variants of A*

Iterative deepening A, Simplified Memory A (SMA*)

Heuristic Error

Difference between true cost h(n) and estimate h'(n).

N-Puzzle Heuristics

h1 = misplaced tiles, h2 = Manhattan distance.

Relaxed Problem

One where constraints are loosened to simplify the problem.

Benefit of Relaxed Problems

Easier heuristic development; properties may transfer.

Automatic Heuristic Generation

Algorithms that generate heuristics from formal problem specs.

Why Merge Multiple Heuristics?

Taking the maximum of admissible heuristics improves accuracy.