摘要 : We consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to f... 展开 We consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not exist in general. On the other hand, we provide a formula for the cost of clearing complete graphs. From our construction it follows that an ideal search strategy of a complete graph does exist and can be calculated efficiently. For general graphs G we give a polynomial-time O(log n)-approximation algorithm for finding minimum cost search strategies. We also prove that recontamination does not help to obtain minimum cost edge search strategies. 收起