Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Vai al contenuto

Teoria dei grafi applicata al mondo reale

La teoria dei grafi, con i suoi algoritmi e le sue proprietà matematiche sviscerate in lungo e in largo, è una delle prove più lampanti del fatto che la teoria non sia “solo teoria”, come l’approccio pragmatico tende spesso a declassarlo: dietro la teoria c’è la potenza della scoperta e quella delle parole, e non solo chiacchiere da universitari. Più che altro la teoria andrebbe nobilitata di per sè, ma è un lungo percorso culturale da intraprendere e non è il caso di approfondirlo qui: ci interessa proporre un po’ di teoria dei grafi e far vedere soprattutto come si possa applicare al mondo reale.

Definizione grafo

Un grafo (indicato con la lettera G) è una struttura afferente alla matematica discreta, cioè quella costituita da numeri interi, che è composto generalmente da due insieme N e A:

G = (N, A)

N indica i Nodi del grafo mentre A indica gli archi, con notazione inglese edges e nodes, mentre in alcuni vecchi libri di teoria i nodi possono essere indicati come vertici. Un grafo è rappresentabile come una coppia di insiemi N ed A, dove N è dato da una serie di etichette univoche (lettere o numeri senza ripetizioni), che rappresentazion le varie “zone” del grafo, mentre A è composto dalle coppie di nodi che sono effettivamente raggiungibili.

Grafo non orientato e grafo completo

Per intenderci, il seguente grafo presenta N e A fatti come indicato:

N = {1, 2, 3, 4, 5, 6}

A = {(1,2), (1,5), (5,2), (5,4), (4,3), (3,2), (6,4)}

6n graf

e si tratta di un grafo non orientato, dato che non è indicato il verso di percorrenza dello stesso. A è composto da un sottoinsieme di tutte le possibili combinazioni di coppie di nodi, che sono numericamente pari al prodotto cartesiano N x N, tutte le combinazioni possibili escludendo le non-coppie come (3,3), di cardinalità:

n * (n-1) / 2 = 6 * 5 / 2 = 15  // numero massimo di archi con n nodi a disposizione

ovvero enumerando le possibili coppie di n nodi (numero di archi) senza ripetizione (dette combinazioni, tecnicamente) avremmo:

