Immersioni profonde in traversate grafiche

Ci sono oltre 2,07 miliardi di utenti Facebook attivi mensili in tutto il mondo a partire dal terzo trimestre del 2017. L'aspetto più importante della rete di Facebook è l'impegno sociale tra gli utenti. Più amici ha un utente, più le conversazioni diventano coinvolgenti tramite commenti su post, messaggi, ecc. Se hai usato Facebook abbastanza regolarmente, devi conoscere la funzione Raccomandazione degli amici.

Facebook consiglia un gruppo di persone che possiamo aggiungere come amici. Il più delle volte, queste sono persone di cui non abbiamo mai sentito parlare prima. Tuttavia, Facebook pensa che dovremmo aggiungerli. La domanda è: in che modo Facebook fornisce una serie di raccomandazioni per una persona specifica?

Un modo per farlo è basato su amici comuni. ad esempio: - Se un utente A e C non si conoscono, ma hanno un amico comune B, probabilmente anche A e C dovrebbero essere amici. Cosa succede se A e C hanno 2 amici comuni e A e D hanno 3 amici comuni? Come sarà l'ordinazione per i suggerimenti?

In questo caso, sembra abbastanza ovvio suggerire D su C ad A perché hanno più amici in comune e hanno maggiori probabilità di connettersi.

Tuttavia, due persone potrebbero non avere sempre amici comuni, ma potrebbero avere connessioni comuni di 2 ° o 3 ° grado.

Connessioni di ennesima laurea

  • A e B sono amici. (0 gradi)
  • A e B sono amici di 1 ° grado significa che hanno un amico comune.
  • A e B sono amici di 2 ° grado se hanno un amico, che è un amico di 1 ° grado con l'altra persona. ad es .: - A - C - D - B, quindi A e B sono amici di secondo grado.
  • Allo stesso modo, A e B sono amici di grado N se hanno connessioni N in mezzo. ad es .: - A - X1 - X2 - X3… .. - XN - B.

Osservando questo approccio per la raccomandazione, dobbiamo essere in grado di trovare il grado di amicizia che due utenti determinati condividono su Facebook.

Inserisci traverse del grafico

Ora che sappiamo come possono essere fatti i consigli degli amici, riaffermiamo questo problema in modo che possiamo guardarlo da una prospettiva algoritmica.

Immaginiamo un grafico non indirizzato di tutti gli utenti su Facebook, in cui i vertici V rappresentano gli utenti e i bordi E rappresentano le amicizie. In altre parole: se gli utenti A e B sono amici su Facebook, c'è un vantaggio tra i vertici A e B. La sfida è scoprire il grado di connessione tra due utenti qualsiasi.

Più formalmente, dobbiamo vedere la distanza più breve tra due nodi in un grafico non orientato, non ponderato.

Considera due vertici in questo grafico non orientato A e C. Esistono due percorsi diversi per raggiungere C:

1. A → B → C e
2. A → G → F → E → D → C

Chiaramente, vogliamo prendere la strada più piccola quando proviamo a vedere il grado di connessione tra due persone sul social network.

Fin qui tutto bene.

Prima di procedere, diamo un'occhiata alla complessità di questo problema. Come affermato in precedenza, Facebook ha circa 2,07 miliardi di utenti a partire dal terzo trimestre del 2017. Ciò significa che il nostro grafico avrà circa 2,07 miliardi di nodi e almeno (2,07 miliardi - 1) bordi (se ogni persona ha almeno un amico).

Questa è una scala enorme per risolvere questo problema. Inoltre, abbiamo anche visto che potrebbero esserci più percorsi da raggiungere da un determinato vertice di origine a un vertice di destinazione nel grafico e vogliamo che il più breve risolva il nostro problema.

Esamineremo due classici algoritmi di attraversamento dei grafici per risolvere il nostro problema:

1. Profondità Prima ricerca e
2. Ampia prima ricerca.

Profondità Prima ricerca

