Implementazione universale degli algoritmi BFS, DFS, Dijkstra e A-Star

Universal implementation of BFS, DFS, Dijkstra, and A-Star algorithms

Risulta che algoritmi ben noti come BFS, DFS, Dijkstra e A-Star sono essenzialmente variazioni dello stesso algoritmo.

In altre parole, è possibile implementare una struttura dati universale che può passare tra questi algoritmi senza richiedere modifiche ai suoi componenti principali. Sebbene ci siano alcune limitazioni da considerare, esplorare questo approccio è interessante.

Puoi trovare tutto il codice funzionante per questi algoritmi nel mio repository GitHub qui. Raccomando di sperimentare con il codice mentre leggi questo articolo poiché l’esperienza pratica migliora l’apprendimento più della sola comprensione teorica.

Rappresentazione del grafo

Consideriamo un grafo con 25 nodi disposti in una griglia 5×5, dove l’obiettivo è trovare un percorso dal Nodo 0 nell’angolo in alto a sinistra al Nodo 24 nell’angolo in basso a destra:

• Trasformare i pixel in etichette descrittive Padronanza della classificazione multiclasse delle immagini con TensorFlow
• Il decoratore Python che potenzia l’esperienza dello sviluppatore 🚀
• Questa ricerca sull’IA presenta un modello di deep learning che può rubare dati ascoltando le pressioni dei tasti registrate da un telefono vicino con un’accuratezza del 95%.

Ogni uno degli algoritmi menzionati è in grado di raggiungere questo obiettivo, ma hanno le proprie limitazioni:

• Sia gli algoritmi BFS che DFS operano su grafi non pesati, ignorando i pesi degli archi. Sebbene possano trovare qualsiasi percorso, non garantiscono il percorso ottimale.
• Sia l’algoritmo di Dijkstra che A-Star funzionano su grafi pesati, ma non dovrebbero essere utilizzati con grafi contenenti pesi negativi. A-Star è di solito più veloce grazie all’ottimizzazione che incorpora le coordinate euclidee durante la ricerca del percorso.

In questo articolo, non tratto i concetti di base, sperando che tu ne sia già familiare. Se i termini menzionati sopra ti sembrano intimidatori, probabilmente dovresti imparare anche le basi. Tuttavia, giocare con questi esempi di codice può essere comunque eccitante.

Per tener conto di queste limitazioni, assegniamo coordinate immaginarie a ciascun nodo (X, Y):

Infine, assegniamo un peso ad ogni arco nel grafo:

In C++, questa struttura può essere rappresentata come segue:

L’elenco degli archi nel Grafo è rappresentato da un array di array, dove l’indice corrisponde al numero del nodo di uscita per ciascun arco nel grafo. Poi, ogni elemento contiene una coppia di valori:

1. Il numero del nodo di ingresso per ciascun arco nel grafo.
2. Il peso dell’arco.

Utilizzando questa semplice struttura, possiamo attraversare ogni nodo nel grafo e ottenere tutte le informazioni necessarie sulle sue connessioni:

Ora, creiamo alcune connessioni personalizzate all’interno del grafo per osservare l’effetto sul funzionamento del nostro algoritmo universale. Poiché questo codice non è il punto focale qui, fornirò i link ai metodi pertinenti:

• Generazione di una lista di nodi
• Creazione di connessioni personalizzate

In alternativa, è anche possibile generare in modo pigro tutte le connessioni e i pesi in questo grafo con ancora meno codice. Tuttavia, questo approccio potrebbe non fornire una comprensione esaustiva delle differenze effettive in cui gli algoritmi attraversano il grafo.

Algoritmo universale

Alla base dell’algoritmo universale di ricerca del percorso si trova la struttura dati universale, che chiameremo “Queue” per scopi di questo progetto. Tuttavia, non è una classica struttura dati FIFO (First-In-First-Out). Invece, è una struttura generale che ci consente di implementare l’inserimento dei nodi durante la ricerca, potendo cambiare il meccanismo di inserimento in base all’algoritmo utilizzato. L’interfaccia per questa “Queue” è semplice:

Prima di approfondire i dettagli della Queue, esaminiamo l’algoritmo di ricerca stesso.

In sostanza, assomiglia molto a un tipico algoritmo di A-Star o Dijkstra. Prima di tutto, dobbiamo inizializzare un insieme di collezioni che ci consentano di:

• Mantenere un elenco di nodi che non sono ancora stati elaborati (colore bianco), che vengono attualmente elaborati (colore grigio) e che sono stati elaborati/visitati (colore nero).
• Tenere traccia della distanza attuale del percorso più breve dal nodo di partenza a ciascun nodo nella collezione.
• Memorizzare un elenco di coppie di nodi precedenti-successivi che ci consentono di ricostruire il percorso finale in seguito.

main.cpp#L18:

In seguito, dobbiamo inizializzare la nostra struttura dati. Utilizzando il codice fornito nel repository GitHub, è sufficiente rimuovere il commento dalla riga di codice necessaria. Il codice non è progettato per selezionare la struttura dati in base a un parametro perché voglio che tu sperimenti attivamente con essa per acquisire una migliore comprensione (sì, sono un tipo duro :D).

Infine, l’algoritmo stesso. In sostanza, è una combinazione di tutti e tre gli algoritmi con alcuni controlli aggiuntivi. Iniziamo con una “customQueue” ed eseguiamo l’algoritmo finché non diventa vuota. Quando esaminiamo ogni nodo vicino nel grafo, inseriamo in coda ogni nodo che potenzialmente deve essere attraversato successivamente. Quindi, chiamiamo il metodo getFirst(), che estrae solo un nodo che deve essere attraversato successivamente nell’algoritmo.

