Algoritmo cobizoso

Un algoritmo cobizoso ( en inglés), é un algoritmo que segue o principio de facer, paso a paso, unha elección óptima local, co fin de obter un resultado global óptimo.

Por exemplo, no problema de dar troco (dar unha cantidade co menor número de moedas posíbel), o algoritmo consistente en repetir a elección da moeda de maior valor que non supere a suma restante é un algoritmo cobizoso. Nos casos en que o algoritmo non proporciona de forma consistente a solución óptima, chámase heurística cobizosa. A ilustración  mostra un caso no que este principio non acha a solución correcta.
dereita|miniatura|250x250px| Partindo do punto A e tratando de subir pola pendente máis pronunciada, un algoritmo cobizoso atopará o máximo local m, mais non o máximo global M.

 Problemas de exemplo 

 Troco 
Dependendo do sistema de moedas, o algoritmo cobizoso é óptimo ou non. No sistema europeo de moedas (en céntimos : 1, 2, 5, 10, 20, 50, 100, 200), onde o algoritmo cobizoso dá a seguinte suma para 37 : 20+10+5+2, podemos demostrar que o algoritmo cobizoso sempre dá unha solución óptima.

No sistema de moedas (1, 3, 4), o algoritmo cobizoso non é óptimo, como mostra o seguinte exemplo sinxelo. Dá para o troco de 6 : 4+1+1, mentres que 3+3 é o óptimo.

 Árbore de expansión mínima 
O problema consiste, nun grafo non dirixido conexo e ponderado, en atopar un subconxunto de arestas, formando unha árbore, incluíndo todos os vértices, de forma que a suma dos pesos de cada aresta sexa mínima.

Tanto os algoritmos de Prim como de Kruskal son algoritmos cobizosos. O primeiro consiste en escoller arbitrariamente un vértice e facer medrar unha árbore a partir dese vértice. O segundo consiste en facer medrar un bosque para unha cobertura completa. Cada aumento realízase da forma máis económica posíbel.

 Viaxeiro comercial 
Unha heurística cobizosa constrúe unha única solución, mediante unha serie de decisións definitivas sen retroceder, entre estes métodos citamos o veciño máis próximo, a inserción máis próxima, a inserción máis afastada e a mellor inserción.

No método do veciño máis próximo, partimos de calquera vértice e en cada unha das  iteracións ligamos o último vértice alcanzado co vértice máis próximo no sentido de custo, despois ligamos finalmente o último vértice co primeiro vértice escollido.

Nos métodos de inserción, partimos dun ciclo reducido dun bucle no comezo, en cada iteración escollemos un vértice libre  entón procuramos a posición de inserción  e  de ciclo que minimiza o incremento total dos custos:

 na inserción máis afastada  é o vértice libre máis afastado do ciclo no sentido de custo;
 na inserción máis próxima  é o máis próximo ao ciclo;
 finalmente na mellor inserción probamos todos os vértices  aínda non inseridos e escollemos o que dea menor incremento de custo.

 Coloración de grafos 
Por exemplo, o seguinte algoritmo propón unha cor que será válida, mais non necesariamente óptima e, polo tanto, é só unha heurística. O problema de coloración dun grafo é NP-completo e, polo de agora, para tratar o caso xeral, só hai heurísticas ou aproximacións polinómicas, ou algoritmos polinómicos nalgúns casos especiais.
 Cobizoso:
   Entrada: lista ordenada V dos n vértices dun grafo G
        lista ordenada C de cores

   Para i de 1 a n
    v = V[i]
    cor = a primeira cor de C que non usan os veciños de v
    cor (v, cor)
   Fin do para
Algoritmo cobizoso para fraccións exipcias 
Este algoritmo cobizoso serve para transformar números racionais en fraccións exipcias. Unha fracción exipcia é unha representación dunha fracción irredutíbel como unha suma de fraccións unitarias distintas.

Chámase algoritmo cobizoso porque en cada paso o algoritmo elixe cobizosamente a fracción unitaria máis grande posible que se pode usar en calquera representación da fracción restante.

Expande a fracción , realizando repetidamente a substitución

(simplificando o segundo termo desta substitución se é necesario). Por exemplo:

 Véxase tamén 

 Bibliografía 


 Outros artigos 
 algoritmo cobizoso para fraccións exipcias
 Algoritmo de Kruskal
 Algoritmo de Prim
 Algoritmo de Dijkstra
 Problema do viaxante
 Ligazóns externas 
 Portage de l'algorithme de coloration en C

Categoría:Algoritmos