Immagina di rimanere bloccato in un labirinto come questo.

Devi uscire in qualche modo. Potrebbero esserci più percorsi dalla posizione iniziale all'uscita. L'approccio naturale per uscire dal labirinto è provare tutti i percorsi.

Supponiamo che tu abbia due scelte nel punto in cui ti trovi attualmente. Ovviamente, non sai quale porta fuori dal labirinto. Quindi decidi di fare la prima scelta e andare avanti nel labirinto.

Continui a fare mosse e continui ad avanzare e raggiungi un vicolo cieco. Ora vorresti idealmente provare un percorso diverso, e quindi tornare indietro a un checkpoint precedente in cui hai fatto una delle scelte e quindi provane uno nuovo, cioè questa volta un percorso diverso.

Continui a farlo finché non trovi l'uscita.

Prova ricorsiva di un percorso specifico e backtracking sono i due componenti che formano l'algoritmo Depth First Search (DFS).

Se modelliamo il problema del labirinto come un grafico, i vertici rappresenterebbero la posizione dell'individuo sul labirinto e i bordi diretti tra due nodi rappresenterebbero un singolo spostamento da una posizione a un'altra posizione. Usando DFS, l'individuo dovrebbe provare tutti i percorsi possibili fino a quando non viene trovata l'uscita.

Ecco un pseudo-codice di esempio per lo stesso.

1 procedura DFS (G, v):
2 etichetta v come scoperta
3 per tutti i bordi da v a w in G.adjacentEdges (v) do
4 se il vertice w non è etichettato come scoperto allora
5 chiama ricorsivamente DFS (G, w)

Per un approfondimento di questo algoritmo, controlla: -

Complessità temporale: O (V + E)

Larghezza Prima ricerca

Immagina una malattia contagiosa che si diffonde gradualmente in una regione. Ogni giorno, le persone che hanno la malattia infettano nuove persone con cui entrano in contatto fisico. In questo modo, la malattia sta facendo una sorta di ampiezza della prima ricerca (BFS) sulla popolazione. La "coda" è l'insieme di persone che sono state appena infettate. Il grafico è la rete di contatto fisica della regione.

Immagina di dover simulare la diffusione della malattia attraverso questa rete. Il nodo principale della ricerca è il paziente zero, il primo malato noto della malattia. Inizi con loro solo con la malattia e nessun altro.

Ora ripeti le persone con cui sono in contatto. Alcuni prenderanno la malattia. Ora ripeti tutti. Dai anche alle persone con cui sono in contatto con la malattia, a meno che non l'abbia già avuta. Continua fino a quando non hai infettato tutti o non hai infettato il tuo obiettivo. Allora hai finito. Ecco come funziona l'ampiezza della prima ricerca.

L'algoritmo di ricerca BFS esplora i vertici strato per strato a partire dal primo vertice e passa al livello successivo solo dopo aver elaborato tutti i vertici sul livello corrente.

Ecco un pseudo-codice di esempio per BFS.

