Problem Reduction

Sometimes problems only seem hard to solve.
?A hard problem may be one that can be reduced to a number of simple problems...and, when each of the simple problems is solved, then the hard problem has been solved.
?This is the basic intuition behind the method of problem reduction.
If we are looking for a sequence of actions to achieve some goal, then one way to do it is to use state-space search, where each node in you search space is a state of the world, and you are searching for a sequence of actions that get you from an initial state to a final state.
Another way is to consider the different ways that the goal state can be decomposed into simpler sub-goals.
?For example, when planning a trip to London you probably don t want to search through all the possible sequences of actions that might get you to London.
?You re more likely to decompose the problem into simpler ones - such as getting to the station, then getting a train to London.
There may be more than one possible way of decomposing the problem - an alternative strategy might be to get to the airport, fly to Heathrow, and get the tube from Heathrow into London.
?These different possible plans would have different costs (and benefits) associated with them, and you might have to choose the best plan.
The Simple State-space Search Techniques Described In The Above Slides Could All Be Represented Using A Tree Where Each Successor Node Represents An Alternative Action To Be Taken.
?The Graph Structure Being Searched Is Referred To As An Or Graph.
?In Or Graph We Want To Find A Single Path To A Goal.