Algoritmo cobizoso

Un algoritmo cobizoso (greedy algorithm 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.

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 de un 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}}.$

Notas

Véxase tamén

Bibliografía

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "16 Greedy Algorithms". Introduction To Algorithms. MIT Press. pp. 370–. ISBN 978-0-262-03293-3.
Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP". Discrete Applied Mathematics 117 (1–3): 81–86. doi:10.1016/S0166-218X(01)00195-0.
Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004). "When the greedy algorithm fails". Discrete Optimization 1 (2): 121–127. doi:10.1016/j.disopt.2004.03.007.
Bendall, Gareth; Margot, François (2006). "Greedy-type resistance of combinatorial problems". Discrete Optimization 3 (4): 288–298. doi:10.1016/j.disopt.2006.03.001.
Feige, U. (1998). "A threshold of ln n for approximating set cover" (PDF). Journal of the ACM 45 (4): 634–652. doi:10.1145/285055.285059. Arquivado dende o orixinal (PDF) o 2022-10-09.
Nemhauser, G.; Wolsey, L.A.; Fisher, M.L. (1978). "An analysis of approximations for maximizing submodular set functions—I". Mathematical Programming 14 (1): 265–294. doi:10.1007/BF01588971.
Buchbinder, Niv; Feldman, Moran; Naor, Joseph (Seffi); Schwartz, Roy (2014). "Submodular maximization with cardinality constraints" (PDF). Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics. ISBN 978-1-61197-340-2. doi:10.1137/1.9781611973402.106. Arquivado dende o orixinal (PDF) o 2022-10-09.
Krause, A.; Golovin, D. (2014). "Submodular Function Maximization". En Bordeaux, L.; Hamadi, Y.; Kohli, P. Tractability: Practical Approaches to Hard Problems. Cambridge University Press. pp. 71–104. ISBN 9781139177801. doi:10.1017/CBO9781139177801.004.
Papadimitriou, Christos H.; Steiglitz, Kenneth (1998). Combinatorial Optimization: Algorithms and Complexity. Dover.

Outros artigos

Ligazóns externas

Portage de l'algorithme de coloration en C