Hay muchos problemas de optimización [matemática] \ matemática {NP} [/ matemática] que son factibles en el sentido de que podemos proporcionar soluciones de buena calidad o incluso óptimas a un gran número de sus instancias en un tiempo computacional decente. Los métodos de metaheurística y búsqueda heurística en general hacen un buen trabajo al proporcionar soluciones prácticas a instancias del mundo real. También hay una serie de algoritmos de aproximación de tiempo polinómico que generan soluciones cuyo valor está garantizado dentro de una desviación conocida de la solución óptima (como en el caso de la mejor estrategia de reducción de ajuste para el Problema de Empaque de Contenedores, cuyas soluciones están probadas para no exceda [matemática] 11/9 [/ matemática] del valor óptimo). Estos resultados son generalmente satisfactorios porque, para fines prácticos, las soluciones cercanas al óptimo son más que suficientes.
Los problemas de decisión son otra historia. Una cosa es encontrar una ruta para el problema del vendedor ambulante que es [matemática] 1 \% [/ matemática] más larga que la óptima, pero es otra cosa deducir erróneamente que una fórmula 3-CNF no es satisfactoria. Esta estructura binaria, “todo o nada” de problemas de decisión puede complicar mucho las cosas.
De hecho, hay muchas veces en las que la metaheurística puede encontrar soluciones óptimas a los problemas de optimización [matemática] \ matemática {NP} [/ matemática], pero se dejan funcionando durante mucho más tiempo del necesario solo porque no pueden demostrar que La solución es óptima. Lo mismo se aplica a las técnicas de ramificación y unión, que a menudo encuentran la solución óptima muy pronto, pero no pueden demostrar su optimización hasta mucho más tarde. Esto ejemplifica el hecho de que querer probar cosas generalmente perjudica la viabilidad más que solo querer una solución que sea lo suficientemente buena.
- En las estructuras de datos, ¿cuál puede ser un ejemplo general utilizado para explicar el peor de los casos, los tiempos de ejecución amortizados y esperados?
- ¿Por qué es importante almacenar y organizar datos de manera eficiente dentro de estructuras específicas al programar?
- ¿Cómo abordar este problema gráfico? ¿Es NP-completo?
- ¿El hashing criptográfico es una buena manera de identificar imágenes de forma exclusiva?
- ¿Quién sabe qué hay detrás de la API de Google Nearby Search? ¿Qué algoritmo usan? ¿Cómo encuentra Google una estación de servicio cercana?
