Problem z wypożyczalnią nart

W informatyce problem wypożyczania nart to nazwa nadana klasie problemów, w których istnieje wybór między dalszym ponoszeniem powtarzających się kosztów a płaceniem jednorazowego kosztu, który eliminuje lub zmniejsza powtarzający się koszt.

Problem

Wiele problemów online ma podproblem zwany problemem wynajmu/kupna. Musimy zdecydować, czy pozostać w obecnym stanie i zapłacić określoną kwotę kosztu za jednostkę czasu, czy też przejść do innego stanu i zapłacić pewien stały, duży koszt bez dalszych opłat. Wypożyczalnia nart jest jednym z przykładów, gdzie wynajem/kupno to cały problem. Jego podstawowa wersja to:

Osoba wybiera się na narty na nieznaną liczbę dni. Wypożyczenie nart kosztuje 1 USD dziennie, a zakup nart kosztuje 10 USD. Każdego dnia osoba musi zdecydować, czy wypożyczyć narty jeszcze jeden dzień, czy kupić parę nart. Jeśli dana osoba wie z góry, ile dni będzie jeździć na nartach, może określić swój minimalny koszt. Jeśli będzie jeździć na nartach dłużej niż 10 dni, taniej będzie kupić narty, ale jeśli będzie jeździć na nartach krócej niż 10 dni, taniej będzie wypożyczyć. Co powinna zrobić, gdy nie wie z góry, ile dni będzie jeździć na nartach? ^{[ potrzebne źródło ]}

Formalnie problem można ustawić w następujący sposób. Istnieje liczba dni d (nieznana), przez które dana osoba będzie jeździć na nartach. Celem jest znalezienie algorytmu, który minimalizuje stosunek między tym, co osoba zapłaciłaby, gdy d nie jest znane z góry, a tym, ile osoba zapłaciłaby optymalnie, gdyby wiedziała o d z góry. Problem jest ogólnie analizowany w najgorszym przypadku, w którym algorytm jest naprawiony, a następnie patrzymy na wydajność algorytmu w najgorszym przypadku na wszystkich możliwych d . W szczególności nie przyjmuje się żadnych założeń dotyczących rozkładu d (i łatwo zauważyć, że znając rozkład d , preferowana byłaby inna analiza, a także inne rozwiązania). ^{[ potrzebne źródło ]}

Algorytm progu rentowności

Algorytm progu rentowności nakazuje wypożyczyć na 9 dni i kupić narty rano 10 dnia, jeśli ktoś nadal chce jeździć na nartach. Jeśli ktoś musi przestać jeździć na nartach w ciągu pierwszych 9 dni, kosztuje to tyle samo, co zapłaciłby, gdyby znał liczbę dni, przez które będzie jeździł na nartach. Jeśli ktoś musi przestać jeździć na nartach po 10 dniu, kosztuje 19 USD, czyli o 90% więcej niż to, co zapłaciłby, gdyby znał liczbę dni, przez które będzie jeździł na nartach z wyprzedzeniem. Jest to najgorszy przypadek dla algorytmu progu rentowności.

Wiadomo, że algorytm progu rentowności jest najlepszym algorytmem deterministycznym dla tego problemu.

Algorytm losowy

Osoba może rzucić monetą. Jeśli wypadnie reszka, kupuje narty ósmego dnia; w przeciwnym razie kupuje narty 10 dnia. Jest to przypadek losowego algorytmu . Oczekiwany koszt jest co najwyżej o 80% wyższy niż to, co dana osoba zapłaciłaby, gdyby wiedziała, ile dni spędzi na nartach, niezależnie od tego, ile dni spędzi na nartach. W szczególności, jeśli osoba jeździ na nartach przez 10 dni, jej oczekiwany koszt to 1/2 [7 +10] + 1/2 [9+10] = 18 dolarów, tylko 80% nadwyżki zamiast 90%.

Algorytm losowy można rozumieć jako kompozycję różnych algorytmów, z których każdy występuje z określonym prawdopodobieństwem. Oczekiwany współczynnik konkurencyjności na danej instancji i określamy jako:

$\ Displaystyle E_ {i} = \ suma _ {j} P (ALG_ {j}) \ cdot ALG_ {j} (i$ ZA $i)}$ ( jest współczynnikiem konkurencyjności na przykład ja, biorąc pod uwagę $\ Displaystyle ALG_ {j}}$

$jest$ określony przez najgorszą wartość we wszystkich podanych przypadkach. W przypadku wypożyczalni nart z rzucaniem monetą zauważamy, że losowy algorytm ma 2 możliwe rozgałęzienia: Jeśli wypadnie orzeł, kupujemy w dniu 8, w przeciwnym razie kupujemy w dniu 10. Możemy nazywać gałęzie ${\ Displaystyle ALG_ {głowice}}$ i ${\ Displaystyle ALG_ {ogony}}$ . ${\ Displaystyle E_ {i} = P (ALG_ {głowy}) \ cdot ALG_ {głowy} (i) + P (ALG_ {ogony}) \ cdot ALG_ { ogony} (i) = {\ Frac {1} {2}} \ cdot 1 + {\ Frac {1} {2}} \ cdot 1 = 1} , dla ja < 8 {\$ Displaystyle $}$ .

${\ Displaystyle E_ {8} = P (ALG_ {głowy}) \ cdot ALG_ {głowy} (8) + P (ALG_ {ogony}) \ cdot ALG_ {ogony} (8 )={\frac {1}{2}}\cdot {\frac {17}{8}}+{\frac {1}{2}}\cdot 1=1,5625}$ ,

