Inhoudsopgave:
- Definitie - Wat betekent niet-deterministisch algoritme?
- Techopedia verklaart niet-deterministisch algoritme
Definitie - Wat betekent niet-deterministisch algoritme?
Een niet-deterministisch algoritme kan verschillende uitgangen bieden voor dezelfde ingang bij verschillende uitvoeringen. In tegenstelling tot een deterministisch algoritme dat slechts één uitvoer produceert voor dezelfde invoer, zelfs bij verschillende runs, reist een niet-deterministisch algoritme in verschillende routes om tot de verschillende resultaten te komen.
Niet-deterministische algoritmen zijn nuttig voor het vinden van oplossingen bij benadering, wanneer een exacte oplossing moeilijk of duur is om af te leiden met behulp van een deterministisch algoritme.
Techopedia verklaart niet-deterministisch algoritme
Een voorbeeld van een niet-deterministisch algoritme is de uitvoering van gelijktijdige algoritmen met race-omstandigheden, die verschillende uitvoer kunnen vertonen bij verschillende runs. In tegenstelling tot een deterministisch algoritme dat een enkel pad van invoer naar uitvoer aflegt, kan een niet-deterministisch algoritme vele paden nemen, waarvan sommige aankomen op dezelfde uitgangen en anderen aankomen op verschillende uitgangen. Deze functie wordt wiskundig gebruikt in niet-deterministische berekeningsmodellen zoals niet-deterministische eindige automaten.
Een niet-deterministisch algoritme kan worden uitgevoerd op een deterministische computer met een onbeperkt aantal parallelle processors. Een niet-deterministisch algoritme heeft meestal twee fasen en outputstappen. De eerste fase is de gokfase, waarbij willekeurige tekens worden gebruikt om het probleem op te lossen.
De tweede fase is de controlefase, die waar of onwaar retourneert voor de gekozen string. Er zijn veel problemen die kunnen worden geconceptualiseerd met behulp van niet-deterministische algoritmen, waaronder het onopgeloste probleem van P vs NP in de computertheorie.
Niet-deterministische algoritmen worden gebruikt bij het oplossen van problemen die meerdere uitkomsten mogelijk maken. Elke uitkomst die het niet-deterministische algoritme produceert, is geldig, ongeacht de keuzes die het algoritme tijdens de uitvoering heeft gemaakt.
