Avaa päävalikko

Tietojenkäsittelytieteessä online-algoritmeihin[1] 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. [1]

Kaikilla offline-algoritmeilla ei ole tehokasta online-vastinetta.

MääritelmäMuokkaa

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 tulkintojaMuokkaa

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äMuokkaa

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-ongelmatMuokkaa

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 [2]

Katso myösMuokkaa

  • Dynaaminen algoritmi
  • Streaming-algoritmi
  • Reaaliaikainen tietojenkäsittely
  • Peräkkäinen algoritmi
  • Verkkokoneen oppiminen / Offline-oppiminen

ViitteetMuokkaa

  1. a b Virhe: Lehtiviitemallineessa julkaisuparametri on pakollinen. [ Ohje ], {{{Vuosi}}}. http://www.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf [{{{www}}} Artikkelin verkkoversio].
  2. {{{Nimike}}}. {{{Julkaisija}}}.

Ulkoiset linkitMuokkaa