TechCodeview

Divide and Conquer és un patró algorítmic. En els mètodes algorísmics, el disseny consisteix a plantejar una disputa sobre una entrada enorme, dividir l'entrada en peces menors, decidir el problema de cadascuna de les peces petites i, a continuació, combinar les solucions a trossos en una solució global. Aquest mecanisme per resoldre el problema s'anomena estratègia Divide & Conquer.

L'algoritme Divide and Conquer consisteix en una disputa mitjançant els tres passos següents.

Divideixel problema original en un conjunt de subproblemes.Conquerir:Resoldre cada subproblema individualment, recursivament.Combina:Ajunta les solucions dels subproblemes per obtenir la solució a tot el problema.

En general, podem seguir el divideix i conquereix enfocament en un procés de tres passos.

Exemples: Els algorismes informàtics específics es basen en l'enfocament Divide & Conquer:

1. Problema màxim i mínim
2. Cerca binària
3. Ordenació (ordenació combinada, ordenació ràpida)
4. Torre de Hanoi.

Fonaments de l'estratègia Divide & Conquer:

Hi ha dos fonamentals de l'estratègia Divide & Conquer:

1. Fórmula relacional
2. Condició d'aturada

1. Fórmula relacional: És la fórmula que generem a partir de la tècnica donada. Després de la generació de la fórmula, apliquem l'estratègia D&C, és a dir, trenquem el problema de forma recursiva i resolem els subproblemes trencats.

2. Condició d'aturada: Quan trenquem el problema amb l'estratègia Divide & Conquer, hem de saber que durant quant de temps hem d'aplicar divide & Conquer. Per tant, la condició on la necessitat d'aturar els nostres passos de recursivitat de D&C s'anomena Condició d'aturada.

Aplicacions de l'enfocament Divide and Conquer:

Els algorismes següents es basen en el concepte de la tècnica Divide and Conquer:

Cerca binària:L'algorisme de cerca binari és un algorisme de cerca, que també s'anomena cerca a mig interval o cerca logarítmica. Funciona comparant el valor objectiu amb l'element central existent en una matriu ordenada. Després de fer la comparació, si el valor és diferent, la meitat que no pot contenir l'objectiu s'eliminarà, i continuarà la cerca a l'altra meitat. Tornarem a considerar l'element mitjà i el compararem amb el valor objectiu. El procés es continua repetint fins que s'aconsegueix el valor objectiu. Si hem trobat que l'altra meitat està buida després d'acabar la cerca, es pot concloure que l'objectiu no està present a la matriu.Classificació ràpida:És l'algorisme d'ordenació més eficient, que també es coneix com a ordenació per intercanvi de particions. Comença seleccionant un valor de pivot d'una matriu seguit de dividint la resta d'elements de la matriu en dos submatrius. La partició es fa comparant cadascun dels elements amb el valor de pivot. Compara si l'element té un valor més gran o menor que el pivot i després ordena les matrius de manera recursiva.Ordenar per combinació:És un algorisme d'ordenació que ordena una matriu fent comparacions. Comença dividint una matriu en submatrius i després ordena recursivament cadascun d'ells. Un cop feta l'ordenació, les torna a fusionar.Parell de punts més proper:És un problema de geometria computacional. Aquest algorisme fa èmfasi en trobar el parell de punts més proper en un espai mètric, donats n punts, de manera que la distància entre el parell de punts ha de ser mínima.Algorisme de Strassen:És un algorisme per a la multiplicació de matrius, que rep el nom de Volker Strassen. S'ha demostrat que és molt més ràpid que l'algorisme tradicional quan funciona amb matrius grans.Algorisme de la transformada ràpida de Fourier (FFT) de Cooley-Tukey:L'algorisme de la transformada ràpida de Fourier rep el nom de J. W. Cooley i John Turkey. Segueix l'enfocament Divide and Conquer i imposa una complexitat de O(nlogn).Algorisme de Karatsuba per a la multiplicació ràpida:És un dels algorismes de multiplicació més ràpids de l'època tradicional, inventat per Anatoly Karatsuba a finals de 1960 i publicat el 1962. Multiplica dos nombres d'n xifres d'aquesta manera reduint-los com a màxim a un sol dígit.

Avantatges de Divide and Conquer

• Divide and Conquer tendeix a resoldre amb èxit un dels problemes més grans, com ara la Torre de Hanoi, un trencaclosques matemàtic. És un repte resoldre problemes complicats dels quals no tens una idea bàsica, però amb l'ajuda de l'enfocament divideix i vencem, ha reduït l'esforç, ja que treballa dividint el problema principal en dues meitats i després resoldre'ls de manera recursiva. Aquest algorisme és molt més ràpid que altres algorismes.
• Utilitza de manera eficient la memòria cau sense ocupar molt d'espai perquè resol subproblemes senzills dins de la memòria cau en lloc d'accedir a la memòria principal més lenta.
• És més competent que la de la seva contrapartida tècnica de força bruta.
• Com que aquests algorismes inhibeixen el paral·lelisme, no implica cap modificació i és gestionat per sistemes que incorporen processament paral·lel.

Inconvenients de Divide and Conquer

• Atès que la majoria dels seus algorismes estan dissenyats incorporant recursivitat, de manera que requereix una gestió de memòria elevada.
• Una pila explícita pot fer un ús excessiu de l'espai.
• Fins i tot pot bloquejar el sistema si la recursivitat es realitza de manera rigorosament superior a la pila present a la CPU.