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?