Optymalizacja online

Optymalizacja online to dziedzina teorii optymalizacji , bardziej popularna w informatyce i badaniach operacyjnych , która zajmuje się problemami optymalizacyjnymi bez lub z niepełną wiedzą o przyszłości (online). Tego rodzaju problemy są określane jako problemy online i są postrzegane jako przeciwieństwo klasycznych problemów optymalizacyjnych, w których zakłada się kompletną informację (offline). Badania nad optymalizacją online można podzielić na problemy online, w których wiele decyzji jest podejmowanych sekwencyjnie na podstawie danych wejściowych kawałek po kawałku oraz takie, w których decyzja jest podejmowana tylko raz. Słynny problem online, w którym decyzja jest podejmowana tylko raz, to tzw Problem z wypożyczalnią nart . Ogólnie rzecz biorąc, wynik algorytmu online porównuje się z rozwiązaniem odpowiedniego algorytmu offline, który z konieczności jest zawsze optymalny i zna z góry całe dane wejściowe (analiza konkurencyjna).

W wielu sytuacjach obecne decyzje (np. alokacja zasobów) muszą być podejmowane przy niepełnej wiedzy na temat przyszłości lub założenia dotyczące dystrybucji w przyszłości nie są wiarygodne. W takich przypadkach można zastosować optymalizację online, która różni się od innych podejść, takich jak optymalizacja solidna , optymalizacja stochastyczna i procesy decyzyjne Markowa .

Problemy z Internetem

Problemem ilustrującym koncepcje algorytmów online jest kanadyjski problem podróżnika . Celem tego problemu jest zminimalizowanie kosztów dotarcia do celu na grafie ważonym, w którym niektóre krawędzie są niewiarygodne i mogły zostać usunięte z grafu. Jednak fakt, że krawędź została usunięta ( nie powiodło się ) zostaje ujawniony podróżnikowi dopiero po dotarciu do jednego z punktów końcowych krawędzi. Najgorszym przypadkiem tego problemu jest po prostu to, że wszystkie niewiarygodne krawędzie zawodzą, a problem sprowadza się do zwykłego problemu z najkrótszą ścieżką . Alternatywną analizę problemu można przeprowadzić za pomocą analizy konkurencji. W przypadku tej metody analizy algorytm offline wie z góry, które krawędzie zawiodą, a celem jest zminimalizowanie stosunku między wydajnością algorytmów online i offline. Ten problem jest PSPACE-zupełny .

Istnieje wiele problemów formalnych, które oferują więcej niż jeden algorytm online jako rozwiązanie:

Zobacz też