Searching Introduction & Problem Solving by Searching

Searching Techniques: Introduction & Problem Solving by Searching

1. Introduction to Searching Techniques

In Artificial Intelligence (AI), searching is one of the most fundamental techniques used for problem solving. A problem in AI is often represented as a state space (a collection of possible states) and the task is to find a path from the initial state to the goal state.

Since computers do not have human-like intuition, they rely on systematic search strategies to explore possible solutions. Searching can be thought of as the process of navigating through a search tree or graph until the solution (goal) is found.

• State space → The set of all possible states where the problem can exist.

• Initial state → The starting point of the problem.

• Goal state → The desired solution or target state.

• Operators → Actions that move from one state to another.

• Search strategy → The method for choosing which state to explore next.

---

2. Problem Solving by Searching

The process of solving problems by searching generally follows these steps:

Step 1: Problem Formulation

• Identify the initial state, possible actions (operators), transition model (how states change), and the goal state.

• Example: In the 8-puzzle problem, the board configuration is the state, moving tiles is the action, and the goal is arranging tiles in order.

Step 2: Search Space Representation

• Represent all possible states and their transitions in a state space tree/graph.

• Nodes = States

• Edges = Actions

Step 3: Search Algorithm Selection

• Apply a search strategy to explore nodes in the state space.

• Search strategies are broadly divided into:

  1. Uninformed (Blind) Search – No extra knowledge beyond problem definition. Examples: Breadth-First Search (BFS), Depth-First Search (DFS), Uniform Cost Search.

  2. Informed (Heuristic) Search – Uses heuristics (problem-specific knowledge) to guide search. Examples: Best-First Search, A* Search, Greedy Search.

Step 4: Exploration and Expansion

• Expand nodes (apply operators) and generate new states.

• Keep track of explored states to avoid repetition (closed list).

Step 5: Goal Test

• At each step, check if the current node satisfies the goal condition.

• If yes → return the solution path.

Step 6: Solution Representation

• The solution is represented as the sequence of actions from initial state to goal state.

• Example: Path in a maze, sequence of moves in chess, or route in GPS navigation.

---

3. Example of Problem Solving by Searching

Example: Pathfinding in a Maze

• Initial state: Entry point of the maze.

• Goal state: Exit point.

• Operators: Move up, down, left, right.

• Search Algorithm:

  • BFS → Finds shortest path (level-wise exploration).

  • DFS → Explores deeply but may not find shortest path.

  • A Search* → Uses heuristic (distance to goal) to find optimal path efficiently.

---

4. Key Characteristics of Search Strategies

When comparing search techniques, consider:

• Completeness → Will it always find a solution if one exists?

• Optimality → Will it find the best (shortest/least-cost) solution?

• Time Complexity → How much time does it take? (depends on branching factor b and depth d).

• Space Complexity → How much memory is needed?

---

✅ Summary:
Searching is the backbone of AI problem solving. It involves representing problems as state spaces, systematically exploring states using search strategies, and applying goal tests to find solutions. Different algorithms (uninformed vs informed) provide trade-offs between time, space, and optimality.

---