恐怕会出现“贪婪选择属性”可能不成立的情况。
对于任何问题,我只能检查小数据集。如果对于大型数据集,属性失败怎么办?
我们能确定吗?
一种可能更具理论性的方法是证明您的问题具有拟阵结构。如果你能证明你的问题有这样的结构,那么就有一个贪心算法来解决它。
根据经典著作“算法简介”,拟阵 a 是有序对 M = (S,l),其中:
* S is a finite nonemtpy set
* l is a nonempty family of subsets of S, such that B element of l and
A a subset of B than also A is element of l. l is called the independent
subsets of S.
* If A and B are elements of l and A is a smaller cardinality than B, then
there is some element x that is in B, but not in A, so that A extended
by x is also element of l. That is called exchange property.
通常还有一个权重函数 w,它为 S 中的每个元素 x 分配一个权重。
如果您可以将您的函数制定为加权拟阵,那么以下类似 Python 的伪代码可以解决您的问题:
GREEDY(M,w):
(S,l) = M
a = {}
sort S into monotonically decreasing order by weight w
for x in S:
if A + {x} in l:
A = A + {x}