✦ LIBER ✦

On the complexity of admissible search algorithms

✍ Scribed by Alberto Martelli

Publisher: Elsevier Science
Year: 1977
Tongue: English
Weight: 788 KB
Volume: 8
Category: Article
ISSN: 0004-3702
DOI: 10.1016/0004-3702(77)90002-9

No coin nor oath required. For personal study only.

✦ Synopsis

This paper analyzes the complexity of heuristic search algorithms, Le. algorithms which find the shortest path in a graph by using an estimate to guide the search. In particular, .algorithm A*, due to Hart, Nilsson and Raphael, is shown to require 0(2 ~) steps, in the worst cdse, for searching a graph with N nodes, if the so called "consistency assumption" does not hold for the estimate. Furthermore, a new search algorithm is presented which runs in O(N 2) steps in the worst case and which never requires more steps than A*.

📜 SIMILAR VOLUMES

On the Complexity of Exclusion Algorithm

On the Complexity of Exclusion Algorithms for Optimization

✍ Eugene Allgower; Melissa Erdmann; Kurt Georg 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 133 KB

Exclusion algorithms are a well-known tool in the area of interval analysis for finding all solutions of a system of nonlinear equations or for finding the global minimum of a function over a compact domain. The present paper discusses a new class of tests for such algorithms in the context of globa

The Complexity and Effectiveness of Pred

The Complexity and Effectiveness of Prediction Algorithms

✍ Boris Ya. Ryabko 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 523 KB

The Greedy Search Algorithm on Binary Ve

The Greedy Search Algorithm on Binary Vectors

✍ Avner Dor 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 185 KB

The Relative Complexity of NP Search Pro

The Relative Complexity of NP Search Problems

✍ Paul Beame; Stephen Cook; Jeff Edmonds; Russell Impagliazzo; Toniann Pitassi 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 521 KB

Papadimitriou introduced several classes of NP search problems based on combinatorial principles which guarantee the existence of solutions to the problems. Many interesting search problems not known to be solvable in polynomial time are contained in these classes, and a number of them are complete

On the fast search algorithms for vector

On the fast search algorithms for vector quantization encoding

✍ Wen-Shiung Chen; Lili Hsieh; Shang-Yuan Yuan 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract One of the major difficulties arising in vector quantization (VQ) is high encoding time complexity. Based on the well‐known partial distance search (PDS) method and a special order of codewords in VQ codebook, two simple and efficient methods are introduced in fast full search vector qu

On the complexity of branch-and-bound se

On the complexity of branch-and-bound search for random trees

✍ Luc Devroye; Carlos Zamora-Cura 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co