Online-algoritmi

Tietojenkäsittelytieteessä online-algoritmeihin kuuluva algoritmi käsittelee syötettä järjestyksessä alkio kerrallaan. Kullakin hetkellä vain siihen mennessä syötettyjä alkioita voidaan käyttää senhetkisen lopputuloksen tuottamiseen. 

Offline-algoritmille taas annetaan koko syöte kerralla. Operatiivisessa tutkimuksessa aluetta, jolla online-algoritmeja kehitetään, kutsutaan online-optimoinniksi. 

Tarkastellaan esimerkiksi lajittelualgoritmien valinta- ja lisäyslajittelua: valintalajittelu valitsee toistuvasti pienimmän elementin lajittelemattomasta jäännöksestä ja sijoittaa sen ensimmäiseksi, mikä edellyttää pääsyä koko syötteeseen; se on siis offline-algoritmi.  Lisäyslajittelu taas käsittelee yksittäistä syötealkiota iteraatiota kohti asettaen sen oikeaan paikkaan jonossa ja tuottaa näin osittaisen ratkaisun huomioimatta tulevia alkioita. Siten lisäyslajittelu on online-algoritmi. 

Huomaa, että lisäyslajittelu tuottaa optimaalisen tuloksen eli oikein järjestetyn luettelon.  Monien ongelmien tapauksessa online-algoritmien tulos ei vastaa offline-algoritmien tulosta.  Jos online-algoritmin ja optimaalisen offline-algoritmin suorituskykyjen välinen suhde on rajattu, online-algoritmia kutsutaan kilpailukykyiseksi.  

Kaikilla offline-algoritmeilla ei ole tehokasta online-vastinetta.

Määritelmä 
Online-algoritmien päätökset eivät välttämättä ole optimaalisia verrattuna offline-algoritmeihin. Online-algoritmien tutkimus on keskittynyt tarkastelemaan saavutettavissa olevaa päätöksenteon laatua. Kilpailuanalyysi muodollistaa ajatuksen vertaamalla online- ja offline-algoritmin kustannuksia samaan ongelmaan sovellettuna, missä kustannus on määritelty ongelmaan sopivalla tavalla. Kilpasuhde (competitive ratio) määritellään pahimman tapauksen kustannuksen suhteena optimaaliseen kustannukseen. Online-ongelman kilpasuhde määritellään parhaaksi mielivaltaisella online-algoritmilla saavutettavaksi kilpasuhteeksi.  Intuitiivisesti algoritmin kilpasuhde kuvaa algoritmin tuottamien ratkaisujen laatua, kun taas ongelman kilpasuhde osoittaa, kuinka ratkaisevaa olisi tietää myös tuleva syöte.

Muita tulkintoja 
Muita näkökulmia online-syötteistä algoritmeille ovat 

 striimaus-algoritmi: tarkastelun kohteena aiempien syötteiden täsmälliseen esittämiseen tarvittava muistin määrä 
 dynaaminen algoritmi : tarkastelun kohteena laskennallinen kompleksisuus ajan suhteen kun ylläpidetään ratkaisua online-syötteitä käsitellessä

Esimerkkejä 
Eräitä online-algoritmeja: 

 Lisäyslajittelu 
 Perceptron 
 Säiliön näytteenotto 
 Ahne algoritmi 
 Vastakkainen malli 
 Metriset tehtäväjärjestelmät 
 Odds-algoritmi 
 Sivun vaihtoalgoritmi 
 Algoritmit varianssin laskemiseksi 
 Ukkosen algoritmi

Online-ongelmat 
Niin kutsuttu Kanadalainen matkustajaongelma havainnollistaa online-algoritmin käsitettä. Ongelmana on minimoida kohdesolmun saavuttamisesta aiheutuva kustannus painotetussa verkossa, kun jotkut reunat ovat epäluotettavia ja mahdollisesti poistettu verkosta. Tosiasia, että reuna on poistettu ( epäonnistunut ) paljastuu matkustajalle vasta hänen saavuttaessaan jonkin kyseisen reunan solmuista. Pahimmassa tapauksessa kaikki epäluotettavat reunat epäonnistuvat ja ongelma pelkistyy tavalliseen lyhimmän polun ongelmaan .  Kilpailuanalyysin avulla voidaan tehdä vaihtoehtoinen analyysi ongelmasta. Tällöin offline-algoritmi tietää etukäteen, mitkä reunat epäonnistuvat. Tavoitteena on minimoida online- ja offline-algoritmien suorituskyvyn suhde. Kyseinen ongelma on PSPACE-täydellinen. 

On monia muodollisia ongelmia, joihin on ratkaisuna useampia online-algoritmeja: 

 K-palvelimen ongelma 
 Työn myymälän aikataulutusongelma 
 Luettelo päivitysongelmasta 
 Bandit-ongelma 
 Sihteeri-ongelma 
 Etsi pelejä 
 Hiihtovuokrausongelma 
 Lineaarisen haun ongelma 
 Portfolion valinnan ongelma

Lähteet

Viitteet

Aiheesta muualla 
 Online-algoritmeja koskevien julkaisujen bibliografia 

Algoritmit
Sivut, joissa on tarkistamattomia käännöksiä
Tietojenkäsittelytiede