La tecnica del Backtracking Vs Forza Bruta

Backtracking vs Bruce Force header

Nel vasto panorama degli algoritmi di risoluzione dei problemi, due approcci principali emergono come metodi distinti ma complementari: il Backtracking e la Forza Bruta. Entrambi sono utilizzati per risolvere problemi computazionali attraverso la ricerca esaustiva delle soluzioni, ma le loro strategie differiscono in modo significativo.

In questo articolo, esamineremo diverse dimensioni dei due approcci, dalla complessità computazionale alla loro applicazione pratica. Attraverso esempi concreti e casi di studio, metteremo in evidenza le situazioni in cui il Backtracking eccelle rispetto alla Forza Bruta e viceversa. Sottolineeremo inoltre l’importanza di una corretta implementazione e considerazioni sulla complessità temporale.

  • Python
    • Algoritmi
      • Alberi
        e Grafi
      • Strutture dati
        Avanzate
      • Numerici
      • Ordinamento
        e Ricerca
      • Ricorsione
        Backtracking

Backtracking e Forza Bruta: due approcci a confronto

Backtracking: La Ricerca Intelligente

Il Backtracking è una strategia che si basa sulla ricerca esaustiva, ma con l’aggiunta di una componente intelligente. Esso esplora le possibilità in modo ricorsivo, facendo scelte e annullando tali scelte quando riconosce che una soluzione parziale non può portare a una soluzione completa. Questa tecnica è particolarmente adatta per problemi di decisione complessi, dove è possibile eliminare molte soluzioni non promettenti.

Forza Bruta: L’Approccio Diretto

Dall’altro lato dello spettro, la Forza Bruta è un approccio diretto ed esaustivo che esamina tutte le possibili soluzioni una dopo l’altra, senza strategie di pruning o eliminazione delle soluzioni non ottimali. Sebbene possa essere meno efficiente su problemi complessi, la Forza Bruta è spesso utilizzata quando la dimensione del problema è limitata o quando non è possibile applicare strategie di ottimizzazione.

Cos’è il Backtracking?

Il backtracking è una tecnica di risoluzione dei problemi che si basa sulla ricerca esaustiva di tutte le soluzioni possibili per un determinato problema. In sostanza, il backtracking esplora tutte le possibilità di una soluzione e, quando si rende conto che la soluzione parziale che sta esaminando non può portare a una soluzione completa, fa “backtrack” alla decisione precedente e riprende l’esplorazione da lì.

La tecnica del backtracking segue una struttura ricorsiva, e il suo pseudocodice può essere rappresentato in modo generale come segue:

def backtrack(soluzione_parciale, altri_parametri):
    if soluzione_parciale è completa:
        # Aggiungi soluzione_parciale alla lista delle soluzioni
    else:
        for scelta in scelte_possibili:
            if scelta è valida:
                # Fai una scelta
                aggiorna soluzione_parciale
                # Chiamata ricorsiva
                backtrack(soluzione_parciale, altri_parametri)
                # Annulla la scelta (backtrack)
                ripristina soluzione_parciale

Il Problema delle N Regine

Questo approccio è particolarmente utile per risolvere problemi di decisione, come ad esempio il problema delle N regine, il problema del commesso viaggiatore e molti altri.

Implementiamo un esempio semplice di backtracking per risolvere il problema delle N regine. In questo problema, l’obiettivo è posizionare N regine su una scacchiera N x N in modo che nessuna regina minacci un’altra.

def is_safe(board, row, col, n):
    # Verifica se è sicuro posizionare una regina in questa posizione
    for i in range(row):
        if board[i][col] == 1:
            return False
        if col - i >= 0 and board[row - i][col - i] == 1:
            return False
        if col + i < n and board[row - i][col + i] == 1:
            return False
    return True

