Indholdsfortegnelse:
- Definition - Hvad betyder ikke-deterministisk algoritme?
- Techopedia forklarer ikke-deterministisk algoritme
Definition - Hvad betyder ikke-deterministisk algoritme?
En ikke-deterministisk algoritme kan give forskellige output til samme input på forskellige henrettelser. I modsætning til en deterministisk algoritme, der kun producerer en enkelt output for samme input selv på forskellige kørsler, kører en ikke-deterministisk algoritme på forskellige ruter for at nå frem til de forskellige resultater.
Ikke-deterministiske algoritmer er nyttige til at finde omtrentlige løsninger, når en nøjagtig løsning er vanskelig eller dyr at udlede ved hjælp af en deterministisk algoritme.
Techopedia forklarer ikke-deterministisk algoritme
Et eksempel på en ikke-deterministisk algoritme er udførelsen af samtidige algoritmer med løbebetingelser, som kan udvise forskellige output på forskellige kørsler. I modsætning til en deterministisk algoritme, der kører en enkelt sti fra input til output, kan en ikke-deterministic algoritme tage mange stier, hvor nogle ankommer til de samme output, og andre ankommer til forskellige output. Denne funktion bruges matematisk i ikke-deterministiske beregningsmodeller som ikke-deterministisk endelig automat.
En ikke-deterministisk algoritme er i stand til udførelse på en deterministisk computer, der har et ubegrænset antal parallelle processorer. En ikke-deterministisk algoritme har normalt to faser og outputtrin. Den første fase er gætfasen, der bruger vilkårlige tegn til at køre problemet.
Den anden fase er bekræftelsesfasen, der returnerer sandt eller usant for den valgte streng. Der er mange problemer, der kan konceptualiseres ved hjælp af ikke-deterministiske algoritmer, herunder det uløste problem med P vs NP i computingsteori.
Ikke-deterministiske algoritmer bruges til at løse problemer, der tillader flere resultater. Hvert resultat, som den ikke-deterministiske algoritme producerer, er gyldig, uanset hvilke valg, algoritmen foretager under udførelsen.
