TSP: Dado un gráfico ponderado dirigido, ¿hay alguna manera de visitar todos los vértices en el gráfico EXACTAMENTE una vez? Este es el problema de decisión. Si la respuesta es SÍ, ¿cuál es el costo mínimo de tal recorrido? Este es un problema de optimización.
Se ha demostrado que ambos son “duros”. Es decir, la solución de tiempo polinomial para ellos probablemente no existe (noboby lo sabe).
MST: Dado un gráfico ponderado conectado, encuentre el árbol de expansión de manera que el costo total de todos los bordes en el árbol de expansión sea lo más pequeño posible. Si el gráfico está conectado, puede decir CON SEGURIDAD que existe un árbol de expansión. Hay algoritmos eficientes como Prim, Kruskal, por nombrar algunos para encontrar MST.
- Cómo escribir un algoritmo que diseña guiones
- ¿Por qué los desarrolladores front-end necesitan conocer estructuras de datos y algoritmos?
- ¿Cómo podemos demostrar que el reconocimiento de objetos basado en la visión es un problema np completo?
- ¿Qué es un algoritmo explicado para que las personas normales puedan entender y también cómo se hacen?
- Cómo identificar la recursividad en un problema de programación
El árbol de expansión no necesita ser el camino. Puede tener ramas.
Nota: existen definiciones técnicas para duro, eficiente, etc.