Jak udowodnić, że chciwy algorytm jest poprawny

Mam chciwy algorytm, który, jak podejrzewam, może być poprawny, ale nie jestem pewien. Jak sprawdzić, czy jest poprawny? Jakich technik należy użyć do udowodnienia, że ​​chciwy algorytm jest poprawny? Czy istnieją wspólne wzorce lub techniki?

^{Mam nadzieję, że stanie się to pytaniem referencyjnym, które można wykorzystać do wskazania początkującym; stąd jego szerszy niż zwykle zakres. Prosimy o podanie ogólnych, dydaktycznie przedstawionych odpowiedzi, które są zilustrowane co najmniej jednym przykładem, ale mimo to obejmują wiele sytuacji. Dzięki!}

Ostatecznie będziesz potrzebować matematycznego dowodu poprawności. Poniżej przedstawię kilka technik dowodowych, ale najpierw, zanim się do nich zagłębię, pozwól mi zaoszczędzić trochę czasu: zanim zaczniesz szukać dowodu, wypróbuj losowe testy.

Losowe testy

Jako pierwszy krok zalecamy przetestowanie algorytmu przy użyciu losowych testów. To zadziwiające, jak skuteczne jest to: z mojego doświadczenia wynika, że ​​w przypadku chciwych algorytmów losowe testowanie wydaje się nieuzasadnione. Poświęć 5 minut na kodowanie algorytmu, a możesz zaoszczędzić godzinę lub dwie, próbując znaleźć dowód.

Podstawowa idea jest prosta: zaimplementuj swój algorytm. Zaimplementuj również algorytm referencyjny, o którym wiesz, że jest poprawny (np. Taki, który wyczerpująco wypróbowuje wszystkie możliwości i bierze najlepsze). W porządku, jeśli algorytm referencyjny jest asymptotycznie nieefektywny, ponieważ uruchamiasz go tylko w przypadku małych problemów. Następnie losowo wygeneruj milion małych wystąpień problemów, uruchom oba algorytmy na każdym z nich i sprawdź, czy algorytm kandydujący daje poprawną odpowiedź w każdym przypadku.

Empirycznie, jeśli twój kandydat na chciwy algorytm jest niepoprawny, zazwyczaj odkryjesz go podczas losowych testów. Jeśli wydaje się być poprawny we wszystkich przypadkach testowych, należy przejść do następnego kroku: wymyślenie matematycznego dowodu poprawności.

Matematyczne dowody poprawności

OK, więc musimy udowodnić, że nasz chciwy algorytm jest poprawny: że generuje optymalne rozwiązanie (lub, jeśli istnieje wiele optymalnych rozwiązań, które są równie dobre, że wypisuje jedno z nich).

Podstawowa zasada jest intuicyjna:

Zasada: jeśli nigdy nie dokonasz złego wyboru, zrobisz dobrze.

Chciwe algorytmy zwykle obejmują sekwencję wyborów. Podstawowa strategia dowodowa polega na tym, że spróbujemy udowodnić, że algorytm nigdy nie dokonuje złego wyboru. Chciwe algorytmy nie mogą cofnąć się - gdy dokonają wyboru, są zobowiązane i nigdy nie cofną tego wyboru - dlatego ważne jest, aby nigdy nie dokonali złego wyboru.

Co by się liczyło jako dobry wybór? Jeśli istnieje jedno optymalne rozwiązanie, łatwo jest zobaczyć, co jest dobrym wyborem: każdy wybór identyczny z wyborem optymalnym. Innymi słowy, postaramy się udowodnić, że na dowolnym etapie wykonywania zachłannych algorytmów sekwencja wyborów dokonanych przez algorytm dokładnie odpowiada pewnemu przedrostkowi optymalnego rozwiązania. Jeśli istnieje wiele równie dobrych optymalnych rozwiązań, dobrym wyborem jest takie, które jest zgodne z co najmniej jednym z optymów. Innymi słowy, jeśli sekwencja wyborów algorytmu do tej pory odpowiada przedrostkowi jednego z optymalnych rozwiązań, na razie wszystko jest w porządku (jak dotąd nic się nie stało).

Aby uprościć życie i wyeliminować zakłócenia, skupmy się na przypadku, w którym nie ma żadnych powiązań: istnieje jedno, unikalne, optymalne rozwiązanie. Wszystkie maszyny zostaną przeniesione do skrzyni, w której może istnieć wiele równie dobrych optymów bez żadnych zasadniczych zmian, ale trzeba być bardziej ostrożnym w kwestii szczegółów technicznych. Zacznij od zignorowania tych szczegółów i skupienia się na przypadku, w którym optymalne rozwiązanie jest unikalne; które pomogą Ci skupić się na tym, co najważniejsze.