1 procedura BFS (G, v):
2 q = Coda ()
3 q.enqueue (v)
4 mentre q non è vuoto:
5 v = q.dequeue ()
6 se v non è visitato:
7 contrassegna v come visitato (// elabora il nodo)
8 per tutti i bordi da v a w in G.adjacentEdges (v) do
9 q.enqueue (w)

Per una comprensione più approfondita di BFS, consulta questo articolo.

Complessità temporale: O (V + E)

Percorsi più brevi

Andiamo avanti e risolviamo il nostro problema originale: trovare il percorso più breve tra due vertici dati in un grafico non orientato.

Guardando le complessità temporali dei due algoritmi, non possiamo davvero distinguere la differenza tra i due per questo problema. Entrambi gli algoritmi troveranno un percorso (o piuttosto il percorso più breve) verso la nostra destinazione dalla fonte data.

Diamo un'occhiata al seguente esempio.

Supponiamo di voler scoprire il percorso più breve dal nodo 8 al 10. Diamo un'occhiata ai nodi esplorati da DFS e BFS prima di raggiungere la destinazione.

DFS

  • Processo 8 → Processo 3 → Processo 1.
  • Indietro a 3.
  • Processo 6 → Processo 4.
  • Indietro a 6.
  • Processo 7.
  • Indietro a 6 → Indietro a 3 → Indietro a 8.
  • Processo 10.

Un totale di 7 nodi vengono elaborati qui prima di raggiungere la destinazione. Ora diamo un'occhiata a come BFS fa le cose.

BFS

  • Processo 8 → Enqueue 3, 10
  • Processo 3 → Enqueue 1,6
  • Processo 10.

Woah, è stato veloce! Sono stati elaborati solo 3 nodi ed eravamo a destinazione.

La spiegazione di questo speedup che possiamo vedere in BFS e non in DFS è perché DFS prende un percorso specifico e va fino alla fine, cioè fino a quando non raggiunge un vicolo cieco e quindi torna indietro.

Questa è la principale caduta dell'algoritmo DFS. Potrebbe dover espandere migliaia di livelli (in un'enorme rete come quella di Facebook, solo perché ha selezionato un percorso errato da elaborare all'inizio) prima di raggiungere il percorso contenente la nostra destinazione. BFS non affronta questo problema e quindi è molto più veloce per il nostro problema.

Inoltre, anche se DFS rileva la destinazione, non possiamo essere sicuri che il percorso seguito da DFS sia il più breve. Potrebbero esserci anche altri percorsi.

Ciò significa che, in ogni caso, per il problema dei percorsi più brevi, DFS dovrebbe estendersi all'intero grafico per ottenere il percorso più breve.

Nel caso di BFS, tuttavia, la prima occorrenza del nodo di destinazione garantisce che sia quello alla distanza più breve dalla sorgente.

Conclusione

Finora abbiamo discusso del problema della Raccomandazione Amici di Facebook e l'abbiamo ridotto al problema di trovare il grado di connessioni tra due utenti nel grafico della rete.

Quindi abbiamo discusso di due interessanti algoritmi Graph Traversal che sono molto comunemente usati. Infine, abbiamo esaminato quale algoritmo funziona meglio per risolvere il nostro problema.

Breadth First Search è l'algoritmo che desideri utilizzare se devi trovare la distanza più breve tra due nodi in un grafico non orientato e non ponderato.

Diamo un'occhiata a questo divertente problema per descrivere la differenza tra i due algoritmi.

Supponendo di aver letto attentamente la dichiarazione del problema, proviamo innanzitutto a modellarlo come problema grafico.

Lascia che tutte le stringhe possibili diventino nodi nel grafico e abbiamo un bordo tra due vertici se hanno una singola mutazione tra di loro.

Facile vero?

Ci viene data una stringa iniziale (leggi il testo di origine) ad es .: - "AACCGGTT" e dobbiamo raggiungere la stringa di destinazione (leggi il vertice di destinazione) "AACCGGTA" nel numero minimo di mutazioni (leggi il numero minimo di passaggi) in modo tale che tutte le stringhe intermedie (nodi) dovrebbero appartenere alla data word bank.

Prova a risolvere questo problema da solo prima di esaminare la soluzione di seguito.

Se provi a risolverlo usando DFS, troverai sicuramente una soluzione, ma ci sono casi di test che supereranno il limite di tempo assegnato sulla piattaforma LeetCode. Ciò è dovuto al problema descritto in precedenza sul motivo per cui DFS impiega così tanto tempo (elaborare 7 nodi anziché 3 in BFS) per raggiungere il vertice di destinazione.

Spero che tu abbia avuto l'idea principale dietro i due attraversamenti del grafico principale e la differenza tra loro quando l'applicazione ha percorsi più brevi in ​​un grafico non ponderato non indirizzato.

Consiglia (recommend) questo post se pensi che possa essere utile per qualcuno!