Rectangle Search: An Anytime Beam Search (Extended Version)
- URL: http://arxiv.org/abs/2312.12554v1
- Date: Tue, 19 Dec 2023 19:50:45 GMT
- Title: Rectangle Search: An Anytime Beam Search (Extended Version)
- Authors: Sofia Lemons, Wheeler Ruml, Robert C. Holte, Carlos Linares L\'opez
- Abstract summary: Anytime search algorithms try to find a (potentially suboptimal) solution as quickly as possible.
We propose a new algorithm, rectangle search, that is instead based on beam search.
- Score: 9.59799149404787
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Anytime heuristic search algorithms try to find a (potentially suboptimal)
solution as quickly as possible and then work to find better and better
solutions until an optimal solution is obtained or time is exhausted. The most
widely-known anytime search algorithms are based on best-first search. In this
paper, we propose a new algorithm, rectangle search, that is instead based on
beam search, a variant of breadth-first search. It repeatedly explores
alternatives at all depth levels and is thus best-suited to problems featuring
deep local minima. Experiments using a variety of popular search benchmarks
suggest that rectangle search is competitive with fixed-width beam search and
often performs better than the previous best anytime search algorithms.
Related papers
- Hybrid Search for Efficient Planning with Completeness Guarantees [63.02803974708516]
We propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces.
This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search.
arXiv Detail & Related papers (2023-10-19T15:16:43Z) - On the Depth between Beam Search and Exhaustive Search for Text
Generation [3.726173629675064]
Beam search is limited in both search width and depth, whereas exhaustive search is a global search that has no such limitations.
We introduce Lookahead Beam Search (LBS), a multi-step lookahead search that optimize the objective considering a fixed number of future steps.
LBS outperforms beam search overall on machine translation tasks.
arXiv Detail & Related papers (2023-08-25T22:57:53Z) - Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
We propose a deterministic search algorithm balancing both quality and diversity.
The proposed algorithm is parameter-free, lightweight, efficient, and easy to use.
arXiv Detail & Related papers (2022-11-22T00:26:13Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
In this paper, we build the search algorithm upon a complicated search space with long-distance connections.
We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks.
In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
arXiv Detail & Related papers (2021-12-05T06:42:48Z) - A Meta-Heuristic Search Algorithm based on Infrasonic Mating Displays in
Peafowls [0.0]
Simplistic methods such as exhaustive search become computationally expensive and unreliable as the solution space for search algorithms increase.
This research proposes an Infrasonic Search Algorithm, inspired from the Gravitational Search Algorithm and the mating behaviour in peafowls.
arXiv Detail & Related papers (2021-06-28T09:04:51Z) - 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) - Quantum Search with Prior Knowledge [15.384459603233978]
We propose a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting.
We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.
arXiv Detail & Related papers (2020-09-18T09:50:33Z) - Searching for a Search Method: Benchmarking Search Algorithms for
Generating NLP Adversarial Examples [10.993342896547691]
We study the behavior of several black-box search algorithms used for generating adversarial examples for natural language processing (NLP) tasks.
We perform a fine-grained analysis of three elements relevant to search: search algorithm, search space, and search budget.
arXiv Detail & Related papers (2020-09-09T17:04:42Z) - Best-First Beam Search [78.71330480725668]
We show that the standard implementation of beam search can be made up to 10x faster in practice.
We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
arXiv Detail & Related papers (2020-07-08T05:56:01Z) - 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)
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.