main.cpp#L48:

Fino a questo punto, l’implementazione non differisce significativamente da altri esempi che potresti trovare nei libri o su internet. Tuttavia, qui si trova l’aspetto chiave – getFirst() è il metodo che serve al fine principale in quanto determina l’ordine esatto di attraversamento dei nodi.

Coda BFS

Diamo uno sguardo più da vicino al funzionamento interno della nostra struttura dati coda. L’interfaccia della coda per BFS è la più semplice. bfsQueue.h#L11:

In realtà, potremmo semplicemente sostituire qui l’interfaccia personalizzata della coda con la coda standard di C++ fornita dalla STL (Standard Template Library). Tuttavia, l’obiettivo qui è l’universalità. Ora, devi solo togliere il commento alla riga nel metodo principale e eseguire questo algoritmo: //bfsQueue customQueue; // RIMUOVI I COMMENTI PER USARE BFS

Come risultato, BFS trova il percorso 24<-19<-14<-9<-8<-7<-6<-1<-0.

Se consideriamo i pesi, il costo finale di questo percorso sarà 11. Tuttavia, ricorda che né BFS né DFS considerano i pesi. Invece, attraversano tutti i nodi nel grafo, sperando di trovare il nodo desiderato prima o poi.

Coda DFS

DFS non sembra molto diverso. Sostituiamo solo la coda STD con uno stack. dfsStack.h#L11:

DFS trova il percorso 24<-23<-22<-21<-20<-15<-10<-5<-0 con un costo di 15 (non dà priorità al trovare il costo ottimale). Interessante, attraversa nella direzione opposta rispetto a BFS:

Coda di Dijkstra

Adesso, l’algoritmo di Dijkstra è l’algoritmo di ricerca avido più noto in un grafo. Nonostante le sue limitazioni note (incapacità di gestire percorsi negativi, cicli, ecc.), rimane popolare ed efficiente abbastanza.

È importante notare che il metodo getFirst() in questa implementazione utilizza un approccio avido per selezionare i nodi da attraversare. dijkstraQueue.h#L17:

L’algoritmo di Dijkstra trova il percorso PIÙ BREVE e più OTTIMALE 24<-19<-18<-13<-12<-7<-6<-1<-0 con un costo di 10:

A-Star

L’algoritmo A-Star è particolarmente adatto per i casi in cui si cerca un percorso in uno spazio euclideo con coordinate, come le mappe. Questo è il motivo per cui è ampiamente utilizzato nei giochi. Non solo utilizza una ricerca avida “cieca” basata sui pesi minimi, ma considera anche la distanza euclidea fino all’obiettivo. Di conseguenza, è di solito molto più efficiente dell’algoritmo di Dijkstra in scenari pratici (fai riferimento al mio altro progetto GitHub per ulteriori dettagli). aStarQueue.h#L18:

Come risultato, otteniamo gli stessi risultati dell’algoritmo di Dijkstra perché fornisce il percorso più ottimale.

È possibile che questo esempio possa essere troppo semplicistico per mostrare le vere differenze di prestazioni tra questi algoritmi. Se sei interessato ad esplorare il potenziale di questi algoritmi, fai riferimento al mio altro progetto, che implementa questi algoritmi in modo efficiente e utilizza un approccio più visivo con una vasta gamma di dati di prova.

Svantaggi

Tuttavia, c’è un problema con i nostri algoritmi di Dijkstra e A-Star… L’implementazione sopra utilizza un vettore (un array dinamico []) all’interno della nostra struttura dati universale. Ad ogni chiamata a getFirst(), ci vuole un tempo O(N) per trovare il nodo richiesto nel vettore. Di conseguenza, assumendo che anche l’algoritmo principale richieda un tempo O(N*M), dove M è il numero medio di vicini, la complessità complessiva potrebbe diventare quasi cubica. Ciò porterebbe a una significativa degradazione delle prestazioni su grafi grandi.

Sebbene questo esempio sia utile per comprendere l’idea generale che tutti e quattro gli algoritmi non sono fondamentalmente diversi, il diavolo sta nei dettagli. Implementare tutti e quattro gli algoritmi in modo efficiente utilizzando una struttura dati universale è una sfida.

Per prestazioni ottimali (che sono tipicamente la preoccupazione principale nel 99% dei casi), dovrebbe essere dedicato più sforzo alle ottimizzazioni. Ad esempio, ha molto senso utilizzare una coda prioritaria invece di un array sia per gli algoritmi di Dijkstra che per quelli di A-Star.

Parlando delle ottimizzazioni dell’algoritmo A-Star, ha molto senso menzionare alcuni link che apriranno un mondo profondo di ottimizzazioni: A* Ottimizzazioni e Miglioramenti di Lucho Suaya e JPS+: Oltre 100 volte più veloce di A* di Steve Rabin.

Parola finale

Lo scopo di questo articolo era quello di mostrare quanto siano rilevanti tra loro tutti gli algoritmi di attraversamento. Ma l’esempio di un grafo utilizzato in questo articolo è sicuramente troppo semplicistico per dimostrare le vere differenze di prestazioni tra questi algoritmi. Pertanto, utilizza questi esempi principalmente per acquisire una comprensione concettuale piuttosto che per scopi produttivi.

Se sei interessato a esplorare il potenziale di questi algoritmi, leggi il mio prossimo articolo basato sul mio altro progetto, che implementa questi algoritmi in modo efficiente e utilizza un approccio più visivo con una vasta gamma di dati di test.

Rimani sintonizzato!