你怎么能确定一个问题展示"贪婪的选择属性"？

Question

我担心可能存在" 贪婪的选择财产 "可能不适用的情况.

对于任何问题,我只能检查小数据集.如果对于大型数据集,属性失败怎么办？

我们能确定吗？

Answer 1

可能更理论化的方法是证明您的问题具有Matroid结构.如果你可以证明你的问题有这样的结构,那么有一个贪婪的算法来解决它.

根据经典着作"算法导论",拟阵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赋予权重.

如果您可以将函数表示为加权matroid,则以下类似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}