FD集最优覆盖多项式时间求解算法的研究

THE RESEARCH ON A POLYNOMIAL TIME ALGORITHM FOR SOLVING OPTIMAL COVER OF FD SET

本文在详细分析了ＦＤ集的最小覆盖和最优覆盖的结构特性基础上，提出并讨论了一个最小覆盖成为最优覆盖的条件及一个最优覆盖的属性集构成的特点、相应的引理和定理。最后给出了一个求ＦＤ集最优覆盖的多项式时间算法。

In this paper, the structure features of a minimum cover and an optimal cover of FD set are analyzed in detail. The condition under which a minimum cover becomes an optimal cover, the properties of composition of an optimal cover's attribute set,and relative lemmas and theorems are proposed and discussed. Finally,a polynomial time algorithm for solving an optimal cover of FD set is given.