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

被引：6

作者：

张伟

俞瑞钊

何志均

机构：

[1] 浙江大学人工智能研究所

来源：

计算机学报 | 1990年 / 06期

关键词：

搜索图; 序列; 搜索算法; 下确界; 最大下界; 复杂度;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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

引用

收藏

页码：449 / 455

页数：7

相关论文

共 1 条

[1] 一个线性的启发式图搜索算法 [J].

张伟 ;

俞瑞钊 ;

何志均 .

信息与控制, 1988, (02) :1-6