Online-algoritme

Dit artikel gaat over de beschikbaarheid van invoer voor een algoritme; het onderscheid online/offline wordt ook gebruikt voor taken die 'van tevoren' of 'live' worden uitgevoerd, bijvoorbeeld het (voor)bewerken van data.

In de informatica is een online-algoritme een algoritme waarbij de invoer niet geheel bekend hoeft te zijn wanneer het algoritme begint. Dit staat tegenover een offline-algoritme waarbij de gehele invoer bekend moet zijn voordat het algoritme kan beginnen. Zo kan insertion sort bijvoorbeeld geïmplementeerd worden als een online-algoritme terwijl dat bij selection sort niet mogelijk is (bij selection sort moet de lijst geheel bekend zijn, bij insertion sort niet). Bij online-algoritmen kan het zijn dat het antwoord niet optimaal is aangezien niet alle informatie van tevoren bekend is.

Voorbeelden

Enkele andere voorbeelden van online-algoritmen zijn:

• Het vinden van een pad in een eindige graaf waarbij de knopen en kanten niet van tevoren bekend zijn (bijvoorbeeld bij robots die een plattegrond opbouwen in een onbekende omgeving)
• Optimaliseringsproblemen, zoals het inpakken van vrachtwagen waarbij men aan elk object een plaatst toekent in de volgorde dat de objecten binnenkomen
• Algoritmen op het gebied van machinaal leren
• Navigatie van webspiders over het World Wide Web

Analyse

De competiviteit van online-algoritmen wordt gebruikt om de kwaliteit van online-algoritmen te analyseren. Hierbij worden de prestaties van het algoritme vergeleken met het optimale antwoord dat men zou kunnen verkrijgen als alle informatie van tevoren bekend was. Men analyseert hoe goed het algoritme presteert op gunstige, gemiddelde en slechte invoer en hoe ver het gegeven antwoord kan afwijken van het optimale antwoord.

Zo kan het zijn dat een online-algoritme theoretisch zeer slechte antwoorden kan geven maar dat dit alleen voorkomt bij invoer die in werkelijkheid niet of nauwelijks zal voorkomen; een online-algoritme kan hierdoor een verbetering zijn in vergelijking met een offline-algoritme (zoals tijdwinst en de daarmee gepaard gaande besparing van kosten).

Deze aanpak lijkt op de analyse die gedaan wordt voor benaderingsalgoritmen waarbij de benadering van het antwoord wordt vergeleken met het werkelijke antwoord.