Tutto sugli algoritmi avidi| Guida per principianti.

Tutto quello che c'è da sapere sugli algoritmi avidi | Guida per principianti.

Immagina di essere in viaggio verso una nuova destinazione, probabilmente utilizzi la navigazione GPS per trovare il percorso più veloce. Proprio come cercare un percorso efficiente in una strada sconosciuta, gli algoritmi avidi selezionano sempre il passo successivo che offre il beneficio più ovvio e immediato. Gli algoritmi avidi tendono a scegliere la migliore opzione ad ogni passo, il che ci permette gradualmente di ottenere una soluzione in modo efficiente in termini di tempo.

Ora affrontiamo un esempio per imparare di più sugli Algoritmi Avidi – il problema del cambio monetario.

Supponiamo che abbiamo bisogno di dare 31 monete come cambio, e abbiamo le seguenti denominazioni: 20, 10, 5, 2, 1.

Il problema del Cambio Monetario utilizza un approccio algoritmico avido –

  • Innanzitutto, trovare la denominazione più grande che è inferiore all’importo totale.
  • Aggiungere la denominazione al risultato e sottrarla dall’importo totale.
  • Se l’importo totale è ora zero, allora stampare le denominazioni.
  • Altrimenti, ripetere i passaggi 1 e 2.

Definizione degli Algoritmi Avidi:

Gli Algoritmi Avidi sono un insieme di algoritmi di ottimizzazione utilizzati nella Risoluzione di problemi algoritmici. L’idea fondamentale dietro l’approccio avido è fare una scelta localmente ottimale in ogni fase con la speranza di trovare il massimo globale. A differenza della programmazione dinamica, in cui risolviamo i sottoproblemi e archiviamo le soluzioni per evitare calcoli ridondanti, gli Algoritmi Avidi prendono decisioni selezionando la migliore opzione disponibile in un determinato momento senza considerare i passaggi successivi.

Quando dovrebbe uno scegliere gli Algoritmi Avidi?

Gli Algoritmi Avidi sono adatti per i problemi che presentano le seguenti caratteristiche:

  1. Scelta Avida: gli Algoritmi Avidi prendono sempre la migliore decisione ad ogni passo per ottenere una soluzione globale ottimale. In questo processo, non considerano di tornare a riesaminare le decisioni prese in precedenza. Se non dobbiamo riesaminare o modificare le decisioni già prese, allora possiamo scegliere un approccio algoritmico avido.
  2. Sottostruttura Ottimale: Se possiamo avvicinarci alla soluzione complessiva suddividendo il nostro problema in un insieme di sottoproblemi in cui la migliore decisione conta, possiamo utilizzare un algoritmo avido.
  3. Efficienza Temporale: gli algoritmi avidi sono semplici ed efficienti in termini di tempo. Si avvicinano più rapidamente all’ottimo globale e potrebbero non considerare le decisioni prese in passato.

Ora lavoriamo su tre problemi che utilizzano un approccio algoritmico avido.

Problema di selezione delle attività – Intervalli non sovrapposti

Dato un array di intervalli intervalli in cui intervalli[i] = [starti, endi], restituisci il numero minimo di intervalli che devi rimuovere affinché gli intervalli rimanenti non si sovrappongano.

Esempio 1:

Input: intervalli = [[1,2],[2,3],[3,4],[1,3]]Output: 1Spiegazione: [1,3] può essere rimosso e gli altri intervalli non si sovrappongono.

Esempio 2:

Input: intervalli = [[1,2],[1,2],[1,2]]Output: 2Spiegazione: Devi rimuovere due intervalli [1,2] affinché gli altri intervalli non si sovrappongano.

Esempio 3:

Input: intervalli = [[1,2],[2,3]]Output: 0Spiegazione: Non è necessario rimuovere nessuno degli intervalli poiché non si sovrappongono.

Codice:

class Solution:    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:        intervals.sort(key=lambda x: x[1])        last_end = intervals[0][1]        count = 0        for s, e in intervals[1:]:          if last_end>s:            count += 1          else:            last_end = e        return(count)

