Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter
Más allá de los matroides…
25 febrero 2015 por Javier Campos en cosas de clase,curiosidades

.

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 Wikipediaen 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…

 

Comentarios