|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Transforming the Search Space Perhaps
the most important improvement one can make is to restructure the problem
to be solved, making it an easier problem. Macro-operators are
sequences of steps that belong together and can be combined into a single
step, making the search take bigger steps at a time. For example, airplanes
take a series of steps in order to change their orientation and altitude.
A common sequence may be used as a single change of state operator, rather
than using the smaller steps individually. In addition, search and general
problem-solving methods can be greatly simplified if they are reduced
to sub-problems, whose individual solutions are fairly simple. In
the case of path-finding, a map can be broken down into large contiguous
areas whose connectivity is known. One or two border tiles between each
pair of adjacent areas are chosen; then the route is first laid out in
by a search among adjacent areas, in each of which a route is found from
one border point to another.
|
|
|
Features
