Quais são os 10 algoritmos que se deve saber para resolver a maioria dos problemas de algoritmos?

Se você quiser algoritmos específicos, meus 10 principais seriam:

• Dijkstra's - dependendo do tipo de concurso, você pode ver problemas básicos de pathfinding, ou você pode ver problemas com reduções não óbvias de problemas de pathfinding. Sempre que você tiver um problema de minimização de custos com um número finito de estados (razoavelmente pequeno), um estado inicial e um estado alvo, você pode olhar para ele como um problema de pathfinding.
• Bellman-Ford é útil para pathfinding quando bordas podem ter custos negativos. Por exemplo, se você're navegar num labirinto com poções que aumentam a saúde e perigos que a reduzem, Bellman-Ford seria uma ótima abordagem.
• Floyd-Warshall é útil para o cálculo de todos os caminhos. É às vezes usado em problemas onde você não'não precisa de todos os caminhos, porque ele'é tão fácil de implementar. É mais lento que outros algoritmos de busca de caminhos, então se Floyd-Warshall é uma opção depende do tamanho do gráfico.
• Edmonds-Karp para problemas de fluxo máximo/minuto de corte. Uma aplicação comum são os problemas de correspondência bipartida. Por exemplo, dado N pessoas, M itens alimentares, e uma lista de cada pessoa's alergias alimentares, quantas pessoas você pode alimentar?
• O algoritmo húngaro para problemas de atribuição. Similar ao acima, mas nestes problemas as bordas têm pesos, e nós're maximizando o peso total ao invés de apenas o número de correspondências.
• O "algoritmo" da linha de varredura (mais de uma abordagem geral realmente) é útil para vários problemas geométricos, como o problema do par mais próximo. Também é útil para uma variedade de problemas relacionados à intersecção, como encontrar segmentos de linha de intersecção, ou eventos de calendário conflitantes.
• Graham scan ou outro algoritmo de casco convexo, para problemas como construir uma cerca mínima para cercar animais.
• Um algoritmo para encontrar componentes fortemente conectados, como Tarjan's.
• algoritmo para árvores de spanning mínimo.
• algoritmo de Knuth-Morris-Pratt para busca de strings.

p>Outros conceitos que vale a pena estudar, que estão't na lista acima porque são't algoritmos específicos:

• >li>Memoization/dynamic programming is quite useful. Alguns problemas têm soluções DP óbvias, enquanto outros têm soluções muito pouco óbvias que levam a prática a reconhecer.
• A pesquisa binária é útil em muitos problemas de otimização, então certifique-se de que você'está muito confortável implementando-o.
• Teoria de jogo comboinatorial vem à tona de vez em quando. I recommend Thomas Ferguson's introduction.
• Tries are useful in a variety of text-related problems.