algorithm - 問題が「欲張り選択特性」を示していることをどのように確認できますか？

Question

「欲張り選択性」が成り立たない状況になるのではないかと思います。

どんな問題でも、私は小さなデータセットしかチェックできません。大規模なデータセットの場合、プロパティが失敗した場合はどうなりますか？

確信できますか？

Answer 1

おそらくもっと理論的な方法は、問題がマトロイド構造を持っていることの証明です。問題がそのような構造を持っていることを証明できれば、それを解決するための欲張りアルゴリズムがあります。

古典的な本「アルゴリズムの紹介」によると、マトロイド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.

多くの場合、Sの各要素xに重みを割り当てる重み関数wもあります。

次の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}