2
$\begingroup$

I'm working my way through parts of Russell and Norvig's AIMA book for a class, and there's something I've never quite managed to wrap my head around. Chapters 3 and 4 contrast 'search' methods with 'local search' optimization methods, suggesting to me that there is some kind of fundamental difference between the two. Here's what I currently understand:

Search algorithms work on graph representations of state space. The idea is to find the least-cost path from an initial state to the goal state. By contrast, local search solves optimization problems by starting from some initial state and moving to the best neighbour at each step, choosing whichever transition is locally optimal, until it reaches the desired global optimum (or runs out of resources). It does not keep track of the path to the current state.

A lot seems to be made of this last fact, but it seems to me that this is merely an artefact of the problem formulation. The fact that we're keeping track of the path to the current state in e.g. Dijkstra's algorithm is a consequence of defining the states to be the nodes in the graph. If instead we consider the state space to consist of all paths to the goal, then we don't have to keep track of the path, and this 'search' simply becomes an ordinary optimization problem.

Conversely, if we take the example of the 8 queens problem, the fact that a solution is an optimal state instead of a path is an arbitrary choice. To wit, we can equivalently build a graph consisting of representations of possible movements of 1 piece from an initial configuration (e.g. $(0, \dots, L, \dots, 0)$ for move $i$-th piece left), and then the solution would essentially be a path (more precisely the configuration obtained by following this path from an initial position).

Is there any fundamental distinction (i.e. not a consequence of arbitrary problem framing) between search and local search? If not, can Dijkstra's algorithm be considered to simply be global optimization algorithm?

$\endgroup$

1 Answer 1

1
$\begingroup$

A representation where the state space is all paths to the goal is completely unusable. It blows up the state space exponentially large. And it loses the structure that algorithms like A* make good use of.

Yes, search in a graph is an optimization problem, and you could certainly view it from that perspective, and use any optimization algorithm you want. But it is an optimization problem that comes with some special structure, and many graph search algorithms make use of that special structure. This is not unusual in optimization: if we have a kind of optimization problem with some special structure, sometimes we can find custom algorithms that a specialized to that situation and that perform better than general-purpose optimization algorithms on problems with that structure.

For me, the interesting bit about search in graphs is not that we keep track of paths (many graph search algorithms don't keep track of paths), but that it is an optimization problem that has some special structure that can be exploited to construct better algorithms.

$\endgroup$
5
  • $\begingroup$ But that's an implementation-level statement rather than a conceptual one, right? $\endgroup$ Jun 16, 2022 at 18:06
  • $\begingroup$ @OthmanElHammouchi, well, I think ability to make use of the structure of the space is more than an implementation-level issue. $\endgroup$
    – D.W.
    Jun 16, 2022 at 18:18
  • $\begingroup$ that happens a lot in optimization, e.g. when the solution is known to be convex, but we don't consider these special cases to be their own 'discipline' $\endgroup$ Jun 16, 2022 at 18:43
  • 1
    $\begingroup$ @OthmanElHammouchi, see my edited answer for additional commentary that might partly address your comments. There is no technical criteria for something being its own discipline and I wouldn't worry too much about that. Often in computer science we take a pragmatic perspective. What constitutes a "discipline" is largely a social matter, more than a technical matter. $\endgroup$
    – D.W.
    Jun 16, 2022 at 18:58
  • $\begingroup$ thank you very much for your answer. I come from a math background, so I fear I'm cursed with the need find neat theoretical explanations for existing categories. $\endgroup$ Jun 16, 2022 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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