2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So why is it not sufficient to require that the/an optimal solution is reachable? Excluding large parts of the state space seems to be an advantage! $\endgroup$ – Raphael♦ Jun 27 '12 at 12:50
  • $\begingroup$ @Raphael It is a different thing to be able to reach a state and to exclude it, i.e. not visit it. In other words, not every state has to be generated and/or stored explicitly even if it can be reached. For your first point: how do you do it when you don't know how to reach the goal state(s)? Isn't that the whole point of a search problem? $\endgroup$ – Juho Jun 27 '12 at 12:56
  • $\begingroup$ Who talks about checking whether the optimum is reachable? I am just saying that this is the important condition for the problem, not that all neighbours are reachable. $\endgroup$ – Raphael♦ Jun 27 '12 at 12:58
  • $\begingroup$ Ofcourse it is better the smaller the search space is. It is not the job of successor function to reduce it, though. Different pruning techniques and heuristics guiding the search take care of that. I just think it is plain silly to use a successor function that isn't able to reach every state, even in principle. $\endgroup$ – Juho Jun 27 '12 at 13:01
  • $\begingroup$ You may find it silly, but it is certainly allowed. $\endgroup$ – Raphael♦ Jun 27 '12 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.