Python - Dividi e conquista

Nell'approccio divide et impera, il problema alla mano viene suddiviso in sotto-problemi più piccoli e quindi ogni problema viene risolto in modo indipendente. Quando continuiamo a dividere i sottoproblemi in sotto-problemi ancora più piccoli, potremmo eventualmente raggiungere uno stadio in cui non è più possibile alcuna divisione. Quei sottoproblemi "atomici" più piccoli possibili (frazioni) sono risolti. La soluzione di tutti i sottoproblemi viene infine unita per ottenere la soluzione di un problema originale.

In generale, possiamo capire divide-and-conquer approccio in un processo in tre fasi.

Dividi / Spezza

Questo passaggio comporta la suddivisione del problema in sottoproblemi più piccoli. I sottoproblemi dovrebbero rappresentare una parte del problema originale. Questo passaggio generalmente richiede un approccio ricorsivo per dividere il problema fino a quando nessun sottoproblema è ulteriormente divisibile. In questa fase, i problemi secondari diventano di natura atomica ma rappresentano ancora una parte del problema reale.

Conquista / Risolvi

Questo passaggio riceve molti sottoproblemi minori da risolvere. Generalmente, a questo livello, i problemi sono considerati "risolti" da soli.

Unisci / Combina

Quando i sottoproblemi più piccoli vengono risolti, questa fase li combina ricorsivamente fino a formulare una soluzione del problema originale. Questo approccio algoritmico funziona in modo ricorsivo e i passaggi di conquista e unione funzionano così vicini da apparire come uno solo.

Esempi

Il seguente programma è un esempio di divide-and-conquer approccio di programmazione in cui la ricerca binaria è implementata utilizzando python.

Implementazione della ricerca binaria

Nella ricerca binaria prendiamo un elenco ordinato di elementi e iniziamo a cercare un elemento al centro dell'elenco. Se il valore di ricerca corrisponde al valore centrale nell'elenco, completiamo la ricerca. Altrimenti si elimina metà della lista degli elementi scegliendo se procedere con la metà destra o sinistra della lista a seconda del valore dell'elemento cercato. Ciò è possibile poiché l'elenco è ordinato ed è molto più veloce della ricerca lineare. Qui dividiamo la lista data e conquistiamo scegliendo la metà corretta della lista. Ripetiamo questo approccio finché non troviamo l'elemento o concludiamo sulla sua assenza nell'elenco.

def bsearch(list, val):

    list_size = len(list) - 1

    idx0 = 0
    idxn = list_size
# Find the middle most value

    while idx0 <= idxn:
        midval = (idx0 + idxn)// 2

        if list[midval] == val:
            return midval
# Compare the value the middle most value
        if val > list[midval]:
            idx0 = midval + 1
        else:
            idxn = midval - 1

    if idx0 > idxn:
        return None
# Initialize the sorted list
list = [2,7,19,34,53,72]

# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))

Quando il codice precedente viene eseguito, produce il seguente risultato:

5
None