Artificial Intelligence Search Algorithms and CSP Methods

Posted on Mar 10, 2026 in Computer Engineering

Search Problem Components

  • State Space: All possible configurations.
  • Initial State: Starting configuration.
  • Successor Function: Allowed transitions between states.
  • Goal Test: Checks if the state satisfies the objective.
  • Cost Function (Optional): Cost per action.
  • Heuristic Function (Optional): Estimate to direct search.
  • Solution: Sequence of actions from initial to goal state.
  • State Space Graph: Vertices are states, edges are transitions.
  • Search Tree: Tree of paths explored by the algorithm.
  • Node: Data structure containing state, path, and cost.

Generic Search Algorithm

  • Initialize Frontier with the Initial Node.
  • While Frontier is not empty:
    • Remove a node from the Frontier.
    • If the node satisfies the goal, return the solution.
    • Add successors to the Frontier.
  • If Frontier is empty, no solution exists.
  • Search strategy is determined by the node removal order.

Depth-First Search (DFS)

  • Strategy: Expand the deepest node first.
  • Frontier Structure: Stack (LIFO).
  • Completeness: Not complete if m = ∞; complete only if the search space is finite.
  • Optimality: Not optimal.
  • Time Complexity: O(b^m).
  • Space Complexity: O(bm).

Breadth-First Search (BFS)

  • Strategy: Expand the shallowest node first.
  • Frontier Structure: Queue (FIFO).
  • Completeness: Complete if b is finite.
  • Optimality: Length-optimal (if all step costs are equal).
  • Time Complexity: O(b^(d+1)).
  • Space Complexity: O(b^(d+1)).

Uniform-Cost Search (UCS)

  • Strategy: Expands the node with the smallest path cost g(n).
  • Frontier Structure: Priority Queue ordered by g(n).
  • Properties: Equivalent to Dijkstra’s algorithm; complete and optimal if ε > 0.
  • Time/Space Complexity: O(b^(C*/ε + 1)).

Node Pruning and Cycle Checking

  • Path Checking: Prevents cycles on the current path.
  • Cycle Checking: Maintains a ‘Closed’ set of visited states to avoid redundant work.

Artificial Intelligence Fundamentals

  • AI: Branch of Computer Science studying intelligent behavior through computation.
  • Turing Test: Interaction-based test for machine intelligence.
  • Rationality: Maximizing expected utility based on outcomes.
  • Agent: Entity that perceives via sensors and acts via actuators.

A* Search

  • Evaluation Function: f(n) = g(n) + h(n).
  • Admissibility: If h(n) ≤ h*(n), A* is optimal.
  • Consistency: h(n) ≤ c(n,n’) + h(n’).
  • Complexity: O(b^d) in the worst case.

Constraint Satisfaction Problems (CSP)

  • Definition: (Variables, Domains, Constraints).
  • Backtracking Search: O(d^n) time complexity.
  • Forward Checking: Prunes inconsistent values from neighbors.
  • Generalized Arc Consistency (GAC): Ensures all values have support in constraints.

Greedy Best-First Search (GBFS)

  • Strategy: Expands node with the smallest h(n).
  • Properties: Not optimal; not necessarily complete.
  • Complexity: O(b^m) worst-case time and space.