可采纳搜索算法最坏复杂度的下确界

THE LOWER BOUND ON THE WORST-CASE COMPLEXITY OF ADMISSIBLE SEARCH ALGORITHMS

本文通过证明可采纳搜索算法的最坏复杂度不可能小于M(M是被搜索图的大小)和可采纳的搜索算法S的最坏复杂度等于M,得出以下结论:可采纳的搜索算法的最坏复杂度的下确界是M。本文还指出了L.Méró关于“无普遍最优算法”的证明中的错误,并给出了新的证明。

After showing that there is no such an admissible algorithm whose, worst-case complexity is less than M (M is the size of the graph searched, namely, M is the number of nodes whose distance to the start node is not greater than f*(s).)and the worst-case complexity of algorithm S is equal to M, we come to the conclusion that the lower bound on the worst-case complexity of admissible search algorithms is M. Some weaknesses in L. Mero's proof of 'No overall Optimal Algorithm Exists' are pointed out and a new proof is proposed.