def solve_n_queens_util(board, row, n, solutions):
    if row == n:
        # Abbiamo trovato una soluzione completa
        solutions.append([row[:] for row in board])
        return
    for col in range(n):
        if is_safe(board, row, col, n):
            # Fai una scelta
            board[row][col] = 1
            # Chiamata ricorsiva
            solve_n_queens_util(board, row + 1, n, solutions)
            # Annulla la scelta (backtrack)
            board[row][col] = 0

def solve_n_queens(n):
    board = [[0] * n for _ in range(n)]
    solutions = []
    solve_n_queens_util(board, 0, n, solutions)
    return solutions

# Esempio di utilizzo
n = 4
solutions = solve_n_queens(n)
for solution in solutions:
    print(solution)

In questo esempio, solve_n_queens restituirà una lista di tutte le possibili disposizioni delle N regine sulla scacchiera. La funzione is_safe verifica se è sicuro posizionare una regina in una determinata posizione. La funzione solve_n_queens_util è una funzione di supporto ricorsiva che esplora tutte le possibili soluzioni. Eseguendo si ottiene il seguente risultato:

[[0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 1]]
[[0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0]]
[[0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0]]
[[0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0]]

Questa è solo un’esempio di come il backtracking può essere utilizzato per risolvere un problema specifico. La chiave è adattare la struttura generale del backtracking al problema specifico che si sta affrontando.

Backtracking vs Forza Bruta

Il backtracking e la forza bruta sono due approcci risolvere problemi computazionali in maniera esaustiva, ma hanno differenze significative nel modo in cui affrontano la ricerca delle soluzioni.

Forza Bruta (Brute Force)

La forza bruta è un approccio diretto ed esaustivo per risolvere un problema, in cui tutte le possibili soluzioni vengono esaminate una dopo l’altra fino a trovare quella corretta. Questo approccio può essere inefficiente su problemi complessi, in quanto esamina tutte le combinazioni possibili, senza alcuna strategia di pruning o eliminazione delle soluzioni che non possono portare a una soluzione ottimale.

Ad esempio, considera un problema in cui devi trovare la somma massima di una sotto-sequenza in un array. La forza bruta esaminerebbe tutte le possibili sotto-sequenze e confronterebbe le somme, senza considerare alcuna proprietà strutturale del problema.

def max_subarray_sum_bruteforce(arr):
    n = len(arr)
    max_sum = float('-inf')
    for i in range(n):
        for j in range(i, n):
            current_sum = sum(arr[i:j+1])
            max_sum = max(max_sum, current_sum)
    return max_sum

Questo approccio può essere inefficiente per problemi con grandi spazi di ricerca.

Backtracking

Il backtracking è un approccio basato sulla ricerca esaustiva delle soluzioni, ma con l’aggiunta di una strategia di pruning. Esso esplora le soluzioni in modo ricorsivo, effettuando delle scelte e verificando se conducono a una soluzione accettabile. Se si scopre che una particolare scelta non può portare a una soluzione valida, il backtracking fa “backtrack” e annulla la scelta, esplorando altre possibilità.

Nel paragrafo precedente, abbiamo visto un esempio di backtracking risolvendo il problema delle N regine. Questo approccio si concentra sulla generazione incrementale delle soluzioni, facendo scelte e annullando le scelte quando necessario.

Il backtracking è spesso più efficiente della forza bruta per problemi in cui esistono molte scelte possibili e alcune di esse possono essere eliminate in modo intelligente. Tuttavia, la complessità temporale può ancora essere elevata in determinati casi.

In conclusione, mentre la forza bruta esamina tutte le possibilità senza strategie di pruning, il backtracking aggiunge un livello di intelligenza alla ricerca esplorando solo le possibilità rilevanti, riducendo così il tempo computazionale. Entrambi gli approcci hanno i loro usi a seconda del problema specifico che si sta affrontando.

Il Problema del Commesso Viaggiatore

