L'algoritmo di Dijkstra è un algoritmo greedy o un algoritmo di programmazione dinamica?

Un punto sottile si sta perdendo in alcune risposte qui (compresa la risposta migliore in questo momento, Nathan Pinsker's risposta a Is Dijkstra's Algorithm a greedy algorithm or a dynamic programming algorithm?), quindi ho bisogno di intervenire in quanto è parzialmente sbagliato e piuttosto fuorviante.

I problemi hanno una struttura che sfruttiamo per progettare algoritmi per loro. Il problema del percorso più breve non è un "problema DP". È un problema che può essere risolto con tecniche come la programmazione dinamica. Questo è un errore comune che le persone fanno; parlano di problemi rispetto agli algoritmi invece del modo corretto (algoritmi rispetto ai problemi). Penso che molta della confusione qui sia più pedagogica che scientifica; come siete stati introdotti all'algoritmo. Non conosco nessun testo di riferimento standard in aree che vanno dall'ottimizzazione combinatoria all'analisi degli algoritmi che si riferisca all'algoritmo come un algoritmo di programmazione dinamica (dato che non lo è). Per esempio, il testo molto usato Algorithm Design di Kleinberg e Tardos lo descrive quasi certamente come un algoritmo greedy:

Fonte: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/04GreedyAlgorithmsII-2x2.pdf

Per non parlare, Introduction to Algorithms di Cormen et al. lo considera sicuramente un algoritmo greedy.

Fonte: Introduction To Algorithms

L'algoritmo di Dijkstra normalmente impiega una coda di priorità, non si potrebbe realizzare questo in un ambiente in cui si avrebbe esclusivamente bisogno di programmazione dinamica.

Tipicamente è considerato un algoritmo greedy in quanto utilizza fondamentalmente la proprietà di scelta greedy per ottenere l'ottimo. Ma si può implementare l'algoritmo di Dijkstra come un algoritmo di programmazione dinamica. È importante capire che queste due categorie non sono disgiunte, l'algoritmo ha proprietà su cui si potrebbe discutere. Normalmente quando le persone discutono di algoritmi di programmazione dinamica, parlano di derivare una relazione di ricorrenza e riempire una tabella per ottenere il valore ottimale, poi (a volte) applicare il backtracing per ottenere la soluzione effettiva. Questo è normalmente ciò a cui ci si riferisce come approccio di programmazione dinamica, perché utilizza il principio di ottimalità (vedi equazione di Bellman - Wikipedia). Il valore dell'ottimo è garantito per essere trovato attraverso il principio di ottimalità. Si può fare questo in un modo simile all'algoritmo di Dijkstra, ma il modo in cui la maggior parte implementa Dijkstra non si adatta a questo perché non abbiamo bisogno di compilare l'intera tabella. Sappiamo che il problema del percorso più breve soddisfa la proprietà di scelta greedy (se volete scavare più a fondo, andate a guardare le matroidi greedy), perché tirare fuori gli strumenti più forti?

Per gli studenti, normalmente lo chiamo un algoritmo greedy perché si adatta a tutto ciò che rende un algoritmo greedy. Si usa sempre l'optimum locale per costruire la soluzione. A volte è utile sottolineare l'approccio di programmazione dinamica che si può usare per scrivere anche l'algoritmo di Dijkstra, ma poi l'algoritmo di Dijkstra può essere derivato in così tanti modi diversi (anche attraverso la programmazione lineare) che diventa un po' troppo sciolto per gli studenti principianti e normalmente vogliamo mostrare gli approcci più efficienti. Meglio tenerlo semplice. Trovo che confonda solo gli studenti chiamarla programmazione dinamica nonostante noi abbiamo etichette migliori per essa. Ma, devo sottolineare che si può scrivere l'algoritmo di Dijkstra come un vero e proprio algoritmo di programmazione dinamica, ma questo approccio non è neanche lontanamente efficiente come l'algoritmo greedy di cui normalmente discutiamo (e a cui facciamo riferimento in questi giorni).

Il modo in cui le persone descrivono gli algoritmi può diventare molto più semplice e raffinato nel tempo. Voglio dire, se si prende l'approccio che normalmente insegniamo dove si ha un array che memorizza le distanze che si aggiornano, questo non è un algoritmo DP perché si costruisce la soluzione mentre si va avanti (si sceglie sempre il minimo per essere il prossimo vertice mentre si esplora il grafico), non si trova l'ottimo poi si fa il backtrace (che è quello che fa un algoritmo DP). Se si dice solo "oh usa la memorizzazione" per affermare che è un algoritmo DP, molti algoritmi possono essere chiamati algoritmi DP, il che non è affatto utile. Le caratteristiche fondamentali e tipiche di un algoritmo DP sono quelle di utilizzare il principio di ottimalità per calcolare il valore ottimale, quindi costruire la soluzione attraverso l'attraversamento di sotto-soluzioni ottimali. Trovo che non sia utile chiamarlo più in generale un algoritmo DP poiché il modo in cui lo insegniamo normalmente è costruire la soluzione man mano che si procede con zero backtracing. Perché tenere tutti i passaggi extra quando si ha a disposizione la proprietà di scelta avida?

Il problema del percorso più breve è molto interessante perché per questo problema funzionano così tanti approcci che si sovrappongono.

In breve: è un algoritmo avido, ma può essere scritto come un algoritmo di programmazione dinamica (ma questo non è altrettanto efficiente in termini di spazio). Come descritto dagli esperti del nostro campo citato sopra, non si adatta al processo di un algoritmo DP (come si userebbe il principio di ottimalità).