Optymalizacja online - Online optimization

Optymalizacja online to dziedzina teorii optymalizacji , bardziej popularna w informatyce i badaniach operacyjnych , zajmująca się problematyką optymalizacji nie posiadająca lub niepełnej wiedzy o przyszłości (online). Tego rodzaju problemy są określane jako problemy online i są postrzegane w przeciwieństwie do klasycznych problemów optymalizacyjnych, w których zakłada się pełną informację (offline). Badania nad optymalizacją online można podzielić na problemy online, w których wiele decyzji podejmowanych jest sekwencyjnie na podstawie danych wejściowych kawałek po kawałku, oraz takie, w których decyzja jest podejmowana tylko raz. Znanym problemem online, w którym decyzja jest podejmowana tylko raz, jest problem wypożyczenia nart . Ogólnie rzecz biorąc, wynik algorytmu online jest porównywany z rozwiązaniem odpowiedniego algorytmu offline, który z konieczności jest zawsze optymalny i zna z góry cały sygnał wejściowy (analiza konkurencji).

W wielu sytuacjach obecne decyzje (np. alokacja zasobów) muszą być podejmowane przy niepełnej wiedzy o przyszłości lub założenia dotyczące przyszłości nie są wiarygodne. W takich przypadkach, optymalizacja w Internecie może być stosowany, który różni się od innych metod, takich jak solidnej optymalizacji , stochastycznego optymalizacji i procesy decyzyjne Markowa.

Problemy online

Problemem egzemplifikującym koncepcje algorytmów internetowych jest problem kanadyjskiego podróżnika . Celem tego problemu jest zminimalizowanie kosztów osiągnięcia celu w ważonym wykresie, w którym niektóre krawędzie są zawodne i mogły zostać usunięte z wykresu. Jednak to, że krawędź została usunięta ( nieudane ) jest ujawniane podróżnikowi dopiero po osiągnięciu jednego z punktów końcowych krawędzi. Najgorszym przypadkiem tego problemu jest po prostu to, że wszystkie zawodne krawędzie zawodzą i problem sprowadza się do zwykłego problemu z najkrótszą ścieżką . Alternatywną analizę problemu można przeprowadzić za pomocą analizy konkurencyjnej. W przypadku tej metody analizy algorytm offline wie z góry, które krawędzie zawiodą, a celem jest zminimalizowanie stosunku wydajności algorytmu online i offline. Ten problem jest kompletny PSPACE .

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

Zobacz też

Bibliografia

Ikona skrótu

Ten artykuł o informatyce jest skrótem . Możesz pomóc Wikipedii, rozwijając ją .