Fundamentals of AI Search Algorithms and Problem Solving

AI Search Problem Fundamentals

Understanding different types of search problems is crucial in Artificial Intelligence.

• Deterministic, fully observable: Classical search problem.
• Non-deterministic and/or partially observable: Requires different approaches beyond classical search.
• Non-observable: Sensorless problems.
• Unknown state space: Exploration problem.

Basic Search Concepts

• State Space: The set of all possible states reachable from the initial state.
• Initial State: The starting state.
• Actions: Possible operations available in a state.
• State Transition Function: Determines the resulting state after performing an action.
• Goal State: A desired state to be reached.
• Step Cost: The cost associated with performing an action.
• Solution: A sequence of actions leading from the initial state to a goal state.
• Frontier (or Fringe): The set of nodes that have been generated but not yet expanded.

True/False Check: The frontier in a search algorithm refers to the set of nodes that have been visited and not yet expanded. Answer: True

Evaluating Search Strategies

Search strategies are evaluated based on several criteria:

• Completeness: Does the strategy always find a solution if one exists?
• Optimality: Does the strategy always find the least-cost solution?
• Time Complexity: How long does it take to find a solution (often measured in nodes generated or expanded)?
• Space Complexity: How much memory is needed (often measured by the maximum number of nodes stored)?

True/False Check: Optimal solutions for classical search problems are always unique. Answer: False

True/False Check: Complete solutions for classical search problems are also optimal. Answer: False

Measuring Complexity

Complexity is often expressed in terms of:

• b: Maximum branching factor (number of successors per node).
• d: Depth of the shallowest goal node.
• m: Maximum depth of the state space (can be infinite).
• c*: Cost of the optimal solution.
• ε: Minimum step cost (must be > 0).

True/False Check: In a tree with an average branching factor of b and depth d, the total number of nodes is approximately b^d. Answer: True (More accurately (b^(d+1)-1)/(b-1), but O(b^d) is the asymptotic complexity).

Uninformed Search Strategies

These strategies use only the information available in the problem definition.

Breadth-First Search (BFS)

• Uses a FIFO queue for the frontier.
• Completeness: Yes.
• Optimality: Yes, if all step costs are equal (finds shallowest goal).
• Time Complexity: O(b^d).
• Space Complexity: O(b^d).

True/False Check: Breadth-first search always returns the path with the fewest nodes between a start and end node. Answer: True (as it explores layer by layer).

Depth-First Search (DFS)

• Uses a LIFO queue (stack) for the frontier.
• Completeness: No (can get stuck in infinite loops or deep paths). Yes, if the state space is finite and cycle detection is used.
• Optimality: No.
• Time Complexity: O(b^m) (can be much larger than BFS).
• Space Complexity: O(b*m) (linear space with backtracking).

True/False Check: Depth-first search always returns the path with the fewest nodes between a start and end node. Answer: False

Uniform-Cost Search (UCS)

• Expands the node n with the lowest path cost g(n). Uses a priority queue for the frontier.
• Completeness: Yes, if step costs are > ε > 0.
• Optimality: Yes.
• Time Complexity: O(b^(1 + floor(c*/ε))).
• Space Complexity: O(b^(1 + floor(c*/ε))).

True/False Check: Uniform cost search will always yield the path containing the fewest nodes between start and a goal. Answer: False (It finds the *least cost* path, which may not have the fewest nodes).

Depth-Limited Search (DLS)

• Performs DFS but only to a predetermined depth limit l.
• Completeness: No (if shallowest goal is beyond limit l).
• Optimality: No.
• Time Complexity: O(b^l).
• Space Complexity: O(b*l).

Iterative Deepening Search (IDS)

• Combines benefits of BFS and DFS. Uses DLS with increasing depth limits (0, 1, 2, ...).
• Completeness: Yes.
• Optimality: Yes, if all step costs are equal.
• Time Complexity: O(b^d).
• Space Complexity: O(b*d).

True/False Check: Iterative Deepening Search uses Depth First Search in its procedure. Answer: True

Informed (Heuristic) Search Strategies

These strategies use problem-specific knowledge (heuristics) to guide the search more efficiently.

Heuristics (h(n))

A heuristic function h(n) estimates the cost from node n to the nearest goal.

• g(n): The actual cost incurred from the start state to reach node n.
• h(n): The estimated cost from node n to the goal. It's a systematic guess!

Heuristic Properties

