Ero sivun ”Online-algoritmi” versioiden välillä
| [katsottu versio] | [katsottu versio] |
+Luokka:Tietojenkäsittelytiede; ±Luokka:Online-algoritmit→Luokka:Algoritmit HotCat-työkalulla, + {{viitteet}}, poistettu punaiset katso myös -linkit |
Htm (keskustelu | muokkaukset) lähdeviitteet mallineisiin, osa noudettu alkueräisartikkelista |
||
| Rivi 1: | Rivi 1: | ||
[[Tietojenkäsittelytiede|Tietojenkäsittelytieteessä]] '''online-[[Algoritmi|algoritmeihin]]'''<ref name= |
[[Tietojenkäsittelytiede|Tietojenkäsittelytieteessä]] '''online-[[Algoritmi|algoritmeihin]]'''<ref name=karp92>{{Verkkoviite|osoite= http://www.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf|Tiedostomuto= PDF| Tekijä= Karp, Richard M. | Nimeke= On-Line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future? | Julkaisija= International Computer Science Institute | Selite= Esitetty World Computer Congressissa Madridissa, Espanjassa, syyskuussa 1992 | Ajankohta= 1992 | Viitattu= 26.3.2019 | Kieli= {{en}}}}</ref> 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. [[Operaatioanalyysi|Operatiivisessa tutkimuksessa]] aluetta, jolla online-algoritmeja kehitetään, kutsutaan online-optimoinniksi. |
'''Offline-algoritmille''' taas annetaan koko syöte kerralla. [[Operaatioanalyysi|Operatiivisessa tutkimuksessa]] aluetta, jolla online-algoritmeja kehitetään, kutsutaan online-optimoinniksi. |
||
| Rivi 5: | Rivi 5: | ||
Tarkastellaan esimerkiksi [[Lajittelualgoritmi|lajittelualgoritmien]] [[Valintalajittelu|valinta-]] ja [[Lisäyslajittelu|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. |
Tarkastellaan esimerkiksi [[Lajittelualgoritmi|lajittelualgoritmien]] [[Valintalajittelu|valinta-]] ja [[Lisäyslajittelu|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. <ref name= |
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. <ref name=karp92/> |
||
Kaikilla ''offline-algoritmeilla'' ei ole tehokasta ''online-''vastinetta. |
Kaikilla ''offline-algoritmeilla'' ei ole tehokasta ''online-''vastinetta. |
||
| Rivi 45: | Rivi 45: | ||
* Hiihtovuokrausongelma |
* Hiihtovuokrausongelma |
||
* Lineaarisen haun ongelma |
* Lineaarisen haun ongelma |
||
* Portfolion valinnan ongelma<ref name=doc16>{{Kirjaviite|Tekijä= Dochow, Robert|Nimeke= Online Algorithms for the Portfolio Selection Problem| Vuosi= 2016 |Julkaisupaikka = Wiesbaden | Julkaisija= Springer Gabler|Isbn= 978-3-658-13528-7 |www= https://www.springer.com/de/book/9783658135270 | www-teksti = Teoksen esittely julkaisijan sivulla | Kieli = {{en}}}}</ref> |
|||
* Portfolion valinnan ongelma <ref name="doc16">{{Kirjaviite|}}</ref> |
|||
== Lähteet == |
== Lähteet == |
||
* {{Kirjaviite|Tekijä= Borodin, Allan & El-Yaniv, R. | Nimeke= Online Computation and Competitive Analysis | Julkaisija= Cambridge University Press | Vuosi = 1998 | Isbn = 0-521-56392-5 | www= https://www.cs.technion.ac.il/~rani/book.html | www-teksti = Teoksen esittely | Kieli= {{en}}}} |
|||
=== Viitteet === |
|||
{{Viitteet}} |
{{Viitteet}} |
||
* {{Kirjaviite|Isbn=0-521-56392-5}} |
|||
== Aiheesta muualla == |
== Aiheesta muualla == |
||
* [http://www.cs.ucr.edu/~marek/pubs/online.bib Online-algoritmeja koskevien julkaisujen bibliografia] |
* [http://www.cs.ucr.edu/~marek/pubs/online.bib Online-algoritmeja koskevien julkaisujen bibliografia] |
||
Nykyinen versio 30. lokakuuta 2022 kello 17.30
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 | muokkaa wikitekstiä]
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[muokkaa | muokkaa wikitekstiä]
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 | muokkaa wikitekstiä]
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[muokkaa | muokkaa wikitekstiä]
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]
Lähteet[muokkaa | muokkaa wikitekstiä]
- Borodin, Allan & El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, 1998. ISBN 0-521-56392-5. Teoksen esittely. (englanniksi)
Viitteet[muokkaa | muokkaa wikitekstiä]
- ↑ a b Karp, Richard M.: On-Line Algorithms Versus Off-Line Algorithms: How Much is it Worth to Know the Future? (Esitetty World Computer Congressissa Madridissa, Espanjassa, syyskuussa 1992) 1992. International Computer Science Institute. Viitattu 26.3.2019. (englanniksi)
- ↑ Dochow, Robert: Online Algorithms for the Portfolio Selection Problem. Wiesbaden: Springer Gabler, 2016. ISBN 978-3-658-13528-7. Teoksen esittely julkaisijan sivulla. (englanniksi)