Algorytm online - Online algorithm
W informatyce , algorytm online to taki, który może przetwarzać jego kawałek po kawałku-wejściowy w sposób seryjny, czyli w takiej kolejności, że wejście jest podawany do algorytmu , bez konieczności całą wejście dostępne od samego początku.
W przeciwieństwie do tego algorytm offline otrzymuje od początku wszystkie dane dotyczące problemu i jest wymagany do uzyskania odpowiedzi, która rozwiązuje dany problem. W badaniach operacyjnych obszar, w którym opracowywane są algorytmy online, nazywany jest optymalizacją online .
Jako przykład rozważmy algorytmy sortowania sortowanie przez wybór i sortowanie przez wstawianie : sortowanie przez wybieranie wielokrotnie wybiera minimalny element z nieposortowanej reszty i umieszcza go na początku, co wymaga dostępu do całego wejścia; jest więc algorytmem offline. Z drugiej strony, sortowanie przez wstawianie bierze pod uwagę jeden element wejściowy na iterację i tworzy częściowe rozwiązanie bez uwzględniania przyszłych elementów. Zatem sortowanie przez wstawianie jest algorytmem online.
Zauważ, że końcowy wynik sortowania przez wstawianie jest optymalny, tj. Poprawnie posortowana lista. W przypadku wielu problemów algorytmy online nie są w stanie dorównać wydajności algorytmów offline. Jeśli stosunek wydajności algorytmu online do optymalnego algorytmu offline jest ograniczony, algorytm online nazywany jest konkurencyjnym .
Nie każdy algorytm offline ma skuteczny odpowiednik online .
Definicja
Ponieważ algorytm online nie zna wszystkich danych wejściowych, jest zmuszony do podejmowania decyzji, które później mogą okazać się nieoptymalne, a badanie algorytmów online skupiło się na jakości podejmowania decyzji, która jest możliwa w tym otoczeniu. Analiza konkurencji formalizuje ten pomysł, porównując względną wydajność algorytmu online i offline dla tego samego wystąpienia problemu. Konkretnie, współczynnik konkurencyjności algorytmu definiuje się jako stosunek kosztu najgorszego przypadku podzielony przez koszt optymalny, obejmujący wszystkie możliwe nakłady. Współczynnik konkurencyjności problemu online to najlepszy współczynnik konkurencyjności osiągnięty przez algorytm online. Intuicyjnie współczynnik konkurencyjności algorytmu daje miarę jakości rozwiązań wytwarzanych przez ten algorytm, podczas gdy współczynnik konkurencyjności problemu pokazuje, jak ważne jest poznanie przyszłości dla tego problemu.
Inne interpretacje
Aby zapoznać się z innymi punktami widzenia na temat danych wejściowych online do algorytmów , patrz
- algorytm przesyłania strumieniowego : skupienie się na ilości pamięci potrzebnej do dokładnego odwzorowania danych wejściowych z przeszłości;
- algorytm dynamiczny : skupienie się na złożoności czasowej utrzymywania rozwiązań problemów z danymi wejściowymi online.
Przykłady
Niektóre algorytmy online :
- Sortowanie przez wstawianie
- Perceptron
- Pobieranie próbek ze zbiornika
- Algorytm chciwy
- Model przeciwnika
- Metryczne systemy zadań
- Algorytm kursów
- Algorytm zamiany stron
- Algorytmy obliczania wariancji
- Algorytm Ukkonena
Problemy online
Problemem ilustrującym koncepcje algorytmów online jest Canadian Traveler Problem . Celem tego problemu jest zminimalizowanie kosztów osiągnięcia celu na wykresie ważonym, gdzie niektóre krawędzie są niewiarygodne i mogły zostać usunięte z wykresu. Jednak informacja, że krawędź została usunięta ( nie powiodła się ), jest ujawniana podróżnemu tylko wtedy , gdy osiągnie jeden z jej punktów końcowych. Najgorszym przypadkiem tego problemu jest po prostu to, że wszystkie niewiarygodne krawędzie zawodzą i problem sprowadza się do zwykłego problemu najkrótszej ścieżki . Alternatywną analizę problemu można przeprowadzić za pomocą analizy konkurencji. W przypadku tej metody analizy algorytm offline wie z wyprzedzeniem, które krawędzie ulegną awarii, a celem jest zminimalizowanie stosunku między wydajnością algorytmów online i offline. Ten problem jest kompletny w PSPACE .
Istnieje wiele formalnych problemów, które oferują więcej niż jeden algorytm online jako rozwiązanie:
- Problem z serwerem k
- Problem z harmonogramowaniem w warsztacie
- Problem z aktualizacją listy
- Problem z bandytami
- Problem sekretarki
- Szukaj gier
- Problem z wypożyczeniem nart
- Problem wyszukiwania liniowego
- Problem wyboru portfela
Zobacz też
- Algorytm dynamiczny
- Algorytm przesyłania strumieniowego
- Prosty interfejs API dla XML
- Obliczenia w czasie rzeczywistym
- Algorytm sekwencyjny
- Uczenie maszynowe online / uczenie offline
Bibliografia
- Borodin, A .; El-Yaniv, R. (1998). Obliczenia online i analiza konkurencji . Cambridge University Press. ISBN 0-521-56392-5 .