ECCC-Report TR96-044https://eccc.weizmann.ac.il/report/1996/044Comments and Revisions published for TR96-044en-usThu, 20 Mar 1997 00:00:00 +0200
Revision 1
| Optimal Search in Trees Revision of: TR96-044 |
Yosi Ben-Asher,
Eitan Farchi,
Ilan Newman
https://eccc.weizmann.ac.il/report/1996/044#revision1
It is well known that the optimal solution for
searching in a finite total order set is binary search.
In binary search we divide the set into two ``halves'' by querying the middle
element and continue the search on the suitable half.
What is the equivalent of binary search when
the set $P$ is partially ordered?
A query in this case is to a point $x\in P$, with
two possible answers: 'yes', indicates that the required element
is ``below'' $x$, or 'no' if the element is not bellow $x$.
We show that the problem of computing an optimal strategy
for search in Posets that are tree-like (or forests) is
polynomial in the size of the tree, and requires at most $O(n^4\log^3 n)$ steps.
Optimal solutions of such search problems are often
needed in program testing and debugging,
where a given program is represented as a tree
and a bug should be found using a minimal set of queries.
This type of search is also applicable in searching
classified large tree-like data bases (e.g. the Internet).
Thu, 20 Mar 1997 00:00:00 +0200https://eccc.weizmann.ac.il/report/1996/044#revision1
Paper TR96-044
| Optimal Search in Trees |
Yosi Ben-Asher,
Ilan Newman
https://eccc.weizmann.ac.il/report/1996/044It is well known that the optimal solution for
searching in
a finite total order set is the binary search.
In the binary search we
divide the set into two ``halves'', by querying the middle
element, and continue the search on the suitable half.
What is the equivalent of binary search, when
the set $P$ is partially ordered?
A query in this case is to a point $x\in P$, with
two possible answers: 'yes', indicates that the required element
is ``below'' $x$, or 'no' if the element is not bellow $x$.
We show that the problem of computing an optimal strategy
for search in Posets that are tree-like (or forests) is
polynomial in the size of
the tree, and requires at most $O(n^2\log^2 n)$ steps.
Optimal solutions of such search problems are often
needed in program testing and debugging,
where a given program is represented as a tree
and a bug should be found using a minimal set of queries.
Mon, 26 Aug 1996 12:05:18 +0300https://eccc.weizmann.ac.il/report/1996/044