(1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
(2, 3), (2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6),
(4, 5), (4, 6),
(5, 6)

Quindi, in un grafo totalmente connesso con 6 nodi, ci sono 15 archi. Il grafo in questo caso sarà completo.

5
Di Koko90 – Opera propria, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=10947365

I grafi sono dotati di proprietà matematiche di vario genere, abbastanza complesse da mettere nero su bianco in modo divulgativo, e rappresentano un modello per molte cose del mondo reale: reti di calcolatori, connettività di router, relazioni tra persone, reti sociali, strade e via dicendo.

L’interno di un grafo si possono definire vari aspetti ulteriori:

  1. Per esempio posso inserire delle etichette sui nodi, che rappresentano una quantità di materiale che posso spostare da una parte all’altra, perché pone il grafo come utile per stabilire le consegne e le tempistiche delle app di logistica (e anche di quelle di Glovo, in parte).
  2. Posso anche inserire dei “pesi” sugli archi per indicare i tempi di percorrenza oppure la lunghezza di una strada, in modo tale che poi possa minimizzare il cammino che è necessario percorrere, ad esempio, per andare da un punto A fino a un punto B diverso da A.
  3. Posso creare dei grafi che presentano dei cicli, ovvero della sequenza in cui il primo e l’ultimo nodo è stesso, che è il caso pratico in cui un fattorino lavora su una rete di consegne e alla fine deve riportare il furgone al magazzino.
  4. Posso inoltre definire dei grafi in cui non siano presenti dei cicli (detti alberi), il che mi aiuterà a definire delle strutture gerarchiche, possono aiutarmi a implementare processi decisionali di vario genere, oppure app di intelligenza artificiale. A loro volta, gli alberi possono essere binari se hanno massimo due nodi in uscita da ogni nodi, n-ari se ne hanno n, gli alberi binari vengono utilizzati per rappresentare in modo efficiente gli indici dei database.

Non finisce qui perché si possono fare molte altre cose: definire per esempio il grado di un nodo, ovvero il numero di archi che escono dallo stesso, definire dei grafi in cui sia possibile avere dei collegamenti tra un nodo e se stesso (alcune applicazioni potrebbero dare senso ad una cosa del genere), in genere l’argomento è talmente vasto che esistono numerosi libri per coprire argomento, e molto spesso neanche bastano. Quello che ci interessa se il grado di ogni nodo e pari si tratta di un grafo euleriano, che gode di determinate proprietà e “raccomandazioni”: ad esempio la possibilità di eseguire al suo interno algoritmi specialistici più efficenti della media.

Sono su queste strutture sono consolidati da anni, e sono già presenti e pronti all’uso all’interno dei linguaggi di programmazione.  Grafi e alberi vengono in genere rappresentati, per concludere, o come liste di oggetti oppure come matrici di numeri.

Algoritmo BFS (Breadth-First Search)

Un esempio semplice di problema su un grafo non orientato potrebbe essere quello di trovare il percorso più corto tra due nodi, ovvero il percorso con il minor numero di archi tra i due nodi. Un algoritmo comune per risolvere questo problema è l’algoritmo di ricerca in ampiezza (BFS – Breadth-First Search). Ecco una descrizione dell’algoritmo:

  1. Inizializza una coda vuota e una lista di nodi visitati.
  2. Inserisci il nodo di partenza nella coda e segnalo come visitato.
  3. Finché la coda non è vuota, estrai un nodo dalla coda.
  4. Per ogni nodo adiacente non ancora visitato, inseriscilo nella coda e segnalalo come visitato. Registra il nodo padre per ogni nodo visitato.
  5. Se il nodo estratto corrisponde al nodo di destinazione, hai trovato il percorso più corto. Puoi ricostruire il percorso risalendo dai nodi visitati utilizzando i nodi padre.
  6. Se la coda si svuota senza raggiungere il nodo di destinazione, significa che non esiste un percorso tra i due nodi.

L’algoritmo BFS esplora il grafo in ampiezza, visitando prima i nodi a distanza 1 dal nodo di partenza, poi i nodi a distanza 2 e così via. Questo garantisce che, una volta che il nodo di destinazione viene raggiunto, è stato trovato il percorso più corto in termini di numero di archi.

L’algoritmo BFS può essere implementato utilizzando una coda per mantenere traccia dei nodi da visitare e una struttura dati per tenere traccia dei nodi visitati e dei loro nodi padre.

Esempio pratico BFS

Ecco un esempio con un grafo non orientato di 4 nodi:

Supponiamo di avere un grafo non orientato con i nodi A, B, C e D, e i seguenti archi:

  • A è collegato a B
  • B è collegato a C
  • C è collegato a D
  • A è collegato a C

L’obiettivo è trovare il percorso più corto tra due nodi, ad esempio tra A e D.

Possiamo rappresentare il grafo nel seguente modo:

A --- B
|     |
|     |
C --- D

Utilizzando l’algoritmo BFS, eseguiamo i seguenti passaggi:

  1. Inizializzazione:
    • Nodo di partenza: A
    • Nodo di destinazione: D
    • Coda: [A]
    • Nodi visitati: []
  2. Iterazione 1: Estraiamo il primo nodo dalla coda, che è A. Segnamo A come visitato.
    • Nodi visitati: [A]
    • Coda: []
    • Nodi adiacenti di A: B, C
  3. Iterazione 2: Esploriamo i nodi adiacenti di A, ovvero B e C. Inseriamo B e C nella coda e li segniamo come visitati. Inseriamo anche il loro nodo padre, che è A.
    • Nodi visitati: [A, B, C]
    • Coda: [B, C]
    • Nodi adiacenti di B: A, C
    • Nodi adiacenti di C: A, B
  4. Iterazione 3: Estraiamo il primo nodo dalla coda, che è B. Segnamo B come visitato.
    • Nodi visitati: [A, B, C]
    • Coda: [C]
    • Nodi adiacenti di B: A, C
  5. Iterazione 4: Esploriamo il nodo adiacente di B, che è C. Inseriamo C nella coda e lo segniamo come visitato. Inseriamo anche il suo nodo padre, che è B.
    • Nodi visitati: [A, B, C]
    • Coda: [C]
    • Nodi adiacenti di C: A, B, D
  6. Iterazione 5: Estraiamo il primo nodo dalla coda, che è C. Segnamo C come visitato.
    • Nodi visitati: [A, B, C]
    • Coda: []
    • Nodi adiacenti di C: A, B, D
  7. Iterazione 6: Esploriamo il nodo adiacente di C, che è D. Troviamo il percorso più corto.
    • Nodi visitati: [A, B, C, D]
    • Coda: []

Una volta raggiunto il nodo di destinazione D, possiamo ricostruire il percorso risalendo dai nodi visitati utilizzando i nodi padre. Nel nostro caso, il percorso più corto da A a D è: A -> C -> D.

Altre applicazioni nel mondo reale

Gran parte della matematica che viene usata nei grafici viene assunta come implicita, E in larga parte oggetto di studio da parte dei matematici più specializzati in genere bisognerebbe quasi sempre aspettarsi che possano esistere, un giorno, dei miglioramenti agli algoritmi esistenti. La cosa incredibile di questo genere di applicazioni e che viene utilizzata ogni giorno, spesso senza che neanche ce ne accorgiamo – E ci sono applicazioni sui grafici che possono supportare per esempio le decisioni che prendiamo ogni giorno, pure che fanno uso di graffi particolari che sono detti alberi, in cui non sono presenti cicli, e che si chiamano alberi decisionali.

Non è difficile immaginare il concetto di cammino all’interno di un grafo, a questo punto: la ricerca dei cammini è una delle cose che sono state più studiate storicamente all’interno di questa disciplina. Molti problemi sono stati risolti da tempo e molti altri sono noti soltanto a livello teorico, o meglio: esistono degli algoritmi approssimati ho visti per risolverli, ma non c’è un metodo per farlo che sia esatto (cioè che produca un risultato completamente corretto). Le approssimazioni sono, nostro malgrado, l’unica strada percorribile in molti casi, dato che la complessità temporale-spaziale di questi problemi è in genere molto elevate. Ma le applicazioni?

Google Maps

Proviamo a pensare per un attimo a Google Maps, che molti di noi utilizzano abitualmente come navigatore: se vogliamo andare da casa nostra fino al cinema, ad esempio, ci propone diverse alternative che si basano sul fatto di essere a piedi, di avere una macchina, di voler prendere i mezzi pubblici e così via.

Per determinare il percorso vengono effettuati dei calcoli appositi su un grafo modellato sulla rete stradale, dove bisognerà fare qualche approssimazione per definire la “percorribilità” dello stesso e dove, per intenderci, i nodi sono dislocati in vari punti della strada, per cui se ci troviamo ad es. in un’area di 10 m² è plausibile che ci siano più nodi, dipende da come sono stati implementati e dalla convenienza nel farlo. Se poi ci sono degli edifici o degli ostacoli, pure se ci sono delle strade percorribili a piedi e non con la macchina, mira a creare più grafi per ogni possibile percorso. Nota a margine per completezza: su una rete stradale tipicamente il grafo sarà orientato, dato che esistono i sensi unici – e in generale non è possibile percorrere tutte le strade in qualunque verso.

Per semplificare il discorso in termini comprensibili, possiamo provare a immaginare un percorso che ci porti da casa al cinema (e viceversa) con la possibilità di risparmiare benzina, oppure di arrivare nel minor tempo possibile. A seconda dell’obiettivo che abbiamo cambieranno le strategie, e saranno possibili diverse varianti tutte di pari interesse, al variare del contesto.

Cammino più breve

Per determinare il percorso più breve tra due punti, come ad esempio da casa al cinema, possiamo utilizzare:

  1. l’algoritmo di Dijkstra
  2. l’algoritmo di A*

Entrambi gli algoritmi sono ampiamente utilizzati per problemi di routing e navigazione. La scelta tra i due dipenderà dalle caratteristiche specifiche del problema e dalle informazioni disponibili sul grafo o sulla mappa di riferimento.

L’algoritmo di Dijkstra è un algoritmo classico per la ricerca del percorso più breve, in un grafo pesato e orientato. Questo algoritmo trova il percorso più breve tra un nodo di partenza e tutti gli altri nodi nel grafo. Puoi utilizzare l’algoritmo di Dijkstra per trovare il percorso più breve sia da casa al cinema che dal cinema a casa. Funziona così:

Ecco una spiegazione passo passo dell’algoritmo di Dijkstra per trovare il percorso più breve tra due punti in un grafo pesato e orientato:

  1. Inizializza il grafo:
    • Assegna un valore di distanza infinito a tutti i nodi tranne il nodo di partenza, a cui viene assegnato un valore di distanza 0.
    • Inizializza un insieme vuoto chiamato “visitati” per tenere traccia dei nodi visitati.
  2. Seleziona il nodo di partenza e assegna una distanza di 0. Questo sarà il nodo iniziale da cui inizia l’algoritmo.
  3. Trova il nodo con la distanza minima non ancora visitato. Inizia con il nodo di partenza, che avrà una distanza 0 all’inizio.
  4. Per il nodo selezionato, considera tutti i suoi nodi adiacenti non visitati e calcola la distanza temporanea sommando la distanza del nodo corrente e il peso dell’arco che li collega.
  5. Se la distanza temporanea calcolata è inferiore alla distanza corrente del nodo adiacente, aggiorna la distanza del nodo adiacente con la distanza temporanea.
  6. Segna il nodo corrente come visitato e rimuovilo dall’insieme dei nodi non visitati.
  7. Ripeti i passaggi 3-6 fino a quando tutti i nodi sono stati visitati o fino a quando non raggiungi il nodo di destinazione.
  8. Alla fine dell’algoritmo, avrai la distanza più breve per raggiungere ogni nodo dal nodo di partenza. Puoi costruire il percorso più breve risalendo dai nodi di destinazione utilizzando le distanze calcolate.

L’algoritmo di Dijkstra garantisce che la distanza finale calcolata per ogni nodo sia la distanza più breve dal nodo di partenza. Questo ti fornirà il percorso più breve per andare da casa al cinema o viceversa.

A*

L’algoritmo di A* (A-star) è un’altra opzione che può essere utilizzata per trovare il percorso più breve tra due punti in un grafo. A* utilizza una combinazione di una funzione di costo e una stima del costo rimanente (euristica) per selezionare il percorso più promettente da esplorare. Questo algoritmo può essere utile se hai informazioni sulla distanza approssimativa tra i punti di interesse, ad esempio attraverso una mappa stradale o coordinate GPS.

Ecco una spiegazione passo passo dell’algoritmo A* (A-star) per trovare il percorso più breve tra due punti in un grafo:

  1. Inizializza il grafo:
    • Assegna un valore di costo infinito a tutti i nodi tranne il nodo di partenza, a cui viene assegnato un costo di 0.
    • Inizializza un insieme vuoto chiamato “visitati” per tenere traccia dei nodi visitati.
  2. Calcola una stima del costo rimanente (euristica) da ogni nodo al nodo di destinazione. Questa euristica deve essere ammissibile, il che significa che non sovrastima mai il costo effettivo per raggiungere la destinazione. Un esempio comune di euristica è la distanza euclidea tra due punti.
  3. Seleziona il nodo di partenza e assegna un costo di 0. Questo sarà il nodo iniziale da cui inizia l’algoritmo.
  4. Calcola la funzione di costo f(n) per ogni nodo, data dalla somma del costo effettivo per raggiungere il nodo (g(n)) e la stima del costo rimanente per raggiungere la destinazione (h(n)).
  5. Trova il nodo con il valore di f(n) minimo non ancora visitato. Inizia con il nodo di partenza, che avrà una funzione di costo f(n) di 0.
  6. Per il nodo selezionato, considera tutti i suoi nodi adiacenti non visitati. Calcola la funzione di costo g(n) temporanea sommando il costo corrente del nodo e il peso dell’arco che li collega.
  7. Se la funzione di costo g(n) temporanea calcolata è inferiore alla funzione di costo g(n) corrente del nodo adiacente o se il nodo adiacente non è ancora stato visitato, aggiorna la funzione di costo g(n) e imposta il nodo padre del nodo adiacente al nodo corrente.
  8. Aggiorna la funzione di costo f(n) del nodo adiacente con la somma della funzione di costo g(n) e dell’euristica h(n).
  9. Segna il nodo corrente come visitato e rimuovilo dall’insieme dei nodi non visitati.
  10. Ripeti i passaggi 5-9 fino a quando raggiungi il nodo di destinazione o fino a quando non hai più nodi da visitare.
  11. Alla fine dell’algoritmo, avrai il percorso più breve dal nodo di partenza al nodo di destinazione. Puoi costruire il percorso risalendo dai nodi di destinazione utilizzando i nodi genitori salvati durante l’esecuzione dell’algoritmo.

L’algoritmo A* utilizza sia il costo effettivo per raggiungere un nodo (g(n)) che una stima del costo rimanente (h(n)) per prendere decisioni sulla scelta del prossimo nodo da esplorare. Questo permette ad A* di spostarsi in direzione della destinazione e di trovare un percorso più efficiente rispetto all’algoritmo di Dijkstra in molti casi.

Problema del postino cinese

Ovviamente l’argomento non finisce qui, e ce ne sarebbero da raccontare: ci fermiamo citando un problema particolarmente simpatico, qui rende l’idea di quanto possa essere compresa questa disciplina è interessante per risolvere i problemi del mondo reale. Parliamo quindi del problema del postino cinese, la cui formulazione matematica non è banale ma, per quello che ci interessa, tanto vale presentarla in veste pratica ancora una volta qui.

Supponiamo di avere un grafo non orientato con 6 nodi con i seguenti archi:

  • A è collegato a B (con peso 2)
  • A è collegato a C (con peso 1)
  • B è collegato a C (con peso 3)
  • B è collegato a D (con peso 2)
  • C è collegato a D (con peso 1)
  • C è collegato a E (con peso 4)
  • D è collegato a E (con peso 3)
  • D è collegato a F (con peso 2)
  • E è collegato a F (con peso 4)

L’obiettivo del problema del postino cinese è trovare un percorso chiuso che attraversi ogni arco del grafo almeno una volta, minimizzando la somma dei pesi degli archi percorsi.

Potremmo rappresentare il grafo nel seguente modo:

  A --- B
   | \   | \
   |   \ |   \
   C --- D --- E
         \   /
          \ /
           F

Utilizzando l’algoritmo del postino cinese, riusciremo a determinare un possibile percorso chiuso che attraversa tutti gli archi con il peso totale minimo, ovvero:

A -> B -> C -> A -> C -> D -> E -> F -> D -> B -> A.

Questo percorso ha una somma dei pesi degli archi pari a 2 + 3 + 1 + 2 + 3 + 2 + 4 + 2 + 1 = 20.

(Immagine di copertina generata da StarryAI)

Da non perdere 👇👇👇



Questo sito web esiste da 4407 giorni (12 anni), e contiene ad oggi 3918 articoli (circa 3.134.400 parole in tutto) e 12 servizi online gratuiti. – Leggi un altro articolo a caso
Non ha ancora votato nessuno.

Ti sembra utile o interessante? Vota e fammelo sapere.

Questo sito contribuisce alla audience di sè stesso.
Il nostro network informativo: Lipercubo.it - Pagare.online - Trovalost.it.