Online-algoritmi - Online algorithm

Vuonna tietojenkäsittelytiede , An online-algoritmi on sellainen, joka pystyy käsittelemään sen panos pala palalta sarjasiirrännällä eli siinä järjestyksessä, että tulo syötetään algoritmi , ilman koko tulo käytettävissä alusta alkaen.

Sitä vastoin offline-algoritmille annetaan koko ongelmadata alusta alkaen, ja sitä tarvitaan vastauksen tuottamiseen, joka ratkaisee käsillä olevan ongelman. In Operations Research , alue, jolla verkossa algoritmeja kehitetään kutsutaan verkossa optimointi .

Harkitse esimerkkinä lajittelualgoritmien valintalajittelu ja lisäyslajittelu : valintalajittelu valitsee toistuvasti vähimmäiselementin lajittelemattomasta jäännöksestä ja sijoittaa sen eteen, mikä edellyttää pääsyä koko syötteeseen; se on siis offline-algoritmi. Toisaalta lisäyslajittelu ottaa huomioon yhden syöttöelementin iteraatiota kohden ja tuottaa osittaisen ratkaisun ottamatta huomioon tulevia elementtejä. Siten lisäyslajittelu on online-algoritmi.

Huomaa, että lisäyslajittelun lopputulos on optimaalinen, eli oikein lajiteltu luettelo. Monissa ongelmissa online-algoritmit eivät voi vastata offline-algoritmien suorituskykyä. Jos online-algoritmin suorituskyvyn ja optimaalisen offline-algoritmin suhde on rajattu, online-algoritmia kutsutaan kilpailukykyiseksi .

Kaikilla offline-algoritmeilla ei ole tehokasta online- vastinetta.

Määritelmä

Koska online-algoritmi ei tiedä koko syötettä, se on pakko tehdä päätöksiä, jotka saattavat myöhemmin osoittautua optimaalisiksi, ja online-algoritmien tutkimus on keskittynyt päätöksenteon laatuun, joka on mahdollista tässä ympäristössä. Kilpailuanalyysi muodostaa tämän idean vertaamalla online- ja offline-algoritmien suhteellista suorituskykyä samaan ongelma-ilmentymään. Tarkemmin sanottuna algoritmin kilpailusuhde määritellään sen kustannusten pahimmassa tapauksessa jaettuna optimaalisilla kustannuksilla kaikkiin mahdollisiin panoksiin. Verkko-ongelman kilpailusuhde on paras online-algoritmilla saavutettu kilpailusuhde. Intuitiivisesti algoritmin kilpailusuhde mittaa tämän algoritmin tuottamien ratkaisujen laatua, kun taas ongelman kilpailusuhde osoittaa tämän ongelman tulevaisuuden tuntemisen tärkeyden.

Muut tulkinnat

Katso muut näkökohdat algoritmien online-syötteistä kohdasta

  • suoratoistoalgoritmi : keskittyminen muistin määrään, joka tarvitaan menneiden syötteiden tarkkaan esittämiseen;
  • dynaaminen algoritmi : keskitytään online-syötteiden ongelmien ratkaisujen ylläpitämisen ajan monimutkaisuuteen.

Esimerkkejä

Joitakin online-algoritmeja :

Verkko-ongelmat

Ongelma esimerkkinä online-algoritmien käsitteistä on Kanadan matkailijoiden ongelma . Tämän ongelman tavoitteena on minimoida tavoitteen saavuttamisesta aiheutuvat kustannukset painotetussa kuvaajassa, jossa jotkin reunat eivät ole luotettavia ja ne on voitu poistaa kaaviosta. Reuna on poistettu ( epäonnistunut ) paljastetaan kuitenkin matkustajalle vasta, kun hän saavuttaa yhden reunan päätepisteistä. Pahin tapaus tälle ongelmalle on yksinkertaisesti se, että kaikki epäluotettavat reunat epäonnistuvat ja ongelma pienenee tavalliseksi lyhimmän polun ongelmaksi . Vaihtoehtoinen ongelma-analyysi voidaan tehdä kilpailuanalyysin avulla. Tätä analyysimenetelmää varten offline-algoritmi tietää etukäteen mitkä reunat epäonnistuvat, ja tavoitteena on minimoida online- ja offline-algoritmien suorituskyvyn suhde. Tämä ongelma on PSPACE-täydellinen .

On monia muodollisia ongelmia, jotka tarjoavat ratkaisuksi useamman kuin yhden online-algoritmin :

Katso myös

Viitteet

Ulkoiset linkit