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 (n-1) 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 j entón procuramos a posición de inserción i e j de ciclo que minimiza o incremento total dos custos:

* na *inserción máis afastada* j é o vértice libre máis afastado do ciclo no sentido de custo;
* na *inserción máis próxima* j é o máis próximo ao ciclo;
* finalmente na *mellor inserción'' probamos todos os vértices j 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 x/y, realizando repetidamente a substitución
\frac{x}{y}=\frac{1}{\lceil \frac y x \rceil}+\frac{(-y)\bmod x}{y \lceil \frac y x  \rceil}
(simplificando o segundo termo desta substitución se é necesario). Por exemplo:
\frac{7}{15}=\frac{1}{3}+\frac{2}{15}=\frac{1}{3}+\frac{1}{8} +\frac{1}{120}.

## 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