Argument ładowania

W informatyce argument ładowania jest używany do porównania wyniku algorytmu optymalizacji z rozwiązaniem optymalnym. Zwykle jest używany do wykazania, że ​​algorytm daje optymalne wyniki, udowadniając istnienie określonej funkcji iniekcyjnej . W przypadku maksymalizacji zysku funkcją może być dowolne odwzorowanie jeden do jednego od elementów rozwiązania optymalnego do elementów wyniku algorytmu. W przypadku problemów z minimalizacją kosztów funkcja może być dowolnym odwzorowaniem jeden do jednego od elementów wyjścia algorytmu do elementów rozwiązania optymalnego.

Poprawność

Aby algorytm optymalnie rozwiązał problem maksymalizacji zysku, algorytm musi generować dane wyjściowe, które mają taki sam zysk, jak optymalne rozwiązanie dla każdego możliwego wejścia. Niech | A(ja) | oznaczamy zysk z wyjścia algorytmu przy danym wejściu I , i niech | OPCJA(I) | oznaczają zysk optymalnego rozwiązania dla I . Jeśli istnieje funkcja iniekcyjna h : OPT(I) → A(I) , to wynika z tego, że | OPCJA(I) | ≤ | A(ja) | . Ponieważ rozwiązanie optymalne ma największy możliwy do osiągnięcia zysk, oznacza to, że dane wyjściowe algorytmu są tak samo opłacalne jak rozwiązanie optymalne, a więc algorytm jest optymalny.

Poprawność argumentu ładowania dla problemu minimalizacji kosztów jest symetryczna. Jeśli | A(ja) | i | OPCJA(I) | oznaczają odpowiednio koszt wyjścia algorytmu i optymalnego rozwiązania, to istnienie funkcji iniekcyjnej h : A(I) → OPT(I) oznaczałoby, że | A(ja) | ≤ | OPCJA(I) | . Ponieważ rozwiązanie optymalne ma najniższy koszt, a koszt algorytmu jest taki sam jak koszt optymalnego rozwiązania problemu minimalizacji, to algorytm również optymalnie rozwiązuje problem.

Wariacje

Argumentów ładowania można również użyć do pokazania wyników przybliżenia. W szczególności można go użyć do pokazania, że ​​algorytm jest n - przybliżeniem problemu optymalizacyjnego. Zamiast pokazywać, że algorytm generuje wyniki o takiej samej wartości zysku lub kosztu jak rozwiązanie optymalne, pokaż, że osiąga tę wartość w ramach czynnika n . Zamiast udowadniać istnienie funkcji jeden do jednego, argument ładowania skupia się na udowodnieniu, że n -do jednego, aby udowodnić wyniki przybliżenia.

Przykłady

Problem z planowaniem interwałów

Główny artykuł: planowanie interwałowe

Dany jest zbiór n przedziałów I = {I 1 , I 2 , ... , Ja n } , gdzie każdy przedział I i ∈ I ma czas początkowy s i i czas końcowy f ja , gdzie s ja < f ja , celem jest znalezienie maksymalnego podzbioru wzajemnie zgodnych przedziałów w I . Tutaj mówi się, że dwa przedziały I j i I k są zgodne, jeśli się nie nakładają, w tym s j < f j ≤ s k < f k .

zachłanny na najwcześniejszy czas zakończenia , opisany w następujący sposób:

  • Zacznij od pustego zestawu interwałów.
  • Posortuj interwały w I według rosnących czasów zakończenia.
  • Rozważ każdy przedział w I w posortowanej kolejności. Dodaj interwał do zbioru, jeśli nie koliduje on z przedziałami już zawartymi w zbiorze. W przeciwnym razie zignoruj ​​interwał.

Problem planowania interwałowego można postrzegać jako problem maksymalizacji zysku, w którym liczba interwałów we wzajemnie zgodnym podzbiorze jest zyskiem. Argument ładowania może być użyty do pokazania, że ​​algorytm najwcześniejszego czasu zakończenia jest optymalny dla problemu planowania interwałowego.