Per meglio vedere la differenza che c’è tra l’approccio Forza Bruta e la tecnica del Backtracking, applicheremo un esempio pratico: il problema del commesso viaggiatore (TSP – Travelling Salesman Problem), che coinvolge la ricerca del percorso più breve che attraversa tutti i punti dati esattamente una volta.

In questo esempio, implementeremo una soluzione di forza bruta e una soluzione di backtracking per risolvere il TSP. Successivamente, useremo la libreria matplotlib per visualizzare le differenze di efficienza tra i due approcci. Per prima cosa generiamo una serie di città disposte in maniera casuale in uno spazio di coordinate (X.Y).

import random
import matplotlib.pyplot as plt

def distance(city1, city2):
    return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5

def plot_cities(cities):
    x, y = zip(*cities)
    plt.scatter(x, y, c='red', marker='o')
    for i, (xi, yi) in enumerate(cities):
        plt.text(xi, yi, str(i), fontsize=9, ha='right', va='bottom')
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.title('Positioning of cities')
    plt.show()

# Generazione di città casuali per il test
def generate_random_cities(num_cities):
    random.seed(42)
    cities = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(num_cities)]
    return cities

# Visualizzazione delle città
num_cities = 10
cities = generate_random_cities(num_cities)
plot_cities(cities)

Eseguendo otterremo la rappresentazione grafica delle città disposte su un piano cartesiano

Backtracking technique 01

Adesso risolviamo il problema del commesso viaggiatore utilizzando sia la forza bruta che il backtracking, e infine, mostreremo un grafico comparativo del tempo impiegato dai due approcci. I tempi possono variare a seconda della configurazione casuale delle città e della potenza computazionale del sistema in uso.

Il calcolo ci dovrà fornire come risultato il percorso più breve che il commesso viaggiatore dovrà fare per visitare tutte le città mostrate nel grafico sopra. Per tale calcolo applicheremo i due diversi approcci fornendo due diverse funzioni.

Forza Bruta (tsp_bruteforce)

def tsp_bruteforce(cities):
    start_time = time.time()
    shortest_path = None
    shortest_distance = float('inf')

    for perm in itertools.permutations(range(len(cities))):
        current_distance = total_distance(perm, cities)
        if current_distance < shortest_distance:
            shortest_distance = current_distance
            shortest_path = perm

    elapsed_time = time.time() - start_time
    return shortest_path, shortest_distance, elapsed_time
  1. Inizializzazione: La funzione tsp_bruteforce inizia misurando il tempo iniziale (start_time) e inizializza le variabili shortest_path e shortest_distance per tenere traccia della soluzione più breve e della sua distanza.
  2. Permutazioni: Utilizzando itertools.permutations, vengono generate tutte le possibili permutazioni degli indici delle città. Ogni permutazione rappresenta un possibile percorso da esaminare.
  3. Calcolo della Distanza: Per ogni permutazione, viene calcolata la distanza totale del percorso utilizzando la funzione total_distance.
  4. Aggiornamento della Soluzione Migliore: Se la distanza calcolata è inferiore alla distanza corrente della soluzione migliore (shortest_distance), la soluzione migliore viene aggiornata.
  5. Misurazione del Tempo: Alla fine del processo, viene calcolato il tempo totale impiegato.

Backtracking (tsp_backtracking)

