[Solved]: Neighbourhood in local search metaheuristic

Problem Detail: 

I cannot seem to find an answer to this question with Google, so I am going to ask here: is it required for a good neighbourhood function that it in principle (i. e. by recursively considering all neighbours of a certain solution - which is not practical) can reach all possible solutions?

My question is whether there are references in literature that explicitely state it's a requirement - I can see that it is a good property of a neighbourhood.

Asked By : Florian Mayer

Answered By : Juho

I think the property of being able to reach all the successor states from a current state is crucial and needed in order for the problem to be well-defined. If this was not the case, you might miss out on good solutions. Moreover, you might never reach a goal state and hence run forever.

The classic AI book by Russell & Norvig, 3rd edition, page 67 gives a formal definition for a problem. One of the components is a successor function which returns all the successor states for a current state. Together the formal components create a search space, that is the set of all states reachable from the initial state. If one uses a different successor function, namely such that it leaves out some successors, the resulting search space is a different one: goal state(s) might be missing and optimal solutions might very well differ. Perhaps the reason you are unable find it from the literature is that the requirement is obvious.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2501

3.2K people like this

 Download Related Notes/Documents