In many problems, however the path to the goal is irrelevant, e.g. in the 8 queen problem, what matters is the final configuration of queens, not the order in which they are dded. This class of problems includes many important applications such as integrated – circuit design, factory – floor layout, job – shop scheduling, automatic programming, telecommunications network optimization vehicle routing and portfolio management..

If the path to the goal does not matter, we might consider a different class of algo, ones that do not worry about paths at all. Local search algo operates using a single current state and generally move only to neighbors of that state. They are not systematic.

Advantages.

1] They use very little memory – usually a constant amount.

2] They can often find reasonable solutions in large or infinite (continuous) state spaces for which systematic algorithms are unsuitable.

Local algo, are useful for solving pure optimizatior problems, in which the aim is to find the best state according to an objective functions.

To understand local search, we will fin it very useful to consider the state space. Landscape.

A landscape has both “location” and “elevation”

Location – Defined by the state

Elevation – Defined by the value of the heuristic cost function or objective function

Global minimum – If elevation correspond to cost, then the aim is to find the lowest valley.

Global maximum – If the elevation corresponds to an objective function, then the aim is to find the highest peak.

Local search algo, explore this landscape. A complete local search algo always finds a goal if one exists, an optimal algo. Always finds a global minimum/maximum.

Figure above, describes A one – dimensional state space landscape in which elevation corresponds to the objective function. The aim is to find the global maximum. Hill-climbing search modifies the current state to try to improve it, as shown by the arrow. The various topographic features are defined in the test.