Local search
Local search is an optimization technique that iteratively explores neighboring candidate solutions to find an improved solution according to an objective or constraint measure.
Advanced Algorithms and Data Structures
Local search is an optimization technique that iteratively improves a candidate solution through nearby modifications.
- How it is used
- Improves candidate solutions by exploring their neighborhoods instead of searching the entire solution space.
- How deep it goes
- Develops random improvement steps and compares neighborhood sizes, but gives no fixed complexity bound for local search.
- Examples
- Uses graph-drawing crossings, traveling-salesperson tour swaps, and a mixed transition function to illustrate candidate moves.
- What you can do after
- Build it from scratch by defining candidate moves and a cost check, then evaluating how move range affects results.
Read how Advanced Algorithms and Data Structures explains local search →
Applied Reinforcement Learning
Local search is an optimization technique that iteratively improves a candidate solution by examining nearby solutions.
- How it is used
- Refines candidate vehicle routes after Monte Carlo tree search simulations and improves the final best solution.
- How deep it goes
- Describes 2-opt segment reversal and repeated distance comparisons, without detailing broader local-search variants.
- Examples
- Demonstrates reversing C2 and C3 in a depot route to remove a crossing and potentially reduce distance.
- What you can do after
- Apply 2-opt to refine vehicle routes by retaining segment reversals that reduce distance.
Read how Applied Reinforcement Learning explains local search →
Optimization Algorithms: AI techniques for design, planning, and control problems
A local search algorithm iteratively moves from a feasible solution to a neighboring solution according to an improvement rule.
- How it is used
- Uses nearby solution changes to improve feasible candidates while exploiting a limited region of the search space.
- How deep it goes
- Defines neighborhoods and gives an iterative improvement procedure, but stops short of guaranteeing a global optimum.
- Examples
- Uses resort restaurant selection and a pseudocode loop of feasible starts, local moves, improvement checks, and termination.
- What you can do after
- Apply local search by defining feasible solutions, neighborhood moves, an improvement rule, and termination criteria.
Essential GraphRAG
Local search is a GraphRAG retrieval method that combines information from entities and their nearby graph structure with related source-text passages.
- How it is used
- Answers entity-focused queries during the graph-retriever stage by combining vector similarity with graph traversal.
- How deep it goes
- Implements embeddings, vector indexing, Cypher expansion, context limits, and LLM generation, while contrasting local with global retrieval.
- Examples
- Uses chamomile and Ulysses questions, entity embeddings, a Neo4j vector index, and Cypher retrieval statements.
- What you can do after
- Build it from scratch by embedding entities, querying a vector index, expanding graph context, and generating an LLM response.
Also covered in
- Quantum Programming in Depth
- Domain-Specific Small Language Models
- Architecture Modernization: Socio-technical alignment of software, strategy, and structure
What to know first
- combinatorial optimizationCombinatorial optimization is the process of selecting an optimal configuration, assignment, subset, or permutation from a finite or discrete set of possibilities.
- convergenceConvergence is the process or property by which an iterative or changing system approaches a stable result, limiting state, or mutual consistency.
- graphA graph is a mathematical structure consisting of vertices and edges that connect pairs of vertices to represent relationships or connections.
- local optimumA local optimum is a feasible point whose objective value is no worse than that of sufficiently nearby feasible points, though a better point may exist elsewhere.
Related concepts
- tabu searchused by · Tabu search is a memory-guided local search technique that restricts recently used moves or solutions to discourage cycling and escape local optima.
- hill climbingincludes · Hill climbing is an iterative local-search optimization method that repeatedly moves from a candidate solution to a better neighboring solution.
- knowledge graphuses · A knowledge graph is a graph-structured representation of entities and their semantically meaningful relationships, often including associated attributes or facts.
- brute-force searchcontrasts with · Brute-force search is a search technique that systematically evaluates candidates in a defined search space, typically examining all possibilities without using selective shortcuts to narrow the search.
- Cypheruses · Cypher is a declarative graph query language for expressing patterns and retrieving, creating, or modifying property-graph data.
Questions about local search
What is local search?
Local search is an optimization technique that iteratively explores neighboring candidate solutions to find an improved solution according to an objective or constraint measure.
Which Manning books explain local search?
Advanced Algorithms and Data Structures, Applied Reinforcement Learning, Optimization Algorithms: AI techniques for design, planning, and control problems and Essential GraphRAG.
What should I know before learning local search?
Manning books that teach local search usually introduce combinatorial optimization, convergence, graph and local optimum first.
What is the difference between local search and brute-force search?
Local search is an optimization technique that iteratively explores neighboring candidate solutions to find an improved solution according to an objective or constraint measure. Brute-force search is a search technique that systematically evaluates candidates in a defined search space, typically examining all possibilities without using selective shortcuts to narrow the search.
What kinds of local search are there?
Kinds of local search include hill climbing.
What is local search a kind of?
Local search is a kind of exploitative algorithm. A search algorithm that primarily focuses on promising regions containing previously found good solutions.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.