Istnieje bardzo popularny wzór dowodu, którego używamy. Będziemy ciężko pracować, aby udowodnić następującą właściwość algorytmu:

Twierdzenie: Niech będzie wyjściem algorytmu, a O rozwiązaniem optymalnym. Jeśli S różni się od O , to możemy dostosować O dostać innego rozwiązania O * , który różni się od O i ściśle lepiej niż O .$S$$O$$S$$O$$O$$O^*$$O$$O$

Zauważ, dlaczego jest to przydatne. Jeśli twierdzenie jest prawdziwe, oznacza to, że algorytm jest poprawny. Jest to w zasadzie dowód sprzeczności. Albo jest taki sam jak O lub jest inny. Jeśli jest inaczej, możemy znaleźć inne rozwiązanie O ∗, które jest zdecydowanie lepsze niż O - ale to sprzeczność, ponieważ zdefiniowaliśmy O jako rozwiązanie optymalne i nie może być żadnego rozwiązania, które byłoby lepsze od tego. Jesteśmy więc zmuszeni stwierdzić, że S nie może różnić się od O ; S musi zawsze być równe $S$$O$$O^*$$O$$O$$S$$O$$S$$O$, tj. chciwy algorytm zawsze wyświetla poprawne rozwiązanie. Jeśli możemy udowodnić powyższe twierdzenie, udowodniliśmy, że nasz algorytm jest poprawny.

W porządku. Jak więc udowodnimy roszczenie? Myślimy o rozwiązaniu jako wektorze ( S 1 , … , S n ), który odpowiada sekwencji n wyborów dokonanych przez algorytm, i podobnie myślimy o optymalnym rozwiązaniu O jako wektorze ( O 1 , … , o n ) odpowiadający sekwencji wyborów, które prowadziłoby do o . Jeśli S różni się od O , musi istnieć jakiś indeks i, gdzie S i$S$$(S_1,\dots,S_n)$$n$$O$$(O_1,\dots,O_n)$$O$$S$$O$$i$ ; skupimy się na najmniejszym takim ja . Następnie będziemy podkręcać O zmieniając O trochę w I th pozycję na mecz S I , czyli będziemy podkręcać Rozwiązaniem optymalnym O zmieniając I th wybór do jednego, wybranego przez algorytm zachłanny, a następnie pokażemy, że prowadzi to do jeszcze lepszego rozwiązania. W szczególności, będziemy definiować O * za coś$S_i \ne O_i$$i$$O$$O$$i$$S_i$$O$$i$$O^*$

z wyjątkiem tego, że często będziemy musieli nieznacznie zmodyfikować część aby zachować globalną spójność. Część strategii dowodowej polega na pewnej sprytności w odpowiednim zdefiniowaniu O ∗ . Następnie mięso dowodu będzie w jakiś sposób wykorzystywało fakty na temat algorytmu i problem wykazania, że O ∗ jest zdecydowanie lepsze niż $O_{i+1},O_{i+2},\dots,O_n$$O^*$$O^*$$O$; tam potrzebujesz szczegółowych informacji na temat problemu. W pewnym momencie musisz zagłębić się w szczegóły konkretnego problemu. Ale to daje poczucie struktury typowego dowodu poprawności dla chciwego algorytmu.

Prosty przykład: podzbiór z maksymalną sumą

Może to być łatwiejsze do zrozumienia, szczegółowo omawiając prosty przykład. Rozważmy następujący problem:

Wejście: zbiór liczb całkowitych, liczba całkowita k Wyjście: zbiór S ⊆ U wielkości k, którego suma jest tak duża, jak to możliwe$U$$k$
$S \subseteq U$$k$

Istnieje naturalny algorytm zachłanny dla tego problemu:

1. Ustaw .$S := \emptyset$
2. Dla : $i := 1,2,\dots,k$
   • Niech być największa liczba w U , które nie zostały jeszcze pobrane (czyli ja th największa liczba w U ). Dodatek x I do S .$x_i$$U$$i$$U$$x_i$$S$

Losowe testy sugerują, że zawsze daje to optymalne rozwiązanie, więc formalnie udowodnijmy, że ten algorytm jest poprawny. Pamiętaj, że optymalne rozwiązanie jest wyjątkowe, więc nie będziemy musieli martwić się o więzi. Udowodnijmy roszczenie przedstawione powyżej:

Twierdzenie: Niech będzie wyjściem rozwiązania przez ten algorytm na wejściach U , k i O rozwiązaniem optymalnym. Jeśli S ≠ O , można skonstruować inne rozwiązanie O * , których suma jest nawet większy niż O .$S$$U,k$$O$$S \ne O$$O^*$$O$