Il codice sopra segue un approccio algoritmo avido. Stiamo ordinando la lista di input per assicurarci di poter seguire le caratteristiche di sottostruttura ottimale, dividendo il problema in problemi più piccoli. Quindi, ci assicuriamo che ogni lista nella lista nidificata non si sovrapponga alla precedente e, in base a questo, incrementiamo la nostra risposta.

Codifica di Huffman

La codifica di Huffman è un algoritmo per la compressione dei dati senza perdita di informazioni. L’obiettivo della codifica di Huffman è rappresentare i dati assegnando codici binari più brevi ai caratteri che si verificano più frequentemente e codici binari più lunghi ai caratteri meno frequenti.

Approccio:

  • Calcolare la frequenza di ciascun carattere nei dati passati.
  • L’albero viene costruito in modo tale che i simboli più frequenti abbiano codici binari più corti e i simboli meno frequenti abbiano codici binari più lunghi.
  • Vengono assegnati codici binari a ciascun carattere. Il percorso dalla radice dell’albero a un determinato carattere definisce in modo univoco il suo codice binario.
  • Questi codici binari assegnati a ciascun simbolo formano i codici di Huffman. I dati originali sono stati sostituiti con il Codice di Huffman.
  • Lo stesso albero di Huffman viene utilizzato per decomprimere i dati. Iniziando dalla radice, i codici binari vengono attraversati e i simboli originali vengono ricostruiti.

Esempio – Costruzione dell’albero:

Consideriamo il testo – ABRACADABRA, Qui A si verifica 5 volte, B e R si verificano due volte e C e D si verificano una volta. L’albero di Huffman viene costruito in base a queste frequenze e l’albero potrebbe apparire così –

In questo esempio, ‘A’ potrebbe essere codificato come ‘0’, ‘B’ come ‘110’, ‘R’ come ‘111’, ‘C’ come ’10’ e ‘D’ come ‘1110’. La codifica di Huffman è ampiamente utilizzata in varie applicazioni, tra cui la compressione dei file (file ZIP), la compressione delle immagini (JPEG) e i protocolli di rete. La sua efficienza deriva dal fatto che i simboli più frequenti hanno codici più corti, il che comporta una compressione complessiva dei dati.

Codice:

import heapqfrom collections import defaultdictclass Node:    def __init__(self, symbol=None, frequency=None):        self.symbol = symbol        self.frequency = frequency        self.left = None        self.right = None    def __lt__(self, other):        return self.frequency < other.frequencydef build_huffman_tree(frequencies):    heap = [Node(symbol=s, frequency=f) for s, f in frequencies.items()]    heapq.heapify(heap)    while len(heap) > 1:        left = heapq.heappop(heap)        right = heapq.heappop(heap)        merged = Node(frequency=left.frequency + right.frequency)        merged.left = left        merged.right = right        heapq.heappush(heap, merged)    return heap[0]def generate_huffman_codes(node, code="", mapping=None):    if mapping is None:        mapping = {}    if node.symbol:        mapping[node.symbol] = code    if node.left:        generate_huffman_codes(node.left, code + "0", mapping)    if node.right:        generate_huffman_codes(node.right, code + "1", mapping)    return mappingdef huffman_encode(text):    frequencies = defaultdict(int)    for symbol in text:        frequencies[symbol] += 1    root = build_huffman_tree(frequencies)    codes = generate_huffman_codes(root)    encoded_text = "".join(codes[symbol] for symbol in text)    return encoded_text, roottext_to_encode = "ABRACADABRA"encoded_text, huffman_tree_root = huffman_encode(text_to_encode)print("Testo originale:", text_to_encode)print("Testo codificato:", encoded_text)

Per sapere di più sulle collezioni utilizzate nel codice sopra, consulta il mio articolo precedente –

Tutto sul modulo Collezioni in Python

Come tutti sappiamo, Python ha i suoi tipi di dati regolari – List, Tuple, Dictionary e famosi Sets. Ma insieme a…

pub.towardsai.net

Algoritmo di Dijkstra

L’algoritmo di Dijkstra viene utilizzato nella teoria dei grafi per trovare il percorso più corto tra i nodi del grafo, principalmente per i grafi con pesi di bordo positivi.

