摘要：提出粗等价类融合禁忌搜索的最小约简完备算法．首先用全局等价类替换元组作为基本计算单位，给出3类粗等价类定义，结合00粗等价类在约简的渐增式计算中递减至空的性质，推导出求正区域的等价方法，并设计求解中双向缩减计算域的优化策略，从而提供快速求初始解、验证解等基础算法；然后面向约简特性设计禁忌搜索下的多种策略，包括双向邻域搜索、藐视准则、有限随机搜索、有限解检验等，最后给出高效的最小约简完备算法．用UCI中20个决策表、KDDCup海量数据集从多个性能指标进行验证，实验结果证明粗等价类理论和禁忌搜索从双方面保证本文算法的完备和高效性，大多数情况下可有效求得最小约简，并在跳出局部最优解、收敛速度和处理海量数据效率等方面优于现有算法．

关键词：最小约简 粗等价类 禁忌搜索 完备算法 

单位：广东工业大学管理学院管科系; 广州510520; 中国科学院信息工程研究所; 北京100093