Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912852514701312 |
|---|---|
| author | Bömer, Thomas Koltermann, Nico Disselnmeyer, Max Amberg, Bastian Meyer, Anne |
| author_facet | Bömer, Thomas Koltermann, Nico Disselnmeyer, Max Amberg, Bastian Meyer, Anne |
| contents | Heuristic functions are essential to the performance of tree search algorithms such as A*, where their accuracy and efficiency directly impact search outcomes. Traditionally, such heuristics are handcrafted, requiring significant expertise. Recent advances in large language models (LLMs) and evolutionary frameworks have opened the door to automating heuristic design. In this paper, we extend the Evolution of Heuristics (EoH) framework to investigate the automated generation of guiding heuristics for A* search. We introduce a novel domain-agnostic prompt augmentation strategy that includes the A* code into the prompt to leverage in-context learning, named Algorithmic - Contextual EoH (A-CEoH). To evaluate the effectiveness of A-CeoH, we study two problem domains: the Unit-Load Pre-Marshalling Problem (UPMP), a niche problem from warehouse logistics, and the classical sliding puzzle problem (SPP). Our computational experiments show that A-CEoH can significantly improve the quality of the generated heuristics and even outperform expert-designed heuristics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_19622 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search Bömer, Thomas Koltermann, Nico Disselnmeyer, Max Amberg, Bastian Meyer, Anne Artificial Intelligence Optimization and Control Heuristic functions are essential to the performance of tree search algorithms such as A*, where their accuracy and efficiency directly impact search outcomes. Traditionally, such heuristics are handcrafted, requiring significant expertise. Recent advances in large language models (LLMs) and evolutionary frameworks have opened the door to automating heuristic design. In this paper, we extend the Evolution of Heuristics (EoH) framework to investigate the automated generation of guiding heuristics for A* search. We introduce a novel domain-agnostic prompt augmentation strategy that includes the A* code into the prompt to leverage in-context learning, named Algorithmic - Contextual EoH (A-CEoH). To evaluate the effectiveness of A-CeoH, we study two problem domains: the Unit-Load Pre-Marshalling Problem (UPMP), a niche problem from warehouse logistics, and the classical sliding puzzle problem (SPP). Our computational experiments show that A-CEoH can significantly improve the quality of the generated heuristics and even outperform expert-designed heuristics. |
| title | Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search |
| topic | Artificial Intelligence Optimization and Control |
| url | https://arxiv.org/abs/2601.19622 |