${\ Displaystyle E_ {9} = P (ALG_ {głowy}) \ cdot ALG_ {głowy} (9) + P (ALG_ {ogony}) \ cdot ALG_ {ogony} (9 )={\frac {1}{2}}\cdot {\frac {17}{9}}+{\frac {1}{2}}\cdot 1=1.444444}$ i

${\ Displaystyle E_ {i} = P (ALG_ {głowy}) \ cdot ALG_ {głowy} (i) + P (ALG_ {ogony}) \ cdot ALG_ {ogony} ( i)={\frac {1}{2}}\cdot {\frac {17}{10}}+{\frac {1}{2}}\cdot {\frac {19}{10}}=1,8 }$ , dla ${\ Displaystyle i \ geq 10}$ .

Dlatego współczynnik konkurencyjności algorytmu losowego rzutu monetą wypożyczalni nart wynosi 1,8.

Najlepszym losowym algorytmem przeciwko nieświadomemu przeciwnikowi jest losowe wybranie pewnego dnia i zgodnie z następującym rozkładem p, wypożyczenie na i-1 dni i zakup nart rano dnia i, jeśli ktoś nadal chce jeździć na nartach. Karlin i in. pierwszy przedstawił ten algorytm z rozkładem ${\ Displaystyle p_ {i} = \ lewo \ {{\ rozpocząć {tablica} {ll} ({\ Frac {b-1} {b}}) ^ {bi} {\ Frac {1}{b(1-(1-(1/b))^{b})}}&i\leq b\\0&i>b\end{array}}\right.,} gdzie zakup nart kosztuje$ miliard ${\ displaystyle b}$ , a wynajem kosztuje 1 dolara. Jego oczekiwany koszt jest co najwyżej $, przez$ które jeździłby na nartach. Żaden losowy algorytm nie może działać lepiej.

Aplikacje

Buforowanie Snoopy'ego : kilka pamięci podręcznych współdzieli tę samą przestrzeń pamięci, która jest podzielona na bloki. Kiedy pamięć podręczna zapisuje do bloku, pamięci podręczne, które współużytkują ten blok, spędzają 1 cykl magistrali, aby uzyskać aktualizację. Te pamięci podręczne mogą unieważnić blok, aby uniknąć kosztów aktualizacji. Istnieje jednak kara p cykli magistrali za unieważnienie bloku z pamięci podręcznej, który wkrótce potem potrzebuje do niego dostępu. Możemy podzielić sekwencje żądań zapisu dla kilku pamięci podręcznych na sekwencje żądań dla dwóch pamięci podręcznych. Jedna pamięć podręczna wykonuje sekwencję operacji zapisu do bloku. Druga pamięć podręczna musi zdecydować, czy ma zostać zaktualizowana, płacąc 1 cykl magistrali na operację, czy też unieważnić blok, płacąc p cyklom magistrali za przyszłe żądanie odczytu. Dwie pamięci podręczne, jeden blok Snoopy problem z buforowaniem to tylko problem z wypożyczalnią nart.

Potwierdzenie TCP : Strumień pakietów dociera do miejsca docelowego i protokół TCP wymaga ich potwierdzenia po przybyciu. Możemy jednak użyć pojedynczego pakietu potwierdzenia do jednoczesnego potwierdzenia wielu zaległych pakietów, zmniejszając w ten sposób narzut związany z potwierdzeniami. Z drugiej strony, zbytnie opóźnianie potwierdzeń może zakłócać mechanizmy kontroli przeciążenia TCP, dlatego nie powinniśmy dopuszczać do zbytniego wzrostu opóźnienia między czasem nadejścia pakietu a czasem wysłania potwierdzenia. Karlin i in. opisał jednoparametrową rodzinę danych wejściowych, zwanych podstawowymi danymi wejściowymi, i pokazał, że w przypadku ograniczenia do tych podstawowych danych wejściowych problem potwierdzenia TCP zachowuje się tak samo, jak problem wypożyczenia nart.

Planowanie całkowitego czasu realizacji: Chcemy zaplanować zadania ze stałymi czasami przetwarzania na m identycznych maszynach. Czas przetwarzania zadania j to p _j . Każde zadanie staje się znane programowi planującemu w momencie jego zwolnienia _rj . Celem jest zminimalizowanie sumy czasów ukończenia wszystkich zadań. Uproszczonym problemem jest pojedyncza maszyna z następującymi danymi wejściowymi: w czasie 0 przychodzi zadanie z czasem przetwarzania 1; k zadań o czasie przetwarzania 0 przybywa w nieznanym czasie. Musimy wybrać godzinę rozpoczęcia pierwszej pracy. Oczekiwanie wiąże się z kosztem 1 za jednostkę czasu, jednak rozpoczęcie pierwszego zadania przed kolejnymi k zadaniami może wiązać się z dodatkowym kosztem k w najgorszym przypadku. Ten uproszczony problem można postrzegać jako ciągłą wersję problemu wypożyczania nart.

Refaktoryzacja a praca ze złym projektem : Podczas opracowywania oprogramowania inżynierowie muszą wybierać między tarciem a ryzykiem błędów związanych z pracą ze zbyt złożonym projektem a redukcją złożoności projektu przed wprowadzeniem zmian. Dodatkowym kosztem każdej zmiany ze starym projektem jest koszt „wynajmu”, koszt refaktoryzacji to koszt „kupna”. „Ile razy pracuje się nad kiepskim projektem, zanim go posprząta?” jest problem z wypożyczalnią sprzętu narciarskiego.

Zobacz też