Czy można udowodnić, że dla danego problemu nie istnieją optymalne algorytmy zachłanne?

Chciwość jest terminem nieformalnym, ale może być (nie jestem pewien, dlatego pytam), że w przypadku niektórych problemów chciwość może być sformułowana matematycznie, a zatem można udowodnić, że nie istnieje optymalny algorytm chciwości. czy to możliwe?

Najprostszą rzeczą jest skonfigurowanie chciwego algorytmu dla problemu, a następnie poszukiwanie kontrprzykładu. Jeśli ją znajdziesz, masz odpowiedź. W przeciwnym razie istnieje wiele sposobów udowodnienia, że ​​chciwość działa . Oczywiście są z tym pewne problemy (takie jak sposób sformułowania chciwego algorytmu). Jeśli chodzi o scharakteryzowanie, które problemy można, a które problemów nie można łapczywie rozwiązać, istnieje również ogólna odpowiedź na to pytanie.

W rzeczywistości, w swoim artykule „Dokładna charakterystyka chciwych struktur” ( SIAM J. Discrete Math . 6 , s. 274–283), Helman, Moret i Shapiro podali formalny opis tego (zwany osadzaniem matroidów , który uogólnia matroidy i greedoidy). Ze streszczenia: „Autorzy przedstawiają dokładne charakterystyki struktur, w których zachłanny algorytm wytwarza optymalne rozwiązania”.

Ogólnie, chciwy algorytm można sformułować w kategoriach zestawów ważonych $(E,\mathcal{F},w)$. Masz zestaw$E$ (na przykład krawędzie, w przypadku minimalnego drzewa rozpinającego), i masz zestaw $\mathcal{F}\subseteq 2^E$ podzbiorów $E$ (pomyśl o częściowo rozciągających się lasach, aby rozwiązać problem minimalnego rozciągania drzew). $\mathcal{F}$ reprezentuje prawidłowe rozwiązania częściowe zbudowane przez połączenie elementów z $E$. Istnieje również funkcja wagi,$w$, co daje wagę lub koszt dowolnego elementu w $\mathcal{F}$. Zazwyczaj zakładamy, że jest to liniowe, tj. Każdy element w$E$ma wagę, a masy (częściowych) rozwiązań są tylko sumą wag elementów. (Na przykład waga drzewa opinającego jest sumą jego wag krawędzi.) W tym kontekście Helman i in. wykazał, że następujące są równoważne:

1. Dla każdej liniowej funkcji celu $(E,\mathcal{F})$ ma optymalną podstawę.

2. $(E,\mathcal{F})$ jest osadzanie matroidu.

3. Chciwe podstawy dla każdej liniowej funkcji celu $(E,\mathcal{F})$ są dokładnie jego optymalnymi podstawami.

Innymi słowy: w przypadku struktur takich jak te (które w zasadzie zawierają takie struktury, o których zwykle myśli się podczas pracy z chciwością), dokładnie zestaw osadzeń matroidów można rozwiązać łapczywie.

Definicja osadzania matroidów nie jest wcale taka trudna, więc udowodnienie, że dany problem jest lub nie jest osadzeniem matroidów, jest z pewnością wykonalne. Wpis Wikipedia podaje definicję dość wyraźnie. (Zrozumienie dowodu, dlaczego są to dokładne struktury rozwiązane przez chciwość - to zupełnie inna sprawa…)

Jeśli Twój problem może być sformułowany w zakresie wyboru z systemu ważenia zestaw z liniowej funkcji celu, a jeśli można pokazać, że to nie matroid osadzanie, a następnie wykazały, że nie może być rozwiązany łapczywie, nawet jeśli Haven” udało mi się znaleźć kontrprzykład. (Chociaż podejrzewam, że znalezienie kontrprzykładu byłoby znacznie łatwiejsze).

Podejście to nie jest całkowicie pozbawione problemów. Jak mówisz, ogólna idea chciwości jest raczej nieformalna i być może uda się ją ulepszyć w taki sposób, aby nie obowiązywał formalizm systemów zbiorów liniowo ważonych.

Tak, jest taka praca. Allan Borodin wraz ze współautorami opracowali teorię, w której formalizują pojęcie chciwości i uzyskują wyniki, które można osiągnąć dzięki stosunkom aproksymacji. Wprowadzają klasę algorytmów priorytetowych, które uogólniają algorytmy zachłanne. Ich pierwszą pracą na ten temat jest praca „ (Przyrostowe) algorytmy priorytetowe ”.

PS Poprzedni akapit odpowiada na inne pytanie: Czy można udowodnić, że dla danego problemu nie istnieją żadne zachłanne algorytmy o stosunku aproksymacji mniejszym niż niektóre $1+\epsilon$? Co dotyczy pytania, jak przypuszczam, zakłada się, że optymalne oznacza dokładne, więc pytanie dotyczy problemów w P (zakładam, że chciwe algorytmy mają wielomianową złożoność, choć myślę, że nie jest to konieczne), o których wiadomo, że mają rozwiązania inne niż chciwe . I nie znam odpowiedzi na to pytanie.

Do ivotron: jeśli nie miałeś na myśli mojej pierwszej interpretacji, usunę tę odpowiedź.

Zobacz także: http://en.wikipedia.org/wiki/Greedoid