Quali sono i 10 algoritmi che si devono conoscere per risolvere la maggior parte dei problemi di algoritmi?

Se vuoi algoritmi specifici, la mia top 10 sarebbe:

• Dijkstra's - a seconda del tipo di gara, potresti vedere problemi di pathfinding di base, o potresti vedere problemi con riduzioni non ovvie a problemi di pathfinding. Ogni volta che avete un problema di minimizzazione dei costi con un (ragionevolmente piccolo) numero finito di stati, uno stato iniziale e uno stato di destinazione, potete vederlo come un problema di pathfinding.
• Bellman-Ford è utile per il pathfinding quando i bordi possono avere costi negativi. Per esempio se state navigando in un labirinto con pozioni che aumentano la salute e pericoli che la abbassano, Bellman-Ford sarebbe un ottimo approccio.
• Floyd-Warshall è utile per calcolare tutti i percorsi. A volte è usato in problemi dove non c'è bisogno di tutti i percorsi, perché è così facile da implementare. Tuttavia è più lento di altri algoritmi di pathfinding, quindi se Floyd-Warshall è un'opzione dipende dalla dimensione del grafico.
• Edmonds-Karp per problemi di max flow/min cut. Un'applicazione comune è il problema della corrispondenza bipartita. Per esempio, date N persone, M prodotti alimentari, e una lista di allergie alimentari di ogni persona, quante persone si possono sfamare?
• L'algoritmo ungherese per problemi di assegnazione. Simile al precedente, ma in questi problemi i bordi hanno dei pesi, e noi stiamo massimizzando il peso totale piuttosto che solo il numero di corrispondenze.
• L'algoritmo "sweep line" (più che altro un approccio generale) è utile per vari problemi geometrici, come il problema della coppia più vicina. Utile anche per una varietà di problemi legati all'intersezione, come trovare segmenti di linea che si intersecano, o eventi di calendario in conflitto.
• Graham scan o un altro algoritmo di convex hull, per problemi come la costruzione di un recinto minimo per racchiudere gli animali.
• Un algoritmo per trovare componenti fortemente connessi, come Tarjan's.
• Algoritmo di Prim per gli alberi a scansione minima.
• Algoritmo Knuth-Morris-Pratt per la ricerca di stringhe.

Altri concetti che vale la pena studiare, che non sono nella lista precedente perché non sono algoritmi specifici:

• La memorizzazione/programmazione dinamica è abbastanza utile. Alcuni problemi hanno soluzioni DP ovvie, mentre altri hanno soluzioni molto non ovvie che richiedono pratica per essere riconosciute.
• La ricerca binaria è utile in molti problemi di ottimizzazione, quindi assicuratevi di essere a vostro agio nell'implementarla.
• La teoria dei giochi combinatoriale viene fuori ogni tanto. I recommend Thomas Ferguson's introduction.
• Tries are useful in a variety of text-related problems.