.

Hemos visto en clase que algunos problemas poseen la estructura algebraica subyacente de matroide y en ese caso pueden resolverse correctamente con un algoritmo voraz.

Existe una extensión del concepto de matroide que permite llegar un poco más lejos, para resolver más problemas con algoritmos voraces: se trata de los gridoides. En Wikipedia o en este informe (acceso con clave) se explica qué son.

Pero tampoco los gridoides caracterizan exactamente todos los problemas que pueden resolverse con un algoritmo voraz.

Hay trabajos posteriores que llegan más allá. Por ejemplo, en el trabajo “An Exact Characterization of Greedy Structures“ (acceso con clave), sus autores, Paul Helman, Bernard M.E. Moret y Henry D. Shapiro, presentan una caracterización para una estructura de problemas para los que un algoritmo voraz calcula una solución óptima.

Y la investigación continúa…