Algoritmos

algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP-hard; como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-hard, se opta por encontrar soluciones no-óptimas en tiempo polinomial. A diferencia de las heurísticas, que usualmente sólo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca aquí es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotadas por cotas conocidas. Idealmente, la aproximación mejora su calidad para factores constantes pequeños (por ejemplo, dentro del 5% de la solución óptima). Los algoritmos de aproximación están siendo cada vez más utilizados para resolver problemas donde los algoritmos exactos de tiempo polinomial son conocidos pero demasiado costosos debido al tamaño de la entrada.- ...................................................................:https://es.wikipedia.org/w/index.php?title=Algoritmo_de_aproximaci%C3%B3n&printable=yes