Artificial Intelligence : Unit - 2 Part - 9 : Problem Reduction

 

UNIT - II

Problem Reduction

---

Part A: Introduction

---

What is Problem Reduction?

Problem Reduction is the process of breaking a complex problem into smaller, simpler sub-problems, solving them individually, and then combining the solutions to solve the original problem.

It is based on the idea that solving small parts is easier than solving the whole problem at once.

---

Real-Life Example:

Imagine you're planning a wedding (big problem). You can reduce it into sub-problems like:

• Booking venue
• Arranging food
• Sending invitations
• Hiring photography

Solving these smaller tasks step by step makes the big event possible.

---

Part B: Problem Reduction in AI

---

In AI, complex problems are often reduced to sub-goals, which can be solved using search, planning, or reasoning.

This approach is useful in:

• Expert systems
• Automated planning
• Hierarchical problem solving

---

How Problem Reduction Works:

1. Identify the goal (main problem)
2. Decompose it into sub-problems
3. Solve each sub-problem
4. Combine their solutions to solve the main problem

---

Part C: Representation – AND-OR Graph

---

Problem reduction is usually represented using an AND-OR graph.

Node Type	Meaning
AND Node	To solve the parent node, all child nodes must be solved
OR Node	To solve the parent node, any one child node is sufficient

---

Part D: Advantages of Problem Reduction

Advantage	Explanation
✅ Easier problem solving	Breaking down tasks makes them manageable
✅ Reusability of sub-solutions	Same sub-problems may occur in different situations
✅ Efficiency	Reduces complexity and avoids solving unnecessary parts
✅ Supports AI reasoning and planning	AI systems use it to make decisions and solve tasks

---

Part E: Disadvantages of Problem Reduction

Disadvantage	Explanation
❌ Requires accurate decomposition	If broken incorrectly, sub-problems may not lead to solution
❌ Increased overhead	More tasks and bookkeeping during execution
❌ Depends on problem structure	Not all problems can be reduced easily

---

Part F: Applications in AI

Area	Use of Problem Reduction
Expert Systems	Breaking diagnosis into symptoms and tests
Game Playing	Breaking moves into sub-moves (e.g., Chess strategy)
Planning	Dividing tasks like cooking into sub-steps
Natural Language	Breaking a sentence into grammatical parts (parse tree)

---

Part G: Problem Reduction vs Traditional Search

Feature	Problem Reduction	Traditional Search (e.g., BFS)
Approach	Break down and solve sub-parts	Explore entire search space
Structure	AND-OR graph	Simple tree/graph
Reusability	✅ Yes	❌ No
Efficient for complex tasks?	✅ Yes	❌ No

---

📝 Summary

• Problem Reduction is the process of dividing a large problem into smaller sub-problems and solving them individually.
• Represented using an AND-OR graph.
• Helps in building smart AI systems that solve hierarchical or structured problems.
• Commonly used in expert systems, planning, robotics, and natural language processing.

Think of problem reduction like “solving a puzzle – piece by piece makes the whole picture clear.”