Czy każdy zachłanny algorytm ma strukturę matroidu?

Jest dobrze znane, że dla każdego matroid $M$ żadna funkcja ciężaru $w$ , nie wychodzi algorytm $\mbox{GreedyBasis}(M,w)$ , która zwraca na podstawę maksymalny ciężar $M$ . Czy zatem odwrotny kierunek jest również prawdą? Oznacza to, że jeśli istnieje jakiś chciwy algorytm, musi również istnieć pewna struktura matroidu.

W rzeczywistości pełny i ogólny opis problemu, który można rozwiązać za pomocą chciwego algorytmu, polega na osadzeniu matroidu , który uogólnia zarówno pojęcie matroidu, jak i greedoidy . Odpowiedź brzmi: nie - problem rozwiązany przez zachłanny algorytm nie musi mieć struktury matroidu, ale będzie miał strukturę osadzania matroidu (co jest, niestety, znacznie bardziej skomplikowane).

Model mentalny niektórych z nich może polegać na znajdowaniu drzew o minimalnej rozpiętości. Struktura używana przez algorytm Kruskala jest matroidem, ale taka, której używa algorytm Prim (wymagający węzła początkowego), nie jest. (Jest to jednak chciwość - i osadzanie matroidów).

$(S,\mathcal{C})$$S$$\mathcal{C}$$S$ $f:2^S\rightarrow\mathbb{R}$$S$

Algorytm zachłanności, zdefiniowany w kategoriach tego formalizmu, jest dość prosty: zaczynasz od pustego zestawu i sukcesywnie dodajesz pojedynczy element, aż dojdziesz do podstawy, zawsze upewniając się, że (i) twój zestaw jest wykonalny na każdym kroku, i ( ii) dodawany element maksymalizuje funkcję celu wynikowego wyniku, wrt. wszystkie alternatywne elementy, które mogłeś dodać. (Oznacza to, że pod względem koncepcyjnym próbujesz dodać wszystkie możliwe alternatywy i wybrać tę, która daje najwyższą wartość celu.)

Można, być może, twierdzą, że mogą istnieć inne formy algorytm zachłanny, ale istnieje kilka podręczniki algorytmów i optymalizacji kombinatorycznej, które opisują ten set-systemowi algorytmu opartego jak na algorytm zachłanny. To nie powstrzymuje cię przed opisaniem czegoś, co nie pasuje, ale przypuszczam, że nadal można je nazwać chciwym. (Mimo to robi okładkę niczego, co mogłoby potencjalnie mieć matroid strukturę, na przykład, choć jest o wiele bardziej ogólne.)

What Helman i in. robią to, że opisują, kiedy ten algorytm zadziała. Dokładniej:

1. Pokazują, że dla liniowych funkcji celu (gdzie wartość celu jest sumą wag elementów), zachłanny algorytm będzie działał dokładnie na strukturze, którą definiują jako osadzenie matroidu;

2. Podają podobną charakterystykę dla tak zwanych celów wąskiego gardła (gdzie wartość obiektywna zestawu jest równa minimum w stosunku do wag poszczególnych elementów); i

3. Podają dokładną charakterystykę, które funkcje celu (poza liniowe) są zoptymalizowane przez chciwy algorytm osadzania matroidów.

Chciwy algorytm nie jest formalnie zdefiniowanym pojęciem. Istnieją różne modele próbujące uchwycić to intuicyjne pojęcie, ale nie ma zgody co do tego, co jest chciwym algorytmem. O ile nie określisz formalnej definicji tego, co rozumiesz przez chciwy algorytm, na pytanie nie można odpowiedzieć jako tak lub nie.

Istnieje uogólnienie matroidów zwanych greedoid, które jest inspirowane przez zachłanne algorytmy, na które możesz spojrzeć.

Rozważ następujące problemy: EURO ŁAŃCUCH MONET: Biorąc pod uwagę nieskończoną ilość banknotów 1,2,5,10 euro, zapłać X euro, używając jak najmniejszej liczby banknotów. Można to rozwiązać za pomocą chciwego algorytmu, który przyjmuje największą możliwą uwagę. Ale w tym problemie nie ma struktury matroidu.

ZAKRES OTWORÓW: W otworach znajdują się otwory x_1, x_2, ..., x_n. Masz naszywkę o długości 10 cm. Popraw dziury, używając jak najmniej łatek. Znów można to rozwiązać w zachłanny sposób (po prostu umieść łatkę tak dobrze, jak to możliwe), ale nie ma struktury matroidu.