Artificial Intelligence (CS607)
© Copyright Virtual University of Pakistan
Lecture No. 11-13
35 Discussion on Problem Solving
In the previous chapter we studied problem solving in general and elaborated on
various search strategies that help us solve problems through searching in
problem trees. We kept the information about the tree traversal in memory (in the
queues), thus we know the links that have to be followed to reach the goal. At
times we don’t really need to remember the links that were followed. In many
problems where the size of search space grows extremely large we often use
techniques in which we don’t need to keep all the history in memory. Similarly, in
problems where requirements are not clearly defined and the problem is ill-
structured, that is, we don’t exactly know the initial state, goal state and operators
etc, we might employ such techniques where our objective is to find the solution
not how we got there.
Another thing we have noticed in the previous chapter is that we perfrom a
sequential search through the search space. In order to speed up the techniques
we can follow a parallel approach where we start from multiple locations (states)
in the solution space and try to search the space in parallel.
36 Hill Climbing in Parallel
Suppose we were to climb up a hill. Our goal is to reach the top irrespective of
how we get there. We apply different operators at a given position, and move in
the direction that gives us improvement (more height). What if instead of starting
from one position we start to climb the hill from different positions as indicated by
the diagram below.
In other words, we start with different independent search instances that start
from different locations to climb up the hill.
Further think that we can improve this using a collaborative approach where
these instances interact and evolve by sharing information in order to solve the
problem. You will soon find out that what we mean by interact and evolve.