决策表的最小算法及其优化问题

The Minimal Algorithms of a Decision Table and Their Optimal Problems

首先给出了计算决策表的所有规则的所有约简的一种算法。以此为基础从三个不同的角度(即最小算法包含的约简数最少,或其中每个约简所含合取项最少,或其中所有约简的合取项数之和最少)讨论了最小算法的优化问题,分别证明它们是NP-hard问题,给出了最小算法三种优化问题的启发式算法,并对其时间复杂度进行了分析。最后,演示了三个算例。

In this paper,a algorithm for computing all the reducts of every decision rule in a decition table is proposed and performed.Furthermore,three optimal problems of the minimal algorithms of a decision table are investigated and their NP-hard nature is proved.Finaly,three heuristic algorithms for the three optimal problems are presented and performed.