Legjobb válasz
Cél szerinti osztályozás
Minden algoritmusnak van célja, például a Quick Sort algoritmus célja az adatok növekvő vagy csökkenő sorrendbe rendezése. De a célok száma végtelen, és ezeket célok szerint kell csoportosítanunk.
Besorolás megvalósítás szerint
Egy algoritmust különböző alapelvek szerint lehet megvalósítani.
- Rekurzív vagy iteratív A rekurzív algoritmus olyan, amely ismételten hívja magát, amíg egy bizonyos feltétel meg nem felel. Ez egy funkcionális programozási módszer. Az iteratív algoritmusok ismétlődő konstrukciókat használnak, mint a hurkok. Bizonyos problémák jobban megfelelnek egyik vagy másik megvalósításnak. Például a hanoi-tornyok jól értelmezhetők a rekurzív megvalósításban. Minden rekurzív változatnak van iteratív egyenértékű iteratívja, és fordítva.
- Logical vagy eljárási Az algoritmus ellenőrzött logikai dedukciónak tekinthető. Egy logikai komponens fejezi ki a számításban felhasználható axiómákat, és egy vezérlő komponens határozza meg a levonás alkalmazásának módját az axiómákra. Ez az alapja a logikai programozásnak. A tiszta logikai programozási nyelvekben a vezérlő komponens fix és az algoritmusok csak a logikai összetevő megadásával határozhatók meg.
- Soros vagy párhuzamos algoritmusokat általában azzal a feltételezéssel vitatják meg, hogy a számítógépek egyszerre hajtanak végre egy algoritmust. Ez egy soros algoritmus, szemben a párhuzamos algoritmusokkal, amelyek a számítógépes architektúrák előnyeit kihasználva egyszerre több utasítást dolgoznak fel. Felosztják a problémát részproblémákra, és továbbadják azokat több processzornak. Az iteratív algoritmusok általában párhuzamosak. A rendezési algoritmusok hatékonyan párhuzamosíthatók.
- Determinisztikus vagy nem determinisztikus A determinisztikus algoritmusok előre meghatározott eljárással oldják meg a problémát, míg a nem determinisztikus algoritmusoknak a heurisztika használatával kell kitalálniuk a legjobb megoldást minden lépésnél.
Osztályozás tervezési paradigma szerint
A tervezési paradigma olyan terület a kutatásban vagy a problémakörben, amelyhez dedikált típusú algoritmus szükséges:
- Osztás és meghódítás Az Osztás és meghódítás algoritmus ismételten a probléma egy példányát ugyanazon probléma egy vagy több kisebb példányává redukálja (általában rekurzívan), amíg a példányok nem lesznek elég kicsi hogy könnyen megoldható legyen. A divide and conquer egyik ilyen példája az egyesítés válogatása. Rendezés elvégezhető az egyes adatszegmenseken, miután az adatokat szegmensekre osztottuk, és a teljes adatok rendezését hódítási fázisban lehet elérni, összevonva őket. A bináris keresési algoritmus az csökkentés és meghódítás algoritmus elnevezésű divide and conquer változatának a példája, amely azonos részproblémát old meg, és ennek az alproblémának a megoldását használja fel. a nagyobb probléma.
- Dinamikus programozás A súlyozott grafikon legrövidebb útja a célhoz legrövidebb utat használva található meg az összes szomszédos csúcsok. Amikor a probléma optimális megoldása az alproblémákra vonatkozó optimális megoldásokból állítható össze, a dinamikus programozással elkerülhetők a már kiszámított újratervezési megoldások. – A fő különbség az “oszd meg és hódítsd” megközelítéssel szemben az, hogy az alproblémák függetlenek az osztódás és a hódítás terén, ahol a részproblémák átfedése a dinamikus programozás során következik be. – A dinamikus programozás és a memóriák összeillenek. Az egyszerű rekurzióval való különbség a rekurzív hívások gyorsítótárazásában vagy memoizálásában rejlik. Ahol az alproblémák függetlenek, ez haszontalan. A memória használatával vagy a már megoldott részproblémák táblázatának fenntartásával a dinamikus programozás sok probléma exponenciális jellegét a polinom komplexitásig csökkenti.
- A kapzsi módszer A kapzsi algoritmus hasonló a dinamikus programozási algoritmushoz, de a különbség az, hogy az alproblémák megoldásait nem kell minden szakaszban ismerni. Ehelyett “kapzsi” döntést lehet hozni arról, ami a pillanat legjobb megoldásának tűnik. A legnépszerűbb kapzsi algoritmus a Kruskal által megadott minimális feszítőfa megtalálása.
- Lineáris programozás A problémát lineáris halmazként fejezik ki. egyenlőtlenségeket, majd megpróbálják maximalizálni vagy minimalizálni a bemeneteket. Ez számos problémát megoldhat, például az irányított grafikonok maximális áramlását, nevezetesen a szimplex algoritmus használatával.A lineáris programozás komplex változatát hívjuk egész programozásnak, ahol a megoldási terület minden egész számra korlátozódik. = “23809baed6″>