• Admissible Heuristic: Never overestimates the true cost to reach the goal (h(n) ≤ h*(n) for all nodes n, where h*(n) is the true cost). If h is admissible, then h(G) = 0 for any goal node G. Example: Straight-line distance.
• Consistent (Monotonic) Heuristic: For every node n and every successor n' generated by action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n' plus the estimated cost of reaching the goal from n' (h(n) ≤ c(n, a, n') + h(n')). A consistent heuristic is always admissible.

True/False Check: A heuristic is admissible if it never underestimates the true cost to the goal. Answer: False (It must never *overestimate*).

Greedy Best-First Search (GBFS)

• Expands the node that appears closest to the goal according to the heuristic: choose node with lowest h(n).
• Completeness: No (can get stuck in loops, similar to DFS). Yes in finite spaces with cycle checking.
• Optimality: No.
• Time Complexity: O(b^m) in the worst case, but often better with a good heuristic.
• Space Complexity: O(b^m) in the worst case.

A* Search

• Expands the node with the lowest evaluation function value f(n) = g(n) + h(n). Uses a priority queue.
• Completeness: Yes.
• Optimality: Yes, if the heuristic h(n) is admissible (for tree search) or consistent (for graph search).
• Time Complexity: Depends on the heuristic quality, can be exponential in the worst case.
• Space Complexity: Keeps all generated nodes in memory, often the main limitation.

True/False Check: In A* search, nodes in the fringe (or frontier) are ordered based on the evaluation function f(n)=g(n)+h(n). Answer: True

Constraint Satisfaction Problems (CSPs)

CSPs involve finding a state (a set of variable assignments) that satisfies given constraints.

Key Terms

• Variables: A set of elements whose values need to be determined (e.g., map coloring regions).
• Domains: The set of possible values each variable can take.
• Constraints: Restrictions on the values that variables can simultaneously take (e.g., adjacent regions must have different colors). Constraints can be unary, binary, or higher-order.

True/False Check: Constraints are always binary or higher-order, but never unary. Answer: False (Unary constraints restrict the domain of a single variable, e.g., VarA ≠ 'red').

True/False Check: For a CSP, a complete assignment is also a consistent assignment. Answer: False (A complete assignment assigns a value to every variable, but it might violate constraints. A *solution* is a complete *and* consistent assignment).

Solving CSPs

• Backtracking Search: A form of depth-first search that incrementally builds assignments. When a variable assignment violates a constraint, it backtracks.
• Forward Checking: When a variable X is assigned a value, check each unassigned variable Y connected to X by a constraint and delete values from Y's domain inconsistent with the assignment to X.
• Arc Consistency (e.g., AC-3): A variable X is arc-consistent with respect to another variable Y if for every value in X's domain, there is some allowed value in Y's domain. AC-3 enforces arc consistency across the CSP.

True/False Check: Forward checking terminates only when all variables have no legal assignment. Answer: False (It's an inference step performed *during* search after each assignment).

True/False Check: Forward checking is better than arc consistency because it will always remove more inconsistent values in one step. Answer: False (Arc consistency is generally stronger and removes more inconsistencies, though it might be computationally more expensive per step).

CSP Heuristics (for Backtracking)

• Minimum Remaining Values (MRV): Choose the variable with the fewest legal values remaining in its domain.
• Degree Heuristic: Choose the variable that is involved in the largest number of constraints on other unassigned variables. (Often used as a tie-breaker for MRV).
• Least Constraining Value: Prefer the value for the current variable that rules out the fewest choices for neighboring variables.

True/False Check: The order in which variables are assigned during backtracking search does not affect the efficiency of the search. Answer: False (Good variable and value ordering heuristics can significantly improve efficiency).

True/False Check: Using the Minimum Remaining Values (MRV) heuristic in Backtracking Search may sometimes lead to not finding a solution for a CSP even if one exists. Answer: False (Heuristics like MRV only affect the *order* of exploration, not the completeness of backtracking search).

Game Playing and Adversarial Search

Concerns problems involving multiple agents with conflicting goals.

Game Trees

Represent the possible moves in a game, with nodes representing game states and edges representing moves.

Minimax Algorithm

Used for finding the optimal move in a two-player, zero-sum game with perfect information.

• Maximizer (Max): Tries to maximize the score (utility).
• Minimizer (Min): Tries to minimize the score (utility).
• The algorithm explores the game tree recursively, propagating utility values up from the leaf nodes (terminal states).

True/False Check: Minimax will always give the best strategy against a rational opponent. Answer: True (Assuming a zero-sum game, perfect information, and infinite computational resources or searching to terminal states).

Alpha-Beta Pruning

An optimization technique for the Minimax algorithm that reduces the number of nodes evaluated.

• α (Alpha): The best value (highest score) found so far for Max along the path to the root. Initialized to -∞.
• β (Beta): The best value (lowest score) found so far for Min along the path to the root. Initialized to +∞.
• Pruning Condition: If at any Min node, β ≤ α from an ancestor Max node, prune the remaining children of the Min node. If at any Max node, α ≥ β from an ancestor Min node, prune the remaining children of the Max node. (Prune when α ≥ β).

True/False Check: Alpha-beta pruning can improve the efficiency of the minimax algorithm by pruning branches that cannot affect the final decision. Answer: True

True/False Check: Minimax with alpha-beta pruning will always explore the same number of nodes in the tree, regardless of the order in which the moves are explored. Answer: False (Move ordering significantly impacts the effectiveness of pruning; optimal ordering explores fewer nodes).

Complexity Notes and Summary

Complexity Variables Recap

• b: Maximum branching factor
• d: Depth of the shallowest solution
• m: Maximum depth of any node (may be ∞)
• l: Cutoff depth for depth-limited search
• c*: Cost of optimal solution
• ε: Minimum step cost (> 0)

Quick Formulas & Properties

• A* Search uses: f(n) = g(n) + h(n).
• BFS Time/Space Complexity: O(b^d).
• DFS Time Complexity: O(b^m). Space: O(bm).
• IDS Time/Space Complexity: O(b^d) / O(bd).
• UCS Time/Space Complexity: O(b^(1 + floor(c*/ε))).
• Optimality of A*: Guaranteed if h(n) is admissible (tree search) or consistent (graph search).
• Arc Consistency (AC-3): Prunes invalid domain values in CSPs.
• Alpha-Beta Pruning: Eliminates unnecessary branches in Minimax search.

Footnotes from Original

• * If m is finite and we use cycle detection (Relevant for DFS/GBFS completeness).
• ** In the worst case (Often applies to complexity bounds).
• *** O(b^(d+1)), or O(b^d) if we modify the code to return when a goal is generated (Likely refers to BFS/IDS time complexity details).
• **** If all steps have the same cost (Relevant for BFS/IDS optimality).