论文部分内容阅读
MasterMind问题是演绎博弈中最著名的问题之一，其求解过程与以下一系列复杂组合最优化问题均有着密切的联系。在对现有MasterMind求解算法，尤其是由Shapiro的简单策略发展而来的一系列算法，进行深入分析和比较的基础上，本文提出了两种具有普适性的改进的MasterMind求解算法。第一种是Reduced算法，它大大降低了前述算法的时间复杂度，但与此同时，算法所需猜测次数有所增加。于是笔者进而提出了基于混合策略的Hybrid算法。Hybrid算法可看作是Reduced算法与原算法的混合体，它不仅降低了原算法的时间复杂度，而且所需猜测次数均小于原算法及Reduced算法。