¿Cuándo es conveniente resolver un problema usando un algoritmo codicioso?

Algo que muchos informáticos no parecen saber [*] es que en realidad hay una pequeña y hermosa pieza de matemática llamada teoría matroide . Un matroide es una estructura algebraica con la siguiente propiedad sorprendente: el algoritmo codicioso funciona en un problema si el problema puede representarse como un matroide. Por lo tanto, al menos en principio, dado un problema, intente caracterizarlo como un matroide y, si tiene éxito, use el algoritmo codicioso. Bueno, en teoria. (-:

En la práctica, sin embargo, el algoritmo codicioso es más útil que eso. A menudo está bien usar un enfoque codicioso. De hecho, hay muchos problemas en los que sabemos tanto que el algoritmo codicioso no es óptimo, sino también que el enfoque codicioso está fuera de la solución óptima por algún límite bastante razonable. En tales casos, probablemente no valga la pena esforzarse más hasta que se demuestre que es el mayor cuello de botella en un sistema (y a menudo no lo es: algo más tiene que ver con los sistemas o el software).

[*] Tuve la suerte de aprender sobre este tema de un ingeniero tan obsesionado con él que escribió un libro completo sobre él: András Recski [Teoría de Matroid y sus aplicaciones en la teoría de redes eléctricas | Andras Recski | Saltador].

Cuando puedas.

Cualquier cosa que se pueda resolver de manera eficiente con un algoritmo codicioso es probable que se resuelva más convenientemente con dicho algoritmo. La razón por la que no usaría un algoritmo codicioso es que no puede hacerlo: es demasiado lento o no funciona en absoluto.

Si está escribiendo un código que permite a las personas navegar desde el punto A al punto B en un mapa como Google Maps o Waze o no, no usaría un algoritmo codicioso, porque no puede. Su objetivo es dar a las personas una ruta corta razonable y eficiente, idealmente, la más corta. Un algoritmo codicioso sería un fracaso miserable.

Haría algo como: en cada intersección, elija la dirección más cercana a la línea recta desde donde se encuentra ahora hasta la meta B. Dos calles adentro, puede llegar a un callejón sin salida. ¿Ahora que? Ok, le enseñas a dar marcha atrás (ahora, estrictamente hablando, ya no es codicioso, pero no importa). Retrocede, encuentra otra intersección y una vez más elige la dirección codiciosa para continuar. Puede quedar atrapado en un laberinto sin fin de calles irrelevantes. Extrañará totalmente la carretera. Te apestará terriblemente, terriblemente.

Así que no usarías un algoritmo codicioso, aunque usarlo hubiera sido muy conveniente: es estúpidamente simple de codificar. Aún así, no puedes usarlo.

Por otro lado, si necesita encontrar un árbol de expansión mínimo de algún gráfico ponderado por el borde (porque está haciendo algún tipo de agrupación simple o reconocimiento de escritura a mano, o lo que sea), con gusto usaría el algoritmo de Kruskal [1] que es, como, totalmente codicioso. Funciona perfectamente y es la opción más conveniente, así que anímate.

Notas al pie

[1] Algoritmo de Kruskal – Wikipedia

Cuando la función que está optimizando es monótona y submodular.

Para funciones submodulares, un algoritmo codicioso produce una solución que en el peor de los casos es el 63% de la solución óptima.

Podemos definir una función submodular de una manera no matemática diciendo que f es submodular si agregar un elemento a un conjunto proporciona una mejora menor que agregarlo a un subconjunto.

La submodularidad es la versión discreta de la concavidad.

Por ejemplo, considere esta versión del problema de cobertura máxima.

Tenemos un conjunto de documentos, cada documento puede pertenecer a varios temas. Nos gustaría elegir documentos “k”, ya que cubren la más amplia gama de temas. Este es un problema NP-completo bien conocido, por lo que no hay una solución exacta en el tiempo polinomial, por lo tanto, una heurística puede ser útil.

Está claro que la función es monótona, ya que al agregar más documentos, la cubierta solo puede aumentar. Para verificar la submodularidad, tenemos que analizar qué sucede si tenemos un conjunto de documentos (A, B, C, D, E) y agregamos un nuevo documento “F” en comparación con lo que sucede si agregamos “F” a un subconjunto decir (A, B, C, D).

En el caso de A, B, C, D tenemos algunos temas cubiertos, por ejemplo, t1 y después de agregar f tendremos t2 con t2> = t1. La ganancia se puede definir como t2-t1.

Si agregamos el documento F a A, B, C, D, E, nunca podremos tener una ganancia mayor. Si “E” no cubre ningún tema nuevo, entonces agregar F a A, B, C, D, E es lo mismo que agregarlo a A, B, C, D y si E cubre algún tema nuevo, entonces agregar F a A , B, C, D, E nunca pueden resultar en una ganancia mayor que sumarla a A, B, C, D. Esto es bastante obvio, pero siempre es bueno revisarlo para comprender qué es la submodularidad.

Una vez que esté seguro de que tiene una función submodular que desea optimizar, una heurística codiciosa le dará una solución bastante buena con el límite mencionado.