Turinys:
Apibrėžimas - ką reiškia nenustatytas algoritmas?
Nedeterministinis algoritmas gali pateikti skirtingus išvedimus tam pačiam įėjimui skirtingose vykdymo vietose. Skirtingai nuo deterministinio algoritmo, kuris sukuria tik vieną išvestį tam pačiam įėjimui net ir skirtingais atvejais, nedeterministinis algoritmas keliauja įvairiais maršrutais, kad pasiektų skirtingus rezultatus.
Nedeterministiniai algoritmai yra naudingi ieškant apytikslių sprendimų, kai sunku nustatyti ar brangų tikslų sprendimą naudojant deterministinį algoritmą.
„Techopedia“ paaiškina nenustatytą algoritmą
Vienas nedeterinistinio algoritmo pavyzdys yra lygiagrečių algoritmų su lenktynių sąlygomis vykdymas, kuris skirtinguose važiavimuose gali parodyti skirtingus išėjimus. Skirtingai nuo deterministinio algoritmo, kuris eina vienu keliu nuo įvesties iki išėjimo, nedeterministinis algoritmas gali eiti daugybe kelių, kai kurie ateina į tuos pačius išėjimus, o kiti - į skirtingus išėjimus. Ši savybė yra matematiškai naudojama nedeterinistiniuose skaičiavimo modeliuose, tokiuose kaip nedeterministinis baigtinis automatas.
Nedeterinistinis algoritmas gali būti vykdomas deterministiniame kompiuteryje, kuriame yra neribotas skaičius lygiagrečių procesorių. Nedeterministinis algoritmas paprastai turi dvi fazes ir išvesties pakopas. Pirmasis etapas yra atspėjimo fazė, kurios metu problemai spręsti naudojami savavališki simboliai.
Antrasis etapas yra tikrinimo fazė, kuri grąžina teisingą arba klaidingą pasirinktai eilutei. Yra daugybė problemų, kurias galima apibrėžti pasitelkiant nedeterministinius algoritmus, įskaitant neišspręstą P vs NP problemą skaičiavimo teorijoje.
Nedeteinistiniai algoritmai naudojami sprendžiant problemas, kurios leidžia pasiekti įvairius rezultatus. Kiekvienas rezultatas, kurį sukuria nedeterministinis algoritmas, yra pagrįstas, neatsižvelgiant į algoritmo pasirinkimus vykdymo metu.
