Python - classes de algoritmo

Algoritmos são etapas inequívocas que devem nos dar uma saída bem definida pelo processamento de zero ou mais entradas. Isso leva a muitas abordagens para projetar e escrever os algoritmos. Foi observado que a maioria dos algoritmos pode ser classificada nas seguintes categorias.

Algoritmos gananciosos

Algoritmos gananciosos tentam encontrar uma solução ótima localizada, o que pode levar a soluções globalmente otimizadas. No entanto, algoritmos geralmente gananciosos não fornecem soluções otimizadas globalmente.

Algoritmos gananciosos procuram uma solução fácil naquele momento, sem considerar como isso afeta as etapas futuras. É semelhante a como os humanos resolvem problemas sem passar pelos detalhes completos das entradas fornecidas.

A maioria dos algoritmos de rede usa a abordagem gananciosa. Aqui está uma lista de alguns deles -

  • Problema do caixeiro viajante
  • Algoritmo de árvore de expansão mínima de Prim
  • Algoritmo de árvore de expansão mínima de Kruskal
  • Algoritmo de árvore de expansão mínima de Dijkstra

Dividir e conquistar

Essa classe de algoritmos envolve a divisão de um determinado problema em subproblemas menores e, em seguida, a resolução de cada um dos subproblemas de forma independente. Quando o problema não pode ser subdividido, começamos a mesclar a solução para cada um dos subproblemas para chegar à solução para o problema maior.

Os exemplos importantes de algoritmos de divisão e conquista são -

  • Mesclar Classificar
  • Ordenação rápida
  • Algoritmo de árvore de expansão mínima de Kruskal
  • Pesquisa Binária

Programaçao dinamica

A programação dinâmica envolve dividir o problema maior em outros menores, mas ao contrário de dividir e conquistar, não envolve resolver cada subproblema independentemente. Em vez disso, os resultados de subproblemas menores são lembrados e usados ​​para subproblemas semelhantes ou sobrepostos. Principalmente, esses algoritmos são usados ​​para otimização. Antes de resolver o subproblema em mãos, o algoritmo dinâmico tentará examinar os resultados dos subproblemas resolvidos anteriormente.

algoritmos dinâmicos são motivados para uma otimização geral do problema e não a otimização local.

Os exemplos importantes de algoritmos de programação dinâmica são -

  • Série de números de Fibonacci
  • Problema de mochila
  • Torre de Hanói