hajota ja hallitse -algoritmi on ongelmanratkaisustrategia, jossa monimutkainen ongelma hajotetaan pienempiin, paremmin hallittaviin osiin, ratkaistaan ​​jokainen osa erikseen ja yhdistetään sitten ratkaisut alkuperäisen ongelman ratkaisemiseksi. Se on laajalti käytetty algoritmitekniikka tietojenkäsittelytieteessä ja matematiikassa.

Esimerkki: Vuonna Yhdistä lajittelu algoritmi, hajota ja hallitse strategiaa käytetään elementtiluettelon lajitteluun. Alla oleva kuva havainnollistaa jakamisen ja yhdistämisen tilat taulukon lajittelemiseksi Yhdistä lajittelu .

verrata javan merkkijonoihin

Sisällysluettelo

• Mikä on hajota ja hallitse?
• Jaa ja hallitse -vaiheet
• Divide and Conquer -sovellukset
• Hajota ja hallitse -pelin perusteet
• Hajota ja hallitse -tavanomaiset algoritmit
• Binaarihakuun perustuvat ongelmat
• Harjoittele ongelmia Divide and Conquer -pelissä

Mikä on hajota ja hallitse -algoritmi?

Divide and Conquer on ongelmanratkaisutekniikka, joka sisältää suuremman ongelman jakamisen osaongelmiin, osaongelmien ratkaisemisen itsenäisesti ja näiden osaongelmien ratkaisujen yhdistämisen saadakseen ratkaisun suuremmalle ongelmalle.

np.zeros

Jaa ja hallitse -algoritmin vaiheet:

Divide and Conquer -algoritmi voidaan jakaa kolmeen vaiheeseen: Jakaa , Valloittaa ja Yhdistää .

1. Jaa:

• Pura alkuperäinen ongelma pienempiin osaongelmiin.
• Jokaisen osaongelman tulee edustaa osa kokonaisongelmaa.
• Tavoitteena on jakaa ongelma, kunnes se ei enää ole mahdollista.

2. Valloita:

• Ratkaise jokainen pienempi osaongelma erikseen.
• Jos aliongelma on tarpeeksi pieni (kutsutaan usein perustapaukseksi), ratkaisemme sen suoraan ilman lisärekursioita.
• Tavoitteena on löytää ratkaisuja näihin osaongelmiin itsenäisesti.

3. Yhdistä:

• Yhdistä aliongelmat saadaksesi lopullisen ratkaisun koko ongelmaan.
• Kun pienemmät osaongelmat on ratkaistu, yhdistämme niiden ratkaisut rekursiivisesti saadaksemme ratkaisun suurempaan ongelmaan.
• Tavoitteena on muotoilla ratkaisu alkuperäiseen ongelmaan yhdistämällä osaongelmien tulokset.

Jaa ja hallitse -algoritmin sovellukset:

• Yhdistä lajittelu: Yhdistä lajittelu on klassinen esimerkki hajota ja hallitse -lajittelualgoritmista. Se jakaa taulukon pienempiin aliryhmiin, lajittelee ne yksitellen ja yhdistää ne sitten lajiteltuun taulukkoon.
• Mediaanilöydös: Lukujoukon mediaani voidaan löytää käyttämällä jakaa ja hallitse -lähestymistapaa. Jakamalla joukko rekursiivisesti pienempiin osajoukkoihin, mediaani voidaan määrittää tehokkaasti.
• Min ja Max löytö: Divide and Conquer -algoritmia voidaan käyttää taulukon minimi- ja maksimielementtien etsimiseen samanaikaisesti. Jakamalla matriisi puoliksi ja vertaamalla kummankin puolikkaan min-max-pareja, kokonaismin ja max voidaan tunnistaa logaritmisen aikamonimutkaisuuden perusteella.
• Matriisin kertolasku: Strassenin matriisin kertolaskualgoritmi on jakaa ja hallitse -tekniikka, joka vähentää suurten matriisien kertolaskujen määrää pilkkomalla matriisit pienemmiksi alimatriiseiksi ja yhdistämällä niiden tulot.
• Lähin pari -ongelma: Lähin pariongelma sisältää kahden lähimmän pisteen löytämisen pistejoukosta moniulotteisessa avaruudessa. Jaa ja hallitse -algoritmi, kuten lähimmän parin jakaminen ja hallitse -algoritmi, voi tehokkaasti ratkaista tämän ongelman jakamalla pisteet rekursiivisesti ja yhdistämällä osaongelmien ratkaisut.

hajota ja hallitse -algoritmin perusteet:

• Johdatus hajota ja hallitse
• Dynaaminen ohjelmointi vs Dive-and-Conquer
• Vähennä ja valloita
• Kehittynyt päälause hajota ja hallitse -toistoille

Vakioalgoritmit käytössä hajota ja hallitse -algoritmi :

• Binäärihaku
• Yhdistä lajittelu
• Nopea lajittelu
• Laske pow(x, n)
• Karatsuba-algoritmi nopeaan kertolaskuun
• Strassenin matriisikertolasku
• Convex Hull (yksinkertainen hajoa ja hallitse -algoritmi)
• Quickhull-algoritmi kuperalle rungolle

Binäärihakuun perustuvat ongelmat:

• Etsi huippuelementti annetusta taulukosta
• Tarkista enemmistöelementti lajitellusta taulukosta
• Kahden lajitellun taulukon K. elementti
• Etsi nollien lukumäärä
• Etsi kiertoluku Kierretty lajiteltu -taulukosta
• Etsi kohta, jossa monotonisesti kasvava funktio tulee positiiviseksi ensimmäisen kerran
• Kahden lajitellun taulukon mediaani
• Kahden erikokoisen lajitellun taulukon mediaani
• Maalarin osioongelma binaarihaulla

Harjoittele ongelmia hajota ja hallitse -algoritmi :

• Kokonaisluvun neliöjuuri
• Matriisin maksimi- ja minimiarvo käyttäen minimimäärää vertailuja
• Etsi kunkin alkion taajuus rajoitetussa taulukossa alle O(n) ajassa
• Laatoitusongelma
• Laske inversiot
• Skyline-ongelma
• Hae rivi- ja sarakekohtaisesti lajitetussa 2D-taulukossa
• Varaa sivujen vähimmäismäärä
• Modulaarinen eksponentio (teho modulaarisessa aritmetiikassa)

Pikalinkit:

• Opi tietorakenne ja algoritmit | DSA opetusohjelma
• 'Harjoitteluongelmat' Divide and Conquer -sivustolla
• 'Tiveliä' aiheesta hajota ja hallitse