A correction to “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: 1995
• Tongue: English
• Weight: 229 KB
• Volume: 77
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(95)00089-w

✦ Synopsis

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 exists iterative deepening search strategies that are optimal for an agent searching on a line, for an agent searching on m-concurrent rays and for an agent searching on an uniform b-q tree. The third result happens to be the major result in the paper (and hence the name of the paper follows from it).

The correction relates only to the second result where we had claimed that there exists an iterative deepening strategy which is optimal for an agent searching on m-concurrent rays. In a personal communication to us, it has been pointed out by Professor Amitava Bagchi of the Indian Institute of Management, Calcutta, that there appears to be an oversight in the proof of this result. Further investigation reveals an interesting property of this problem--there can be no iterative deepening strategy which is optimul for an agent searching in m-concurrent rays except when m = 2. The special case of m = 2 establishes the first result, that is, when the agent is searching on a line.

In this paper, we establish two results: l We first show that the iterative deepening strategy presented in [2] for an agent searching in m-concurrent rays is actually 1.58 times optimal in the worst case (rather than being optimal). This corrects our previous oversight. l We then establish that there is no iterative deepening strategy which is optimal for an agent searching in m-concurrent rays except when m = 2. The best iterative deepening strategy is 1.47 times optimal in the worst case.