En general, no debe intentar resolver un problema de NP completo en tiempo polinómico. Ese es un esfuerzo engañado. El problema es intratable.
Sin embargo, hay formas de manejar la intratabilidad. Puede intentar resolver un caso especial o escribir un algoritmo de aproximación o un algoritmo probabilístico. Puede intentar utilizar formas alternativas de computación como simulaciones biológicas o una computadora cuántica. Puede diseñar un algoritmo intuitivo que es exponencial en teoría pero que puede comportarse eficientemente en la práctica con datos reales. Y puede escribir algoritmos heurísticos que no tienen por qué ser correctos pero que a veces lo sorprenden.
Necesita conocer una cantidad justa para seguir mis sugerencias anteriores.
- ¿Las computadoras actuales funcionan bien para la capacitación de aprendizaje profundo?
- ¿Utiliza Windows y prácticamente arranca Linux o al revés?
- ¿Cómo es tomar CS 246 en Stanford?
- ¿Son las habilidades teóricas más valiosas que las habilidades de implementación en EE o CS en general?
- ¿Hay algún empleado anterior de Satyam Computers en Quora? ¿Cómo fue trabajar con Satyam Computers?
- Toda la complejidad resulta sobre el problema en cuestión, incluidos casos especiales: por ejemplo, para un problema gráfico: tipos restringidos de gráficos: DAG, árboles, bipartitos, limitados por grados, intervalos, cordales, etc.
- Teoría básica de la complejidad y teoría de la probabilidad.
- Estructuras de datos y cómo programar eficientemente con ellos, utilizando la recursividad, la estrategia codiciosa o la programación dinámica.
- Cosas interesantes como la computación cuántica o la computación de ADN.
- AI: programación heurística.