计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2005年
24期
41-43
,共3页
决策表%粗糙集%约简%NP-hard问题%启发式算法
決策錶%粗糙集%約簡%NP-hard問題%啟髮式算法
결책표%조조집%약간%NP-hard문제%계발식산법
首先给出了计算决策表的所有规则的所有约简的一种算法.以此为基础从三个不同的角度(即最小算法包含的约简数最少,或其中每个约简所含合取项最少,或其中所有约简的合取项数之和最少)讨论了最小算法的优化问题,分别证明它们是NP-hard问题,给出了最小算法三种优化问题的启发式算法,并对其时间复杂度进行了分析.最后,演示了三个算例.
首先給齣瞭計算決策錶的所有規則的所有約簡的一種算法.以此為基礎從三箇不同的角度(即最小算法包含的約簡數最少,或其中每箇約簡所含閤取項最少,或其中所有約簡的閤取項數之和最少)討論瞭最小算法的優化問題,分彆證明它們是NP-hard問題,給齣瞭最小算法三種優化問題的啟髮式算法,併對其時間複雜度進行瞭分析.最後,縯示瞭三箇算例.
수선급출료계산결책표적소유규칙적소유약간적일충산법.이차위기출종삼개불동적각도(즉최소산법포함적약간수최소,혹기중매개약간소함합취항최소,혹기중소유약간적합취항수지화최소)토론료최소산법적우화문제,분별증명타문시NP-hard문제,급출료최소산법삼충우화문제적계발식산법,병대기시간복잡도진행료분석.최후,연시료삼개산례.
