Como sabrán, se muestra que la cobertura mínima del conjunto es NP-completa. Problemas como este generalmente se resuelven mediante algoritmos de aproximación o métodos heurísticos, porque es un compromiso razonable que no requerirá demasiado tiempo.
Como algoritmo de aproximación, el algoritmo codicioso puede no encontrar la solución óptima globalmente, sino probablemente una solución óptima localmente, siempre que el conjunto de subconjuntos de entrada tenga un subconjunto, cuya unión cubrirá el conjunto universal.
Veamos los pasos del algoritmo codicioso:
- Cómo garantizar un resultado devuelto de la función que llamamos (en sí mismo) es correcto en la recursividad
- ¿Cuál es el valor de la suma k ^ 2 * C (n, k) 0 a n?
- ¿Cómo se escriben los algoritmos de espacio?
- ¿Cuáles son los mejores algoritmos híbridos para el filtrado colaborativo y basado en contenido?
- ¿Podemos, y qué significa, 'crear algoritmos sin codificación'?
- Si el subconjunto resultante está vacío, coloque el subconjunto más grande en él;
- De lo contrario, busque un subconjunto con el mayor número de elementos que no están en el subconjunto resultante;
- Repita hasta que la unión del conjunto resultante cubra el conjunto universal.
Si ejecuta este algoritmo manualmente en varias entradas, es intuitivo que eventualmente resolverá la cobertura mínima establecida, pero la solución que encontrará no siempre será óptima.