def tsp_backtracking(cities):
    start_time = time.time()

    def backtrack(path):
        if len(path) == len(cities):
            nonlocal shortest_path, shortest_distance
            current_distance = total_distance(path, cities)
            if current_distance < shortest_distance:
                shortest_distance = current_distance
                shortest_path = path
        else:
            for i in range(len(cities)):
                if i not in path:
                    backtrack(path + [i])

    shortest_path = None
    shortest_distance = float('inf')
    backtrack([])

    elapsed_time = time.time() - start_time
    return shortest_path, shortest_distance, elapsed_time
  1. Inizializzazione: La funzione tsp_backtracking inizia misurando il tempo iniziale (start_time) e inizializza le variabili shortest_path e shortest_distance.
  2. Funzione di Backtrack Ricorsiva: La funzione backtrack è una funzione ricorsiva che esplora tutte le possibili permutazioni dei percorsi. Se la lunghezza del percorso corrente è uguale al numero di città, viene calcolata la distanza totale e aggiornata la soluzione migliore se necessario. Altrimenti, per ogni città non ancora inclusa nel percorso, la funzione si richiama ricorsivamente aggiungendo la città al percorso.
  3. Inizializzazione del Backtrack: La funzione principale tsp_backtracking inizia il processo di backtracking chiamando backtrack([]), indicando che il percorso iniziale è vuoto.
  4. Misurazione del Tempo: Alla fine del processo, viene calcolato il tempo totale impiegato.

Backtracking vs Brute Force

Adesso scriviamo il codice interamente che effettuerà il calcolo del percorso più breve con entrambe gli approcci e poi paragoneremo i risultati ottenuti ed il tempo impiegato.

import itertools
import time
import matplotlib.pyplot as plt

def total_distance(path, cities):
    total_dist = 0
    for i in range(len(path) - 1):
        total_dist += distance(cities[path[i]], cities[path[i + 1]])
    return total_dist

# Soluzione di Forza Bruta per il TSP
def tsp_bruteforce(cities):
    start_time = time.time()
    shortest_path = None
    shortest_distance = float('inf')

    for perm in itertools.permutations(range(len(cities))):
        current_distance = total_distance(perm, cities)
        if current_distance < shortest_distance:
            shortest_distance = current_distance
            shortest_path = perm

    elapsed_time = time.time() - start_time
    return shortest_path, shortest_distance, elapsed_time

# Soluzione di Backtracking per il TSP
def tsp_backtracking(cities):
    start_time = time.time()

    def backtrack(path):
        if len(path) == len(cities):
            nonlocal shortest_path, shortest_distance
            current_distance = total_distance(path, cities)
            if current_distance < shortest_distance:
                shortest_distance = current_distance
                shortest_path = path
        else:
            for i in range(len(cities)):
                if i not in path:
                    backtrack(path + [i])

    shortest_path = None
    shortest_distance = float('inf')
    backtrack([])

    elapsed_time = time.time() - start_time
    return shortest_path, shortest_distance, elapsed_time

# Esecuzione delle soluzioni
bruteforce_result = tsp_bruteforce(cities)
backtracking_result = tsp_backtracking(cities)

# Stampa dei risultati
print("Brute force:")
print("Shortest route:", bruteforce_result[0])
print("Minimum distance:", bruteforce_result[1])
print("Execution time (seconds):", bruteforce_result[2])

print("\nBacktracking:")
print("Shortest route:", backtracking_result[0])
print("Minimum distance:", backtracking_result[1])
print("Execution time (seconds):", backtracking_result[2])

# Creazione del grafico di confronto
labels = ['Brute force', 'Backtracking']
times = [bruteforce_result[2], backtracking_result[2]]
plt.bar(labels, times, color=['blue', 'green'])
plt.ylabel('Execution time (seconds)')
plt.title('Comparison between Brute Force and Backtracking for TSP')
plt.show()

L’esecuzione richiederà diversi secondi (quasi un minuto). Al termine del calcolo verranno visualizzati i seguenti risultati:

Brute force:
Shortest route: (2, 7, 8, 5, 6, 1, 4, 0, 9, 3)
Minimum distance: 203.1584418265072
Execution time (seconds): 23.648714065551758

Backtracking:
Shortest route: [2, 7, 8, 5, 6, 1, 4, 0, 9, 3]
Minimum distance: 203.1584418265072
Execution time (seconds): 27.852330446243286
Backtracking technique 02

Interessante il risultato. In questo caso, l’approccio Brute Force risulterebbe più efficiente del Backtracking, impiegando per il calcolo alcuni secondi in meno.

Lascia un commento