Priority queues are one of the most fundamental and widely used data
structures in computer science. Their primary objective is to efficiently
support the insertion of new elements with assigned priorities and the
extraction of the highest priority element. In this study, we investigate the
design of priority queues within the learning-augmented framework, where
algorithms use potentially inaccurate predictions to enhance their worst-case
performance. We examine three prediction models spanning different use cases,
and show how the predictions can be leveraged to enhance the performance of
priority queue operations. Moreover, we demonstrate the optimality of our
solution and discuss some possible applications.

研究目标是在学习增强框架中设计优先队列，利用预测提高优先队列操作的性能，同时证明解决方案的最优性和讨论一些可能的应用。

学习增强优先级队列

Learning-Augmented Priority Queues

The classic problem of \textit{constrained path finding} is a well-studied
but yet challenging topic in AI with a broad range of applications in various
areas such communication and transportation. The Weight Constrained Shortest
Path Problem (WCSPP), as the base form of constrained path finding with only
one side constraint, aims to plan a cost optimum path whose weight/resource
usage is limited. Given the bi-criteria nature of the problem (i.e., dealing
with cost and weight of paths), methods addressing the WCSPP have some common
properties with bi-objective search. This paper leverages the recent
state-of-the-art A*-based techniques in both constrained path finding and
bi-objective search and presents two exact solution approaches to the WCSPP,
both capable of solving hard problem instances on very large graphs. We
empirically evaluate the performance of our algorithms on a new set of large
and realistic problem instances and show their advantages over the
state-of-the-art algorithms in both time and space metrics. This paper also
investigates the importance of priority queues in constrained search with A*.
We show with extensive experiments on both realistic and randomised graphs how
bucket-based queues without tie-breaking can effectively improve the
algorithmic performance of exhaustive bi-criteria searches.

本文研究基于 A * 算法和双目标搜索的两种解决方案，解决只有一个约束条件的成本最小路径规划问题，并研究在约束搜索中优先队列的重要性。实验证明，不带打结断的桶队列可以有效提高双目标搜索的算法性能。