Siksha Sarovar

Siksha Sarovar (sikshasarovar.com) is a free educational web application that helps students in India learn programming and prepare for academic and competitive exams. The platform offers structured coding courses (C, C++, Python, Java, HTML, CSS, PHP, Power BI, AI, Machine Learning, Data Science), complete university curriculum notes for BCA/MCA students with previous year question papers, Class 10 and Class 12 CBSE/HBSE school notes, and dedicated preparation material for SSC, UPSC, Banking, Railway and other government exams. Browsing the site is completely free and requires no account. Users may optionally sign in with Google solely to save their learning progress, quiz scores and personal preferences across devices.

Privacy Policy | Terms of Service | Contact Siksha Sarovar | About Siksha Sarovar

v4.0.9 · PWA
Siksha Sarovar logo
Siksha Sarovar
Your Learning Universe

Siksha Sarovar is a free e-learning platform for coding courses, BCA university notes and competitive exam preparation. Optional Google sign-in saves your learning progress across devices.

Initializing knowledge base…
Compiling modules 0%

Unit 1 — Issues in the Design of Search Problems

Lesson 9 of 34 in the free Artificial Intelligence notes on Siksha Sarovar, written by Rohit Jangra.

Issues in the Design of the Search Problem

Designing a search-based problem solver is not just "pick BFS or DFS" — several deeper design questions must be answered first.

Key Design Issues

IssueQuestion to answer
1. Search directionShould the search go forward (from initial state toward goal — data-driven) or backward (from goal toward initial state — goal-driven)?
2. State representationHow should a state be represented so that it is compact, unambiguous, and supports the operators cleanly?
3. Choice of operatorsWhat are the legal moves? Are they reversible? Do they have preconditions?
4. Handling the combinatorial explosionThe state space typically grows exponentially — how do we avoid exploring all of it? (heuristics, pruning, bounding)
5. Knowledge representation and useShould the system use extra knowledge about the problem (heuristics) to guide the search, or search "blindly"?
6. Detecting repeated statesShould the algorithm remember visited states to avoid infinite loops / wasted work, and at what memory cost?

Forward vs Backward Reasoning

Forward searchBackward search
Starts fromInitial stateGoal state
Best whenBranching factor from start is small, or many possible goalsGoal is well-defined and branching factor into the goal is small
ExampleWater jug problem (many operators applicable from start)Theorem proving (work backward from what's to be proved)

The Combinatorial Explosion Problem

If a state has b possible next states (branching factor) and the goal is d steps away, a blind search may examine up to b^d states. Even modest b and d values (say b=10, d=10) yield 10 billion states — this is why AI needs heuristic search (next three lessons) instead of blind enumeration.

Choosing a Good State Representation

A well-designed representation should:

  • Capture everything relevant to the problem, and nothing irrelevant (avoid combinatorial blow-up from unused detail)
  • Make the goal test and operators simple to compute
  • Support any heuristic function the algorithm will need later

Exam tip: "Discuss the issues in the design of a search problem" is a frequently repeated theoretical question — structure your answer around these six issues rather than jumping straight into an algorithm.