Page 51 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 4: Heuristic Search Techniques

can be positioned, either by hand or as a consequence of learning. The following are some Notes
common purpose control approaches (frequently known as weak methods).

 Generate-and-test
 Hill climbing
 Best First Search (A* search)
 Constraint satisfaction
 Means-ends analysis

A heuristic process, or heuristic, is defined as enclosing the following properties:
1. It will typically locate good, although not essential optimum solutions.
2. It is quicker and easier to execute than any recognized exact algorithm (one which guarantees
an optimum solution).
Usually, heuristic search perk up the excellence of the path that are exported. By means of good
heuristics we can expect to acquire good solutions to tough problems like the traveling salesman
problem in less than exponential time. There are a number of good common purpose heuristics
that are valuable in a broad variety of problems. It is also probable to create special purpose
heuristics to resolve specific problems.

Self Assessment

Fill in the blanks:
1. Heuristic techniques are known as ...................................... methods, as they are susceptible
to combinatorial explosion.

2. ...................................... techniques give the frame work into which domain specific
knowledge can be positioned.

4.2 Generate and Test

This is the easiest search strategy. It comprises the following steps:
1. Producing a possible solution for some problems; this means generating a particular
point in the problem space. For others it may be creating a path from a start state.

2. Test to observe if this is really a solution by comparing the chosen point at the end point
of the chosen path to the set of acceptable goal states.
3. If a solution has been found, quit or else return to step 1.

The generate and Test algorithm is a depth first search practice since complete possible solutions
are produced before test. This shows that executed states are likely to emerge frequently in a
tree; it can be implemented on a search graph instead of a tree.
Self Assessment

Fill in the blanks:
3. The .............................. algorithm is a depth first search practice since complete possible
solutions are produced before test.

LOVELY PROFESSIONAL UNIVERSITY 45