Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version)

• URL: http://arxiv.org/abs/2408.08227v1
• Date: Thu, 15 Aug 2024 15:54:25 GMT
• Title: Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version)
• Authors: Carlos Linares López, Ian Herman,
• Abstract summary: This paper introduces a new search algorithm with the same time complexity, which results from a natural evolution of A* thus, it preserves all its interesting properties. Experiments in various testbeds show a significant improvement in performance over the state of the art, often by one or two orders of magnitude.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of finding the shortest path in a graph G(V, E) has been widely studied. However, in many applications it is necessary to compute an arbitrary number of them, k. Even though the problem has raised a lot of interest from different research communities and many applications of it are known, it has not been addressed to the same extent as the single shortest path problem. The best algorithm known for efficiently solving this task has a time complexity of O (|E| + |V|log{|V|}+k|V|)$ when computing paths in explicit form, and is based on best-first search. This paper introduces a new search algorithm with the same time complexity, which results from a natural evolution of A* thus, it preserves all its interesting properties, making it widely applicable to many different domains. Experiments in various testbeds show a significant improvement in performance over the state of the art, often by one or two orders of magnitude.

Related papers

• Pathfinding with Lazy Successor Generation [12.02023514105999]
  We study a pathfinding problem where only locations are given, and edges are implicitly defined. Despite its simple structure, this problem becomes non-trivial with a massive number of locations. We propose a novel LaCAS* algorithm, which does not generate successors all at once but gradually generates successors as the search progresses.
  arXiv  Detail & Related papers  (2024-08-27T23:25:25Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy.
  arXiv  Detail & Related papers  (2024-02-01T09:18:34Z)
• Enhanced Methods for the Weight Constrained Shortest Path Problem [18.567812400186092]
  The Weight Constrained Shortest Path Problem (WCSPP) is a well-studied, yet challenging, topic in AI. This paper presents two new solution approaches to the WCSPP on the basis of A* search. We empirically evaluate the performance of our algorithms on a set of large and realistic problem instances.
  arXiv  Detail & Related papers  (2022-07-29T15:32:45Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem. We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
  arXiv  Detail & Related papers  (2021-12-06T20:34:55Z)
• Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
  Path finding is a well-studied problem in AI, which is often framed as graph search. We present two algorithms, grounded in the same idea, that can obtain provably optimal solutions to the considered problem.
  arXiv  Detail & Related papers  (2021-04-14T07:59:53Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  We introduce an efficient algorithm for finding sparse permutations of a directed acyclic graph. We show that our method with depth $w$ runs in $O(pw+3)$ time. We also compare our algorithm to provably consistent causal structure learning algorithms, such as the PC algorithm, GES, and GSP, and show that our method achieves comparable performance with a shorter runtime.
  arXiv  Detail & Related papers  (2020-11-06T21:56:41Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.