Dowód. Załóżmy, i pozwolić i jest indeksem pierwszej iteracji, gdzie x i ∉ O . (Taki indeks i musi istnieć, ponieważ przyjęliśmy S ≠ O, a według definicji algorytmu mamy S = { x 1 , … , x k } .) Ponieważ (z założenia) i jest minimalne, musimy mieć x 1 , … , x i - 1 ∈ O , w szczególności,$S \ne O$$i$$x_i \notin O$$i$$S \ne O$$S=\{x_1,\dots,x_k\}$$i$$x_1,\dots,x_{i-1} \in O$ ma postać O = { x 1 , x 2 , … , x i - 1 , x ′ i , x ′ i + 1 , … , x ′ n } , gdzie liczby x 1 , … , x i - 1 , x ′ i , … , x ′ $O$$O=\{x_1,x_2,\dots,x_{i-1},x'_i,x'_{i+1},\dots,x'_n\}$$x_1,\dots,x_{i-1},x'_i,\dots,x'_n$są wymienione w kolejności malejącej. Patrząc na to, jak algorytm wybiera , widzimy, że musimy mieć x i > x ′ j dla wszystkich j ≥ i . W szczególności x i > x ′ i . Zdefiniuj więc O = O ∪ { x i } ∖ { x ′ i } , tzn. Otrzymamy O ∗ poprzez usunięcie i- tej liczby w $x_1,\dots,x_i$$x_i > x'_j$$j\ge i$$x_i > x'_i$$O^ = O \cup \{x_i\} \setminus \{x'_i\}$$O^*$$i$$O$i dodając . Teraz suma elementów O * jest sumą elementów O Plus x I - x ' I , a x I - x ' I > 0 , więc wy * 's suma jest większa niż ściśle O ' sumy s. To potwierdza roszczenie. $x_i$$O^*$$O$$x_i-x'_i$$x_i-x'_i>0$$O^*$$O$$\blacksquare$

Intuicja polega na tym, że jeśli chciwy algorytm dokona wyboru niezgodnego z , to możemy udowodnić, że O mógłby być jeszcze lepszy, gdyby został zmodyfikowany w celu włączenia elementu wybranego przez chciwy algorytm na tym etapie. Ponieważ O jest optymalne, nie może być żadnego sposobu, aby uczynić go jeszcze lepszym (byłoby to sprzecznością), więc jedyną pozostałą możliwością jest to, że nasze założenie było błędne: innymi słowy, zachłanny algorytm nigdy nie dokona wyboru które są niezgodne z o .$O$$O$$O$$O$

Ten argument jest często nazywany argumentem wymiany lub lematem wymiany . Znaleźliśmy pierwsze miejsce, w którym optymalne rozwiązanie różni się od chciwego rozwiązania i wyobrażaliśmy sobie, że wymienimy ten element na odpowiadający mu chciwy wybór (zamieniliśmy x ′ i na x i ). Niektóre analizy wykazały, że ta wymiana może jedynie poprawić optymalne rozwiązanie - ale z definicji optymalne rozwiązanie nie może zostać ulepszone. Jedyny wniosek jest taki, że nie może być miejsca, w którym optymalne rozwiązanie różni się od chciwego rozwiązania. Jeśli masz inny problem, poszukaj możliwości zastosowania tej zasady wymiany w konkretnej sytuacji.$O$$x'_i$$x_i$

Jako przykład użyję następującego prostego algorytmu sortowania:

repeat:
  if there are adjacent items in the wrong order:
     pick one such pair and swap
  else
     break

Aby udowodnić poprawność, wykonuję dwa kroki.

• Najpierw pokazuję, że algorytm zawsze się kończy.
• Następnie pokazuję, że rozwiązanie, w którym się kończy, jest tym, którego chcę.

Po pierwsze, wybieram odpowiednią funkcję kosztu, dla której mogę pokazać, że algorytm poprawia ją na każdym etapie.

$A$$A[i]$$A[j]$$A[i] > A[j]$$i<j$

$A[i]$$A[i+1]$$A[i],A[i+1]$

Dowodzi to, że algorytm ostatecznie się kończy.

Liczba inwersji na posortowanej liście wynosi 0. Jeśli wszystko pójdzie dobrze, algorytm zmniejszy liczbę inwersji do 0. Musimy tylko pokazać, że nie utknie w lokalnym minimum.

Zazwyczaj dowodzę tego przez sprzeczność. Zakładam, że algorytm zatrzymał się, ale rozwiązanie jest nieprawidłowe. W tym przykładzie oznacza to, że lista nie jest jeszcze posortowana, ale nie ma sąsiadujących elementów w niewłaściwej kolejności.

$A[i]$$A[j]$$i<j$$A[i]>A[j]$$i$$j$$i+1 < j$$A[i]<A[i+1]$$A[i+1]<A[j]$$A[i]<A[j]$

Dowodzi to, że algorytm zatrzymuje się tylko podczas sortowania listy. I tak skończyliśmy.