✦ LIBER ✦

Agent searching in a tree and the optimality of iterative deepening

✍ Scribed by Pallab Dasgupta; P.P. Chakrabarti; S.C. DeSarkar

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 695 KB
Volume: 71
Category: Article
ISSN: 0004-3702
DOI: 10.1016/0004-3702(94)90066-3

No coin nor oath required. For personal study only.

✦ Synopsis

The agent searching framework models the effort of a search strategy in terms of the distance traversed by an agent while exploring the search space. The framework has been found to be useful in modeling search problems where the cost of backtracking and retracing search paths is important in determining search complexity. In this paper we show that depth-first iterative deepening (DFID) strategies are optimal for an agent searching in a line, in m concurrent rays, and in uniform b-ary trees. In the conventional search model it is known that DFID is asymptotically optimal for uninformed search of uniform b-ary trees. In this paper we prove the stronger result that for agent searching in uniform b-ary trees, iterative deepening is optimal up to lower-order terms. We also discuss the problems involved in optimally performing agent search in a graph.

📜 SIMILAR VOLUMES

A correction to “Agent searching in a tr

A correction to “Agent searching in a tree and the optimality of iterative deepening”

✍ Pallab Dasgupta; P.P. Chakrabarti; S.C. DeSarkar 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 229 KB

This paper contains a correction to one of the results presented in an earlier work [ 21 and establishes a new result in that direction. In the paper entitled "Agent searching in a tree and the optimality of iterative deepening" [2] we had presented three independent results, namely that there exist

The optimal location of a path or tree i

The optimal location of a path or tree in a tree network

✍ Edward Minieka 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 610 KB

This article describes methods for finding an optimal location for a path-shaped or tree-shaped facility of a specified size in a tree network. Four optimization criteria are examined: minimizing distancesum, minimizing eccentricity, maximizing distancesum, and maximizing eccentricity.

The optimal distribution of a tree in a

The optimal distribution of a tree in a finite set

✍ A.V. Panyukov; B.V. Pel'tsverger 📂 Article 📅 1988 🏛 Elsevier Science ⚖ 219 KB

In Search of the Canary Tree: the Story of a Scientist, a Cypress, and a Changing World

✍ Oakes, Lauren E. 📂 Fiction 📅 2018 🏛 Basic Books 🌐 English ⚖ 898 KB 👁 3 views

The surprisingly hopeful story of one woman's search for resiliency in a warming world Several years ago, ecologist Lauren E. Oakes set out from California for Alaska's old-growth forests to hunt for a dying tree: the yellow-cedar. With climate change as the culprit, the death of this species meant

In Search of the Canary Tree: The Story

In Search of the Canary Tree: The Story of a Scientist, a Cypress and a Changing World

✍ Lauren E. Oakes 📂 Fiction 📅 2018 🏛 Basic Books 🌐 English ⚖ 2 MB 👁 3 views

**The surprisingly hopeful story of one woman's search for resiliency in a warming world** Several years ago, ecologist Lauren E. Oakes set out from California for Alaska's old-growth forests to hunt for a dying tree: the yellow-cedar. With climate change as the culprit, the death of this species

Construction of a tree from its traversa

Construction of a tree from its traversals in optimal time and space

✍ Arne Andersson; Svante Carlsson 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 430 KB