Skaldyk ir valdyk yra algoritminis modelis. Taikant algoritminius metodus, siekiama ginčytis dėl didžiulės įvesties, suskaidyti įvestį į nedideles dalis, išspręsti kiekvienos mažos dalies problemą ir tada sujungti atskirus sprendimus į visuotinį sprendimą. Šis problemos sprendimo mechanizmas vadinamas „Skaldyk ir valdyk“ strategija.

„Skaldyk ir valdyk“ algoritmą sudaro ginčas, naudojant šiuos tris veiksmus.

Padalintipradinę problemą į subproblemų rinkinį.Užkariauti:Išspręskite kiekvieną subproblemą atskirai, rekursyviai.Sujungti:Sujunkite subproblemų sprendimus, kad gautumėte visos problemos sprendimą.

Paprastai galime sekti skaldyk ir valdyk trijų etapų procese.

Pavyzdžiai: Konkretūs kompiuteriniai algoritmai yra pagrįsti „Skaldyk ir užkariauk“ metodu:

1. Didžiausia ir mažiausia problema
2. Dvejetainė paieška
3. Rūšiavimas (sujungti rūšiavimą, greitas rūšiavimas)
4. Hanojaus bokštas.

„Skaldyk ir valdyk“ strategijos pagrindai:

Yra du „Skaldyk ir užkariauk“ strategijos pagrindai:

1. Santykių formulė
2. Sustojimo sąlyga

1. Santykių formulė: Tai formulė, kurią sukuriame pagal pateiktą techniką. Sukūrę formulę taikome D&C strategiją, t.y. rekursyviai išsprendžiame problemą ir išsprendžiame sugedusias subproblemas.

2. Sustojimo sąlyga: Kai išsprendžiame problemą naudodami strategiją Divide & Conquer, turime žinoti, kad kiek laiko turime taikyti „skaldyk ir užkariauk“. Taigi sąlyga, kai reikia sustabdyti mūsų D&C rekursinius veiksmus, vadinama stabdymo sąlyga.

„Skaldyk ir valdyk“ metodo taikymas:

Šie algoritmai yra pagrįsti „Skaldyk ir valdyk“ technikos koncepcija:

Dvejetainė paieška:Dvejetainis paieškos algoritmas yra paieškos algoritmas, kuris dar vadinamas pusės intervalo paieška arba logaritmine paieška. Jis veikia lygindamas tikslinę vertę su viduriniu elementu, esančiu surūšiuotame masyve. Atlikus palyginimą, jei reikšmė skiriasi, pusė, kurioje negali būti taikinio, galiausiai bus pašalinta, o tada bus tęsiama paieška kitoje pusėje. Dar kartą apsvarstysime vidurinį elementą ir palyginsime jį su tiksline verte. Procesas kartojamas tol, kol pasiekiama tikslinė vertė. Jei baigę paiešką radome tuščią kitą pusę, tai galima daryti išvadą, kad taikinio masyve nėra.Greitas rūšiavimas:Tai efektyviausias rūšiavimo algoritmas, kuris taip pat žinomas kaip skaidinio mainų rūšiavimas. Pradedama pasirinkus sukimosi reikšmę iš masyvo, po to likusius masyvo elementus padalijant į du antrinius masyvus. Skirstymas atliekamas lyginant kiekvieną elementą su sukimosi reikšme. Jis palygina, ar elementas turi didesnę ar mažesnę reikšmę nei sukinys, ir tada rekursyviai rūšiuoja masyvus.Sujungti rūšiavimą:Tai rūšiavimo algoritmas, kuris rūšiuoja masyvą palygindamas. Jis pradedamas padalijus masyvą į pomasyvį, o vėliau rekursyviai surūšiuoja kiekvieną iš jų. Atlikus rūšiavimą, jie sujungiami atgal.Artimiausia taškų pora:Tai yra skaičiavimo geometrijos problema. Šis algoritmas pabrėžia artimiausios taškų poros metrinėje erdvėje, duotų n taškų, nustatymą, kad atstumas tarp taškų poros būtų minimalus.Strasseno algoritmas:Tai matricos daugybos algoritmas, pavadintas Volkerio Strasseno vardu. Jis pasirodė esąs daug greitesnis nei tradicinis algoritmas, kai dirbama su didelėmis matricomis.Cooley-Tukey greitojo Furjė transformacijos (FFT) algoritmas:Greitasis Furjė transformacijos algoritmas pavadintas J. W. Cooley ir Johno Turkey vardu. Jis vadovaujasi „skaldyk ir valdyk“ metodu ir nustato O(nlogn) sudėtingumą.Karatsuba algoritmas greitam dauginimui:Tai vienas greičiausių tradicinių laikų daugybos algoritmų, išrastas Anatolijus Karatsuba 1960 m. pabaigoje ir paskelbtas 1962 m. Jis padaugina du n skaitmenų skaičius tokiu būdu sumažindamas jį iki daugiausiai vienženklių.

„Skaldyk ir valdyk“ pranašumai

• „Skaldyk ir valdyk“ linkęs sėkmingai išspręsti vieną didžiausių problemų, pavyzdžiui, Hanojaus bokštą – matematinį galvosūkį. Sunku išspręsti sudėtingas problemas, apie kurias neturite pagrindinės idėjos, tačiau pasitelkus „skaldyk ir valdyk“ metodą, tai sumažino pastangas, nes pagrindinė problema yra padalinta į dvi dalis, o vėliau jas sprendžiama rekursyviai. Šis algoritmas yra daug greitesnis nei kiti algoritmai.
• Jis efektyviai naudoja talpyklą, neužimdamas daug vietos, nes išsprendžia paprastas poproblemas talpykloje, o ne pasiekia lėtesnę pagrindinę atmintį.
• Jis yra labiau įgudęs nei jo kolega Brute Force technika.
• Kadangi šie algoritmai slopina lygiagretumą, jis nereikalauja jokių pakeitimų ir yra tvarkomas sistemose, turinčiose lygiagretų apdorojimą.

Skaldyk ir valdyk trūkumai

• Kadangi dauguma jo algoritmų yra sukurti įtraukiant rekursiją, tai reikalauja didelio atminties valdymo.
• Aiškus krūvas gali per daug išnaudoti vietos.
• Ji netgi gali sugadinti sistemą, jei rekursija atliekama griežtai didesne nei procesoriaus krūva.