Mając zbiór przedziałów I = {I 1 , I 2 , ... , I n } , niech OPT(I) będzie dowolnym optymalnym rozwiązaniem problemu szeregowania przedziałów i niech EFT(I) będzie rozwiązaniem najwcześniejszego zakończenia algorytm czasu. Dla dowolnego przedziału J ∈ OPT(I) , zdefiniujmy h(J) jako przedział J' ∈ EFT(I) przecinający J z najwcześniejszym czasem zakończenia spośród wszystkich przedziałów w EFT(I) przecinających się z J . Aby pokazać, że algorytm najwcześniejszego czasu zakończenia jest optymalny przy użyciu argumentu ładowania, h jest funkcją jeden do jednego odwzorowującą interwały w OPT(I) na interwały w EFT(I) . Załóżmy, że J jest dowolnym przedziałem w OPT(I) .

Pokaż, że h jest funkcją odwzorowującą OPT(I) na EFT(I) .

Załóżmy jako sprzeczność, że nie istnieje przedział J' ∈ EFT(I) spełniający h(J) = J' . Z definicji h oznacza to, że żaden przedział w EFT(I) nie przecina się z J . Jednak oznaczałoby to również, że J jest zgodne z każdym przedziałem w EFT(I) , a więc algorytm najwcześniejszego czasu zakończenia dodałby J do EFT(I) , a więc J ∈ EFT(I) . Powstaje sprzeczność, ponieważ założono, że J nie przecina się z żadnym przedziałem w EFT(I) , a jednak J jest w EFT(I) , a J przecina się sam ze sobą. Zatem przez sprzeczność J musi przecinać się z co najmniej jednym przedziałem w EFT(I) .
Pozostaje pokazać, że h(J) jest jednoznaczny. W oparciu o definicję kompatybilności nigdy nie może być tak, że dwa kompatybilne interwały mają ten sam czas zakończenia. Ponieważ wszystkie interwały w EFT(I) są wzajemnie kompatybilne, żaden z nich nie ma takiego samego czasu zakończenia. W szczególności każdy interwał w EFT(I) , który przecina się z J , ma różne czasy zakończenia, a więc h(J) jest unikalny.

Pokaż, że h jest różnorakie.

Załóżmy dla sprzeczności, że h nie jest iniekcyjne. Wtedy są dwa różne przedziały w OPT(I) , J 1 i J 2 , takie, że h odwzorowuje zarówno J 1, jak i J 2 na ten sam przedział J' ∈ EFT(I) . Bez utraty ogólności załóżmy, że f 1 < f 2 . Przedziały J 1 i J 2 nie mogą się przecinać, ponieważ oba znajdują się w optymalnym rozwiązaniu, więc f 1 ≤ s 2 < f 2 . Ponieważ EFT(I) zawiera J' zamiast J1 , J1 algorytm najwcześniejszego czasu wykańczania napotkał J' przed . Zatem f' ≤ fa 1 . Oznacza to jednak, że f' ≤ f 1 ≤ s 2 < f 2 , więc J' i J 2 nie przecinają się. Jest to sprzeczność, ponieważ h nie może odwzorować J 2 na J' , jeśli się nie przecinają. Zatem przez sprzeczność h jest iniekcyjne.

Dlatego h jest funkcją jeden do jednego odwzorowującą interwały w OPT(I) na przedziały w EFT(I) . Zgodnie z argumentem ładowania, algorytm najwcześniejszego czasu zakończenia jest optymalny.

Problem z planowaniem interwałów zadań

Rozważmy problem planowania interwałowego zadań, NP-trudny wariant omawianego wcześniej problemu planowania interwałowego. Tak jak poprzednio, celem jest znalezienie maksymalnego podzbioru wzajemnie zgodnych przedziałów w danym zbiorze n przedziałów, I = {I 1 , I 2 , ... , I n } . Każdy przedział I i ∈ I ma czas rozpoczęcia s i , czas zakończenia fi i klasę pracy c i . Tutaj mówi się, że dwa przedziały I j i I k są kompatybilne, jeśli nie nakładają się i nie mają różnych klas.

