Search Techniques


INFORMED SEARCH

When more information than the initial state, the operators, and the goal available, the size of the search space can usually be constrained. When this is the case, the better the information available, the more efficient the search process will be. Such methods are known as informed search methods. They often depend on the use of heuristic information.

Heuristic Information

Q. Describe briefly the following A.I. technique:
Heuristics (June 99, June 02, June 03)

Ans. Heuristic is a rule of thumb or judgmental technique that leads to a solution some of the time but provides no guarantee of success. It may in fact end in failure. Heuristic are usually acquired with much experience. For example, in locating a fault in a TV set, an experienced technician will not start by making numerous voltage checks when it is clear that the sound is present but the picture is not, but instead will immediately reason that the high voltage flyback transformer or related component is the culprit. This type of reasoning may not always be correct, but it frequently is, and then leads to a quick solution.

Heuristics play an important role in search strategies because of the exponential nature of most problems. They help to reduce the number of alternatives from an exponential number to a polynomial number and, thereby, obtain in a tolerable amount of time. When exhaustive search is impractical, it is necessary to compromise for a constrained search which eliminates many paths but offers the promise of success some of the time.

Informed Search methods

Q. Enumerate various informed search methods used in AI. What do you understand by 'Heuristics'? What is the role of 'Heuristics' in informed search? (Jan. 01, June 03)

Ans. Various informed search methods used in AI are listed below:

  • Hill Climbing Methods
  • Best-First Search
  • Branch-and-Bound Search
  • A* Search

Please refer to the previous question for more info.

 
          AI Contents  
©Universal Teacher Publications Web: www.universalteacherpublications.com.