Local search
Local search is an optimization technique that iteratively modifies a candidate solution by exploring neighboring alternatives according to an improvement rule.
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 →
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.
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.
- hillclimbingincludes · Hill climbing is an iterative local-search technique that moves from a candidate solution to a neighboring solution with a better objective value.
- knowledge graphuses · A knowledge graph is a graph-structured representation of entities and their semantically meaningful relationships, often including associated attributes or facts.
- global searchcontrasts with · A search strategy that explores broadly across the search space to seek a global optimum rather than concentrating only near one current solution.
- Cypheruses · Cypher is a declarative graph query language for expressing patterns and retrieving, creating, or modifying property-graph data.
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.