Как вы можете быть уверены, что проблема показывает «Жадный выбор собственности»?

Question

Боюсь, что может возникнуть ситуация, в которой свойство жадного выбора "может не сохраниться.

Для любой проблемы я могу проверять только небольшие наборы данных. Что делать, если для больших наборов данных свойство не выполняется?

Можем ли мы быть уверены?

Answer 1

Вероятно, более теоретическим способом является доказательство того, что ваша задача имеет структуру Matroid . Если вы можете доказать, что ваша проблема имеет такую ​​структуру, есть жадный алгоритм для ее решения.

Согласно классической книге "Введение в алгоритмы" Матроид А - это упорядоченная пара 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, которая присваивает каждому элементу x в S вес.

Если вы можете сформулировать свою функцию как взвешенный матроид, то следующий 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}