𝔖 Bobbio Scriptorium
✦   LIBER   ✦

BIDA∗: an improved perimeter search algorithm

✍ Scribed by Giovanni Manzini

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
937 KB
Volume
75
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we present a new bidirectional heuristic search algorithm. Our algorithm can be viewed as a perimeter search algorithm, and it uses a new technique for reducing the number of heuristic evaluations.

We also prove some general results on the behavior of iterative deepening perimeter search algorithms, and we discuss some new "lazy evaluation" techniques for improving their performance.

The theoretical and experimental results show that perimeter search algorithms outperform the other bidirectional algorithms, and we believe it is worthwhile to give them a deep look in subsequent research.

📜 SIMILAR VOLUMES

An improved adaptive string searching al
An improved adaptive string searching algorithm
✍ Z. Liu; X. Du; N. Ishi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 56 KB

Sunday's OM algorithm can reduce the number of character comparisons by making use of information of character distribution in an alphabet. Smith's adaptive algorithm uses dynamic statistics to reduce comparisons, and its performance is close to that of the OM algorithm in the number of character co

An Improved VQ Codebook Search Algorithm
An Improved VQ Codebook Search Algorithm Using Principal Component Analysis
✍ Chin-Chen Chang; Dai-Chuan Lin; Tung-Shou Chen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 532 KB

process of VQ is achieved by using only the indices of the closest codewords for storage and transmission. ## We present an improved codebook search algorithm in this paper. We call it the double test of principal components As is obvious, choosing the closest codeword for each (DTPC). This algor

Improving Greedy Algorithms by Lookahead
Improving Greedy Algorithms by Lookahead-Search
✍ U.K. Sarkar; P.P. Chakrabarti; S. Ghose; S.C. Desarkar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 967 KB

This paper shows that repeated application of a greedy approximation algorithm on some suitably selected subproblems of a problem often leads to a solution which is better than the solution produced by the greedy algorithm applied to the original problem. The lookahead search technique, a polynomial

An improved LLL algorithm
An improved LLL algorithm
✍ Franklin T. Luk; Daniel M. Tracy 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 145 KB

The LLL algorithm has received a lot of attention as an effective numerical tool for preconditioning an integer least squares problem. However, the workings of the algorithm are not well understood. In this paper, we present a new way to look at the LLL reduction, which leads to a new implementation