  Let h be a probability measure on the nodes and arcs of a network Q, viewed
either as the location of a hidden object to be found or as the continuous
distribution of customers receiving packages. We wish to find a trajectory
starting from a specified root, or depot O that minimizes the expected search
or delivery time. We call such a trajectory optimal. When Q is a tree, we ask
for which h there is an optimal trajectory that is depth-first, and we find
sufficient conditions and in some cases necessary and sufficient conditions on
h. A consequence of our analysis is a determination of the optimal depot
location in the Delivery Man Problem, correcting an error in the literature. We
concentrate mainly on the search problem, with the Delivery Man Problem arising
as a special case.

Optimization and Control