𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An upper bound on the time complexity of iterative-deepening-A*

✍ Scribed by Brian G. Patrick; Mohammed Almulla; Monroe M. Newborn

Publisher
Springer Netherlands
Year
1992
Tongue
English
Weight
704 KB
Volume
5
Category
Article
ISSN
1012-2443

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Time complexity of iterative-deepening-A
Time complexity of iterative-deepening-Aβˆ—
✍ Richard E. Korf; Michael Reid; Stefan Edelkamp πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 178 KB

We analyze the time complexity of iterative-deepening-A \* (IDA \* ). We first show how to calculate the exact number of nodes at a given depth of a regular search tree, and the asymptotic brute-force branching factor. We then use this result to analyze IDA \* with a consistent, admissible heuristic

A probabilistic upper bound for the edge
A probabilistic upper bound for the edge identification complexity of graphs
✍ Eberhard Triesch πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 344 KB

Given a finite graph G=( V, E), what is the minimum number c(G) of incidence tests which are needed in the worst case to identify an unknown edge e\*EE? The number c(G) was first studied by Aigner and Triesch (1988), where it was shown that for almost all graphs in the random graph model where d(n)