Search - contd.

• AI tries to solve two types of problems.
  • not solvable
  • exponential
    • searching
• Generally, if the search space is exponential, you have to choose the search strategy carefully
• breadth first, depth first, uniform cost, depth limited search, iterative deepening search, bidirectional search
• No matter what strategy we use, our program could run forever. But the above search strategies gurantee a solution if you give them enough time
• Heuristic search
  • heuristic function (determines closeness to our goal)
  • expand the node that is closest to the goal
  • may not always work
• Genetic algorithms
  • Write down your search strategy as a series of bits.
  • Use a measure of closeness
  • Randomly try a few search strategies
  • Pick the top few which are the closest to the goal and breed them through mating and occasional mutation
  • A significant departure from previous strategies
  • Does not have systematic approach
  • It is possible that we will never get the solution
• There are obvious flaws with genetic algorithm strategy. But it is trying to solve a problem that cannot be solved in reasonable amount of time.
• Just because you have combined top half of one and bottom half of the other and just to cover your bet you also did vice versa, doesn't mean that you will have atleast one of the new genes which is superior. Many of the features are not independent.
• You have to try the genetic algorithm to a problem before concluding whether it is good or not good
• You can never prove that genetic algorithm is not a good solution. There are far too many breeding strategies.