Metodo:

  • Inizializza una coda prioritaria per tenere traccia delle distanze dal nodo sorgente ai nodi. Imposta la distanza dal nodo sorgente a 0 e “inf” per tutti gli altri nodi.
  • Dal nodo con la minore distanza, aggiorna le distanze verso gli altri vicini calcolando la somma della distanza corrente dai nodi selezionati agli altri nodi.
  • Dopo aver esplorato le distanze, segnala il nodo come visitato per evitare di esplorarlo nuovamente. Ripeti il processo finché tutti i nodi non sono stati visitati.

Esempio:

Nodi: A, B, C, D Archi: (A, B, 4), (A, C, 5), (A, D, 2), (B, C, 1), (B, D, 3), (C, D, 5)

Troviamo i percorsi più brevi da A a tutti gli altri nodi utilizzando l’algoritmo di Dijkstra:

  • Inizia dal nodo A. Imposta la distanza di A a 0 e “inf” per tutti gli altri nodi: (A, 0), (B, ∞), (C, ∞), (D, ∞).
  • Inizializza la coda prioritaria con queste distanze.
  • Seleziona A con distanza 0. Esplora i suoi vicini: B (peso 4), C (peso 5), D (peso 2).
  • Aggiorna le distanze: (A, 0), (B, 4), (C, 5), (D, 2).
  • Segna A come visitato. Ripeti finché tutti i nodi non sono stati esplorati.
  • Seleziona D con distanza 2. Esplora i suoi vicini: B (peso 3) e C (peso 5).
  • Aggiorna le distanze: (A, 0), (B, 4), (C, 5), (D, 2) (nessuna modifica per D). Segna D come visitato.
  • Ripeti il processo per tutti gli altri nodi.
  • I percorsi più brevi da A agli altri nodi sono:
  • A a B: [A, D, B] (Distanza totale: 4 + 3 = 7)
  • A a C: [A, D, C] (Distanza totale: 2 + 5 = 7)
  • A a D: [A, D] (Distanza totale: 2)

Codice:

import heapqfrom collections import defaultdictdef dijkstra(graph, start):    distances = {node: float('inf') for node in graph}    distances[start] = 0    priority_queue = [(0, start)]    while priority_queue:        current_distance, current_node = heapq.heappop(priority_queue)        if current_distance > distances[current_node]:            continue        for neighbor, weight in graph[current_node].items():            distance = current_distance + weight            if distance < distances[neighbor]:                distances[neighbor] = distance                heapq.heappush(priority_queue, (distance, neighbor))    return distancesgraph = {    'A': {'B': 4, 'C': 5, 'D': 2},    'B': {'A': 4, 'C': 1, 'D': 3},    'C': {'A': 5, 'B': 1, 'D': 5},    'D': {'A': 2, 'B': 3, 'C': 5}}start_node = 'A'shortest_distances = dijkstra(graph, start_node)print(f"Distanze più brevi da {start_node}:")for node, distance in shortest_distances.items():    print(f"A {node}: {distance}")

Puoi esplorare problemi correlati agli algoritmi avidi in questo link.

Nota: È importante selezionare il miglior approccio per un problema. L’algoritmo avido potrebbe non sempre fornire la soluzione ottimale. Ad esempio, nel problema del resto dei soldi, cosa succede se le denominazioni sono [3,5] e l’importo è 9. Un approccio algoritmico avido fallirà in questo caso, ma ci sono numerose altre soluzioni in cui funziona. Quindi, scegli il tuo approccio saggiamente.

Puoi conoscere di più sulle strutture dati e la programmazione dinamica utilizzando gli articoli sottostanti —

Comprensione del Backtracking utilizzando Python: Guida per principianti

Backtracking è un algoritmo utilizzato per cercare tutte le possibili soluzioni a un problema. In questa tecnica, troviamo una…

pub.towardsai.net

Migliorare il codice Python: Memoization vs Tabulation

La memoization è una specifica tecnica di ottimizzazione utilizzata nella programmazione informatica e nel design degli algoritmi per migliorare…

blog.devgenius.io

Spero che questo articolo sia utile… Buono studio….