Wikipedia tiene un buen artículo sobre problemas de NP-Complete, que proporciona una lista de ellos indexados por su área. Puede verificarlo aquí: Lista de problemas NP-completos
Si desea una sugerencia de un problema de gráfico NP-Complete particular, puede consultar la formulación del problema de decisión Euclidiana 2D del problema del vendedor ambulante. Este es el problema de decidir, para un conjunto dado de puntos en un espacio bidimensional y una constante K, si existe una ruta que visite cada punto exactamente una vez cuya longitud sea más corta que K.
Este problema es una elección interesante, ya que TSP y sus variaciones son algunos de los problemas más estudiados en optimización y la literatura es rica en heurística para encontrar soluciones de buena calidad para ellos. Debido a que TSP es un problema tan popular, también puede beneficiarse de sitios web como TSPLIB, que proporcionan miles de instancias de TSP que puede usar para probar sus algoritmos.
- ¿Qué tan bueno es Ingeniería Física, especialmente en IIT Hyderabad?
- ¿Es posible evitar Fortinet?
- ¿Cuáles son algunos de los problemas NP-Complete más notables?
- ¿Cuáles son las puertas lógicas más comunes en las computadoras?
- ¿Qué tan bueno es Apple en informática distribuida?
OBS Observe que sugerí la versión de decisión del problema, ya que NP-Complete es una clase de complejidad definida solo para problemas de decisión, y TSP es de optimización. Sin embargo, es posible que su maestro esté acuñando “NP-Complete” de una manera menos rigurosa y solo quiera que proporcione una heurística a cualquier problema cuya versión de decisión sea NP-Complete. Deberías verificar esto con ellos.
