algoritmos para la resolución de problemas NP

Vista previa del material en texto

Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
algoritmos para la resolución de problemas NP-
completos 
Los problemas NP-completos son un tipo de problema 
computacional que es difícil de resolver, incluso para los 
ordenadores más potentes. Estos problemas se 
caracterizan por tener una función objetivo que se 
desea minimizar o maximizar, y un conjunto de 
restricciones que deben cumplirse. 
¿Qué es un problema NP-completo? 
Un problema NP-completo es un problema 
computacional que tiene las siguientes propiedades: 
• Es un problema de decisión, es decir, la solución 
se puede expresar como un sí o un no. 
• Es un problema NP-duro, es decir, no existe un 
algoritmo polinomial que pueda resolverlo. 
• Es un problema NP-completo, es decir, cualquier 
problema NP-duro puede reducirse a él. 
¿Cómo se resuelven los problemas NP-completos? 
Los problemas NP-completos no tienen una solución 
general, es decir, no existe un algoritmo que pueda 
resolverlos todos. Sin embargo, existen algoritmos 
específicos que pueden resolver algunos problemas 
NP-completos. 
Ejemplos de problemas NP-completos 
Algunos ejemplos de problemas NP-completos son: 
• El problema del viajante de comercio: encontrar 
el camino más corto que visita todas las 
ciudades de un conjunto dado. 
• El problema del coloreado de grafos: encontrar 
una asignación de colores a los vértices de un 
grafo de manera que no haya dos vértices 
adyacentes con el mismo color. 
• El problema del reparto de mochila: encontrar la 
combinación de elementos que se puede meter 
en una mochila de tamaño limitado de manera 
que el valor total 
de los elementos 
sea lo mayor 
posible. 
Algoritmos para la 
resolución de problemas 
NP-completos 
Existen varios 
algoritmos que se 
pueden utilizar para 
resolver problemas NP-
completos. Algunos de 
estos algoritmos son: 
• Algoritmos 
heurísticos: Estos 
algoritmos no 
garantizan 
encontrar la 
solución óptima, 
pero suelen 
encontrar una 
solución buena 
en un tiempo 
razonable. 
• Algoritmos 
aproximados: Est
os algoritmos 
proporcionan una 
solución que no 
es 
necesariamente 
óptima, pero se 
garantiza que no 
está lejos de la 
solución óptima. 
• Algoritmos 
probabilísticos: E
stos algoritmos 
utilizan el azar 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
para encontrar una solución. 
Conclusión 
Los problemas NP-completos son un desafío importante 
para la informática. La resolución de estos problemas 
tendría un impacto significativo en una amplia gama de 
áreas, como la ingeniería, la ciencia y los negocios. 
Ideas principales para estudiantes de universidad 
• Los problemas NP-completos son un tipo de 
problema computacional que es difícil de 
resolver. 
• Los problemas NP-completos no tienen una 
solución general, pero existen algoritmos 
específicos que pueden resolver algunos de 
ellos. 
• Algunos ejemplos de problemas NP-completos 
son el problema del viajante de comercio, el 
problema del coloreado de grafos y el problema 
del reparto de mochila. 
• Existen varios algoritmos que se pueden utilizar 
para resolver problemas NP-completos, como los 
algoritmos heurísticos, los algoritmos 
aproximados y los algoritmos probabilísticos.