Artificial Intelligence Search Algorithms

Search Terminology

• Problem Space: Environment including a set of states and actions to change those states.
• Problem Instance: Combination of initial state and goal state.
• Problem Space Graph: Graphical representation of problem space; nodes represent states, edges represent actions.
• Depth: Length of the shortest path from the initial state to the goal state.
• Space Complexity: Maximum number of nodes that can be stored in memory at any point.
• Time Complexity: Maximum number of nodes that are expanded during the search process.
• Admissibility: Property ensuring that an algorithm always finds an optimal solution.
• Branching Factor: Average number of children for a node in a search tree.

Search Techniques

General Search Techniques

• Path Finding: Involves systematically enumerating candidates and checking for solutions.
• Tree Search / Graph Search: Two main approaches to searching in AI.
  • Uninformed Search (Blind Search): No extra information about the states, relies entirely on problem definition.
  • Informed Search: Uses domain knowledge to guide the search toward the goal.

Brute-Force Search Strategies

• Brute-Force Search / Exhaustive Search: Technique that explores all possible solutions systematically.
  • Algorithm Steps:
  1. Generate a potential solution (expand a node).
  2. Test if it’s the expected solution.
  3. If not a solution, return to step 1.
• Requirements:
  • State description
  • Set of valid actions
  • Initial state and goal state description

Specific Search Algorithms

Breadth-First Search (BFS)

• Explores the nearest nodes first, using FIFO queue.
• Guarantees shortest path solution but has high memory consumption due to saving all nodes at each level.
  • Complexity: A depth of 16 can take approximately 350 years to solve.

Depth-First Search (DFS)

• Explores the deepest nodes first, implemented using LIFO stack.
• Risk of going infinitely deep and not finding the shortest path.

Bidirectional Search

• Simultaneous search from both initial and goal states, checking intersections for solutions.
• Often uses breadth-first search for forward search and depth-first for backward.

Uniform-Cost Search

• Similar to BFS but incorporates weights for each node.
• Always explores based on cumulative cost rather than depth.

Dijkstra’s Algorithm

• Specifically for finding shortest paths in weighted graphs.
• It systematically checks nodes and paths to ensure the least cost is followed.

Differences: Dijkstra’s vs Uniform-Cost

• Dijkstra’s algorithm exploratively enters all nodes to a priority queue while Uniform-Cost starts with only the initial node.

Informed Search Techniques

Why Use Informed Search?

• Informed searches take advantage of heuristic information to rank alternatives and optimize the search process, leading to more efficient solutions than uninformed searches.

Greedy Search and Best-First Search

• Takes the best option available at each step, evaluating based on a heuristic function that estimates distance to the goal.

Heuristic Function

• Denoted as $h(n)$, which estimates the cost from the node ( n ) to the goal state.

A* Search Algorithm

• Combines uniform-cost and greedy search strategies.
• Expands nodes based on a path cost and an estimated cost to the goal:
  f(n) = g(n) + h(n)
• Requires well-defined heuristics that are admissible, meaning they should not overestimate the cost to reach the goal state.

Heuristics

Admissible vs Non-Admissible Heuristics

• Admissible Heuristic: Underestimates the cost to reach the goal, ensuring optimal solutions.
• Non-Admissible Heuristic: May overestimate the cost, hence can lead to non-optimal solutions.

Comparing Search Algorithms

Conclusion

• Understanding these search algorithms and techniques is crucial for problem-solving in AI. Each has its strengths and weaknesses, relevant to their specific applications in various AI contexts.