Programación General > C/C++
Re: problema de la mochila
De Profundiis:
Por cierto, dije que yo tenía una solución algorítmica. Tengo que aclarar que mi solución no es una solución correcta del todo. Me explico:
El algoritmo que tengo tiene un coste lineal, pero a cambio de esto, no siempre da el mejor resultado para algunos casos, sino que da una soúción aproximadamente óptima. A veces es mejor una solución casi correcta y rápida, que una solución correcta, pero muy lenta. Nada más.
Saludos.
Murciego:
Hola.
Yo soy el matemático de computación.
Efectivamente, el problema de la mochilla fraccionada se puede resolver mediante una algoritmo voraz, y la solución dada es la exacta.
Para el problema de la mochila no fraccionada nosotros usabamos algoritmos de programación dinámica, y de exploración del arbol de soluciónes con ramificación y acotacion (usando el problema de la mochila fraccionada) y el ramificación y poda.
No recuerdo si el problema era NP-completo. Lo que si esta claro es que es NP, puesto que una máquina con oraculo lo resuelve en tiempo polinomial.
Para informarte sobre el tema puedes mirar el libro G.Brassard- P.Bratley "Algoritmica, Concepcion y Analisis" Ed. Masson
Por cierto, el problema de cortar tablas que sugerí para un reto, y que nadie lo ha resuelto aun, creo que también es NP-completo, aunque estuve casi un més intentando resolverlo y no fui capaz (y la profesora que me daba Calculabilidad tampoco).
Un saludo
De Profundiis:
Hola Murciego,
gracias por tu respuesta. Conozco el libro de Brassard y Bratley (ya es un clásico:D junto al Cormen) he estado pensando en comprármelo, quizás lo haga. Con respecto a tu problema de las tablas, ya estuve pensando que sería NP-completo, pero no estaba seguro:P. El caso es que no domino de la teoría de la complejidad, pero algo sé.
Me gustaría si es posible que comentásemos abiertamente en el foro algo de esto, pero podríamos hacerlo en el foro de Algoritmos. En primer lugar me gustaría, si no te importa, que me explicases la diferencia entre un problema de la familia NP y la familia NP-completa (pensaba que eran lo mismo:().
Bueno, ya irán surgiendo cosas.
Un saludo.
Murciego:
Un problema se dice que pertenece a la clase NP si existe una máquina de Turing NO determinista que lo resuelve en tiempo polinomial.
Un problema se dice DURO para una clase si cualquier problema de esa clase se puede "tranformar" a el en tiempo Polinomial. En particular, un problema es NP-DURO si cualquier problema NP se puede reducir a el en tiempo polinomial (o lo que es equivalente, es espacio logaritmico)
Un problema es NP-completo si es NP y además es NP-DURO, o sea, DURO para la clase NP.
Es facil ver, que cualquier problema P es NP, y que cualquier problema NP es EXP (resolubles por una máquina determinista en tiempo exponencial).
También se sabe que P es distinto de EXP.
Entonces tenemos la siguiente cadena de desigualdades:
P contenido en NP contenido en EXP y P distinto de EXP
Entonces P es distinto de EXP o de P o de ambos (existen muchas clases de complejidad intermedia). La duda es: En esa cadena,¿en que punto de da la desigualdad extricta?
Bueno, no me enrollo más. Si quieres hablar más de este tema no dudes en decirmelo.
Un saludo
De Profundiis:
Gracias por la explicación, no tengo mucho tiempo ahora, pero ten por seguro que cuando esté más desahogado trataré de plantear algunas otras dudas que me quedan, aunque quizás lo haga en el foro "Diseño de Algoritmos" porque me parece que esto ya no es C. Jejeje.
Un saludo.
Navegación
[*] Página Anterior
Ir a la versión completa