Przypomnij sobie algorytm najwcześniejszego czasu zakończenia z poprzedniego przykładu. Po zmodyfikowaniu definicji zgodności w algorytmie argumentu ładowania można użyć do pokazania, że ​​algorytm najwcześniejszego czasu zakończenia jest algorytmem 2-przybliżenia dla problemu planowania interwałów zadań.

Niech OPT(I) i EFT(I) oznaczają rozwiązanie optymalne i rozwiązanie otrzymane przez algorytm najwcześniejszego czasu zakończenia, jak zdefiniowano wcześniej. Dla dowolnego przedziału J ∈ OPT(I) zdefiniuj h w następujący sposób:

Aby pokazać, że algorytm najwcześniejszego czasu zakończenia jest algorytmem przybliżenia 2 przy użyciu argumentu ładowania, należy pokazać, że h jest funkcją dwa do jednego odwzorowującą interwały w OPT(I) na przedziały w EFT(I) . Załóżmy, że J jest dowolnym przedziałem w OPT(I) .

Pokaż, że h jest funkcją odwzorowującą OPT(I) na EFT(I) .

Po pierwsze, zauważ, że albo jest jakiś przedział w EFT(I) z tą samą klasą pracy co J , albo go nie ma.
Przypadek 1. Załóżmy, że jakiś przedział w EFT(I) ma tę samą klasę zadań co J . Jeśli w
EFT(I) istnieje przedział o tej samej klasie co J , to J odwzoruje ten przedział. Ponieważ interwały w EFT(I) są wzajemnie kompatybilne, każdy interwał w EFT(I) musi mieć inną klasę zadań. Zatem taki przedział jest wyjątkowy.
Przypadek 2. Załóżmy, że w EFT(I) nie ma interwałów z tą samą klasą pracy co J . Jeśli w
EFT(I) nie ma przedziałów tej samej klasy co J , to h odwzorowuje J na przedział z najwcześniejszym czasem zakończenia spośród wszystkich przedziałów w EFT(I) przecinających się z J . Dowód istnienia i jednoznaczności takiego przedziału podano w poprzednim przykładzie.

Pokaż, że h jest równe dwa do jednego.

Załóżmy dla sprzeczności, że h nie jest równe dwa do jednego. Wtedy są trzy różne przedziały w OPT(I) , J 1 , J 2 i J 3 , takie, że h odwzorowuje każdy z J 1 , J 2 i J 3 na ten sam przedział J' ∈ EFT(I) . Zgodnie z zasadą przegródki co najmniej dwa z trzech interwałów zostały odwzorowane na J' , ponieważ mają tę samą klasę pracy co J ' lub ponieważ J ' jest interwałem z najwcześniejszym czasem zakończenia spośród wszystkich interwałów w EFT(I) przecinających oba interwały. Bez utraty ogólności załóżmy, że te dwa przedziały to J 1 i J 2 .
Przypadek 1. Załóżmy, że J 1 i J 2 zostały odwzorowane na J ', ponieważ mają tę samą klasę zawodów co J '.
Wtedy każdy J ', J 1 i J 2 ma tę samą klasę zawodów. Jest to sprzeczność, ponieważ przedziały w rozwiązaniu optymalnym muszą być zgodne, ale J 1 i J 2 nie są.
Przypadek 2. Załóżmy, że J ' jest interwałem z najwcześniejszym czasem zakończenia spośród wszystkich interwałów w EFT(I) przecinających zarówno J 1 , jak i J 2 .
Dowód tego przypadku jest równoważny z tym z poprzedniego przykładu, który wykazał iniekcję. Z powyższego dowodu wynika sprzeczność.

Dlatego h odwzorowuje nie więcej niż dwa różne przedziały w OPT(I) na ten sam przedział w EFT(I) , a więc h wynosi dwa do jednego. Zgodnie z argumentem ładowania, algorytm najwcześniejszego czasu zakończenia jest algorytmem z dwoma przybliżeniami dla problemu planowania interwałów zadań.

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Charging_argument&oldid=973893362 ”