문제가 "Greedy choice property"를 어떻게 나타낼 수 있습니까?

Question

"greedy choice property"이 보유하지 않은 상황이있을 수 있습니다.

어떤 문제라도 작은 데이터 세트 만 확인할 수 있습니다. 큰 데이터 세트의 경우 속성이 실패하면 어떻게됩니까?

우리는 확신 할 수 있습니까?

Answer 1

더 이론적 인 방법은 문제가 Matroid 구조임을 증명하는 것입니다. 문제가 그러한 구조를 가지고 있다는 것을 증명할 수 있다면 그것을 해결할 수있는 탐욕적인 알고리즘이 있습니다.

고전 책에 따르면 "Introduction to Algorithms" matroid A를 갖는 순서쌍 M = (S, l)이다, 즉, S의 각 원소 (X)를 할당 승

* 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. 

종종 또한 가중 함수가 인 무게. 가중 당신이 함수를 공식화 할 수있는 경우

다음 파이썬 같은 의사가 당신의 문제를 해결하는 것이 matroid :

이

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}