Paras vastaus
Luokittelu käyttötarkoituksen mukaan
Jokaisella algoritmilla on tavoite, esimerkiksi pikalajittelualgoritmin tarkoituksena on lajitella tietoja nousevassa tai laskevassa järjestyksessä. Mutta tavoitteiden määrä on rajaton, ja meidän on ryhmiteltävä ne erilaisten tarkoitusten mukaan.
Luokittelu toteutuksen mukaan
Algoritmi voidaan toteuttaa eri perusperiaatteiden mukaisesti.
- Rekursiivinen tai iteratiivinen Rekursiivinen algoritmi on se, joka kutsuu itseään toistuvasti, kunnes tietty ehto täsmää. Se on toiminnalliselle ohjelmoinnille yhteinen menetelmä. Iteratiiviset algoritmit käyttävät toistuvia rakenteita, kuten silmukoita. Jotkut ongelmat sopivat paremmin yhteen tai toiseen toteutukseen. Esimerkiksi hanoi-ongelman tornit ymmärretään hyvin rekursiivisessa toteutuksessa. Jokaisella rekursiivisella versiolla on iteratiivinen vastaava iteratiivinen ja päinvastoin.
- Looginen tai menettelytapa Algoritmia voidaan pitää hallittuna loogisena deduktiona. Looginen komponentti ilmaisee aksioomat, joita voidaan käyttää laskennassa, ja ohjauskomponentti määrittää tavan, jolla vähennys kohdistetaan aksiomeihin. Tämä on loogisen ohjelmoinnin perusta. Puhtaissa logiikan ohjelmointikielissä ohjauskomponentti on kiinteä ja algoritmit määritetään toimittamalla vain logiikkakomponentti.
- Sarja tai rinnakkaiset algoritmeista keskustellaan yleensä olettaen, että tietokoneet suorittavat yhden algoritmin käskyn kerrallaan. Tämä on sarjaalgoritmi, toisin kuin rinnakkaisalgoritmit, jotka hyödyntävät tietokonearkkitehtuureja käsittelemään useita käskyjä kerralla. He jakavat ongelman alaongelmiin ja välittävät ne useille prosessoreille. Iteratiiviset algoritmit ovat yleensä rinnakkaisia. Lajittelualgoritmit voidaan rinnastaa tehokkaasti.
- Deterministinen tai ei-deterministinen Deterministiset algoritmit ratkaisevat ongelman ennalta määritetyllä prosessilla, kun taas ei-deterministisen algoritmin on arvattava paras ratkaisu kussakin vaiheessa heuristiikan avulla.
Luokittelu suunnitteluparadigman mukaan
Suunnitteluparadigma on tutkimusalue tai ongelmaluokka, joka vaatii erillisen algoritmin:
- Divide and Conquer Divide and Conquer -algoritmi pelkistää ongelman esiintymän toistuvasti yhdeksi tai useammaksi saman ongelman pienemmäksi esiintymäksi (yleensä rekursiivisesti), kunnes esiintymät ovat riittävän pieniä ratkaista helposti. Yksi tällainen esimerkki jakamisesta ja valloittamisesta on yhdistämislajittelu. Lajittelu voidaan tehdä jokaiselle tietosegmentille sen jälkeen, kun data on jaettu segmentteihin, ja koko tieto voidaan lajitella valloitusvaiheessa yhdistämällä ne. Binaarihakualgoritmi on esimerkki jakamisen ja valloittamisen muunnoksesta, nimeltään pienennys ja valloitusalgoritmi , joka ratkaisee identtisen alaongelman ja ratkaisee tämän osaongelman ratkaisun. isompi ongelma.
- Dynaaminen ohjelmointi Painotetun kaavion lyhin polku löytyy käyttämällä lyhintä polkua tavoitteeseen kaikista vierekkäisistä kärjet. Kun optimaalinen ratkaisu ongelmaan voidaan muodostaa optimaalisista ratkaisuista osahäiriöihin, dynaamisen ohjelmoinnin avulla vältetään jo lasketut uudelleenratkaisut. – Tärkein ero ”jaa ja valloita” -lähestymistavassa on, että osaongelmat ovat toisistaan riippumattomia jakautumisessa ja valloittamisessa, kun dynaamisessa ohjelmoinnissa esiintyy osaongelmien päällekkäisyyttä. – Dynaaminen ohjelmointi ja muistiinpano menevät yhteen. Ero suoraviivaiseen rekursioon on rekursiivisten puheluiden välimuistiin tallentamisessa tai muistiinpanossa. Jos osaongelmat ovat riippumattomia, tämä on hyödytöntä. Käyttämällä muistiinpanoa tai ylläpitämällä jo ratkaistun osaongelmien taulukkoa dynaaminen ohjelmointi vähentää monien ongelmien eksponentiaalisen luonteen polynomimutkaisuuteen.
- Ahne menetelmä Ahne algoritmi on samanlainen kuin dynaaminen ohjelmointialgoritmi, mutta ero on siinä, että ratkaisuja alakysymyksiin ei tarvitse tietää kussakin vaiheessa. Sen sijaan ”ahne” valinta voidaan tehdä siitä, mikä näyttää parhaimmalta ratkaisulta tällä hetkellä. Suosituin ahne algoritmi on löytää Kruskalin antama vähimmäispinta-ala.
- Lineaarinen ohjelmointi Ongelma ilmaistaan lineaarisena joukona. eriarvoisuutta ja sitten yritetään maksimoida tai minimoida panokset. Tämä voi ratkaista monia ongelmia, kuten suunnattujen kaavioiden maksimivirta, erityisesti käyttämällä yksinkertaisella algoritmilla.Monimutkaista lineaarisen ohjelmoinnin varianttia kutsutaan kokonaislukuohjelmoinniksi, jossa ratkaisutila on rajoitettu kaikkiin kokonaislukuihin.
- Reduction kutsutaan myös nimellä muuntaminen ja valloittaminen Ratkaise ongelma muuttamalla se uudeksi ongelmaksi. Yksinkertainen esimerkki: mediaanin löytäminen lajittelemattomasta luettelosta tarkoittaa tämän ongelman muuttamista ensin lajitteluongelmaksi ja keskimmäisen elementin löytämistä lajitellusta luettelosta. Pelkistyksen päätavoitteena on löytää mahdollisimman yksinkertainen muunnos.
- Kaavioiden käyttäminen Monet ongelmat, kuten shakkipelaaminen, voidaan mallintaa ongelmiksi. kaavioissa. Käytetään graafin etsintäalgoritmeja. Tähän luokkaan kuuluvat myös hakualgoritmit ja takaisku.
- Todennäköinen ja heuristinen paradigma Todennäköisyys Ne, jotka tekevät joitain valintoja satunnaisesti. Geneettinen Yritä löytää ratkaisuja ongelmiin jäljittelemällä biologisia evoluutioprosesseja satunnaisten mutaatioiden syklin avulla, joka tuottaa peräkkäisiä ”ratkaisujen” sukupolvia. Siten he jäljittelevät lisääntymistä ja ”parhaan selviytymistä”. Heuristinen joiden yleinen tarkoitus ei ole löytää optimaalista ratkaisua, vaan likimääräinen ratkaisu, jossa aika tai resurssit täydellisen ratkaisun löytämiseen eivät ole käytännöllisiä.
Luokittelu monimutkaisuuden mukaan
Jotkut algoritmit täydentyvät lineaarisessa ja toiset eksponentiaalisessa ajassa, ja jotkut eivät koskaan täydennä.
Lähde: Algoritmien luokitus
Vastaus
Seuraava on toinen tapa luokitella algoritmeja.
Kilpailevassa ohjelmoinnissa on 4 pääongelmaa- paradigmojen ratkaiseminen.
Toisin sanoen, tässä annetaan ongelman vuoksi erilaisia lähestymistapoja / työkaluja, joita sinun on käytettävä sen ratkaisemiseksi.
- Brute Force / Täydellinen haku: menetelmä, joka tarkastelee kaikkia mahdollisuuksia ja valitsee parhaan ratkaisun.
- Plussat: yksinkertainen, pitäisi aina löytää ratkaisu, koska tarkastelet kaikkia mahdollisuuksia
- Haitat : mahdotonta, koska mahdollisuuksien määrä kasvaa räjähdysmäisesti kohteiden määrän kasvaessa
- Jaa ja valloita: menetelmä, joka jakaa ongelman pienempiin osiin ja ratkaisee sitten ne osat. Ajattele binaarihakua.
- Ahne lähestymistapa: menetelmä, joka valitsee parhaimman vaihtoehdon tällä hetkellä ilman tulevaisuuden harkintaa.
- Plussat: nopea, yksinkertainen, voi saada parhaan ratkaisun tai saada jonkin verran yhteyttä
- Haitat: useimmiten emme saa parasta ratkaisua.
- Dynaaminen ohjelmointi: Menetelmä, joka rakentuu ratkaisuun käyttämällä aiemmin löydettyjä alaratkaisuja. Ehdottomasti yksi edistyneemmistä tekniikoista, mutta erittäin tehokas ja sovellettavissa.
- Plussat: löytää optimaalisen ratkaisun moniin ongelmiin polynomiajassa ( kun taas raakaa voimaa vaatisi eksponentiaalinen)
- Haitat : vaikea ymmärtää ja soveltaa, vie aikaa eri tilojen ja toistumisen ymmärtämiseen
Lähteet
Halim, Steven ja Felix Halim. Kilpailukykyinen ohjelmointi: Ohjelmointikilpailujen uusi alaraja . Lulu, 2013.