Foros de SóloIngeniería

- 10 Dic 2008, 08:09 #132787

Hola, me he quedado flipado, ¿sabéis por qué? Porque no hace mucho en la asignatura "Estructura de Datos y Algoritmos", al final del tema "Ánalisis de algoritmos iterativos" el profesor nos habló de este tipo de problemas. Por lo visto hay tres grados: clase P (polinómicos), NP (no deterministas polinómicos) y NP Completos. Los dos tipos de problemas primeros tienen soluciones, pero para el último se especula que no tienen solución, aunque no se ha demostrado lo contrario; es más, hay reservado un gran premio a quien consiga realizar uno

Ponnos el enunciado que en los ratos libres sacamos la solucion de los problemas que dicen no tener solucion.

• 
• 
• 
• 
• 
• 

*5 por el culo te la hinco...
*UNA MUJER ME ARRASTRÓ A LA BEBIDA... Y NUNCA TUVE LA CORTESÍA DE DARLE LAS GRACIAS.

- 10 Dic 2008, 22:45 #132998

Jajajaaja... ni siquiera nos puso un enunciado tipo, sólo nos dijo que a quien los resolviera (NP-Completos) se le daría un premio equivalente al Nobel! Así que ya os podéis imaginar

• 
• 
• 
• 
• 
• 

- 11 Dic 2008, 03:57 #133016

Jajajaaja... ni siquiera nos puso un enunciado tipo, sólo nos dijo que a quien los resolviera (NP-Completos) se le daría un premio equivalente al Nobel! Así que ya os podéis imaginar

todos estos problemas si tienen solucion, el problema es crear un algoritmo que resuelva el problema en un tiempo razonable, porque si te pones a probar todas las posibilidades el tiempo de resolucion es funcion de las posibilidades generalmente (N-1)! dependiendo de la naturaleza y eso es aproximadamente para este caso 2^X cn X>100

lo que sifnigica que el tiempo en segundos es mayor a la edad del universo, por lo tanto probar no es una buena idea

es aqui donde entra la heuristica y la metaheuristica la cual, funciona con probabilidades y variables aleatorias, es decir, no es necesario probar todas las posibilidades, la solucion converge a un valor optimo local que no necesariamente es el optimo global.

He encontrado un documento muy bueno publicado por la universidad de sevilla, el cual me ha servido mucho para resolver esto

aun falta un poco, cuando tenga el codigo completo, lo dejare como libre distribucion si alguien lo quiere, ademas formara parte del concurso nacional de investigacion de operaciones de Chile, que el cual este año tenemos que ganas

nos vemos, saludos

• 
• 
• 
• 
• 
• 

Estudiante 5to año Ingenieria Civil Industrial
Universidad de Talca, Chile

- 12 Dic 2008, 10:17 #133261

Gracias por la aclaración elchile. La verdad es que yo no he dicho que no tengan solución (me refería a los NP-Completos), sino que se especula con que no tienen, aunque todavía no se ha demostrado lo contrario...

Un

• 
• 
• 
• 
• 
• 

- 12 Dic 2008, 13:56 #133316

He encontrado un documento muy bueno publicado por la universidad de sevilla, el cual me ha servido mucho para resolver esto

Gracias por el reporte, elchile.
Igual podías dejar un enlace a la página dónde has encontrado ese documento, por si a alguien le interesa.
A mí me vendría muy bien para cuando mi novia me hace según qué preguntas. Me encantaría poder responder con alguna respuesta óptima local, aunque no encuentre la global (porque no la hay)...

Gracias por la aclaración elchile. La verdad es que yo no he dicho que no tengan solución (me refería a los NP-Completos), sino que se especula con que no tienen, aunque todavía no se ha demostrado lo contrario...

Se podria aplicar al caso de las pelusas de polvo y otros restos que se forman en mi casa al cabo del tiempo; no sé de dónde vienen, ni cómo, ni cuándo, pero ahí están, indefectiblemente.
Especulo con que este problema no tiene solución. Y que alguien me demuestre lo contrario.

• 
• 
• 
• 
• 
• 

Para colgar una imagen en un mensaje, pulsa aquí
Para introducir un enlace en un mensaje, pulsa aquí
Si eres nueva en el foro, preséntate aquí. Y págate unas cervezas al hacerlo.

- 15 Dic 2008, 23:43 #133755

Se podria aplicar al caso de las pelusas de polvo y otros restos que se forman en mi casa al cabo del tiempo; no sé de dónde vienen, ni cómo, ni cuándo, pero ahí están, indefectiblemente.
Especulo con que este problema no tiene solución. Y que alguien me demuestre lo contrario.

claro ejemplo de NP-Completo

• 
• 
• 
• 
• 
• 

- 16 Dic 2008, 08:18 #133763

Se podria aplicar al caso de las pelusas de polvo y otros restos que se forman en mi casa al cabo del tiempo; no sé de dónde vienen, ni cómo, ni cuándo, pero ahí están, indefectiblemente.
Especulo con que este problema no tiene solución. Y que alguien me demuestre lo contrario.

Mirate en el ombligo y encontrarás la solución....

• 
• 
• 
• 
• 
• 

"Hazlo, o no lo hagas, pero no lo intentes"
-Yoda -

- 16 Dic 2008, 13:14 #133834

Mirate en el ombligo y encontrarás la solución....

Pues debe ser pequeño ,vamos como una tapa de alcantarilla ( y en movimiento bailón)

• 
• 
• 
• 
• 
• 

- 16 Dic 2008, 17:35 #133887

Igual podías dejar un enlace a la página dónde has encontrado ese documento, por si a alguien le interesa.
A mí me vendría muy bien para cuando mi novia me hace según qué preguntas. Me encantaría poder responder con alguna respuesta óptima local, aunque no encuentre la global (porque no la hay)...

• 
• 
• 
• 
• 
• 

- 27 Ene 2009, 16:18 #139740

BUENO ,MUCHACHOS LO PROMETIDO ES DEUDA


TERMINE EL ALGORITMO HEURISTICO, EL CUAL REALIZE EN LENGUAJE JAVA, USANDO LA BIBLIOTECA DE APACHE POI.

al que le interesa contactese conmigo....

este codigo sera una de las respuestas participantes en el Concurso Naciona de Investigacion de Operaciones de Chile, organizado por el Instituto Milenio de Sistemas Complejos de Ingenieria de Chile

visiten www.gocup.cl

interesados contactense conmigo..

son aproximadamente 1300 lineas de codigo..

nos vemos,

• 
• 
• 
• 
• 
• 

Estudiante 5to año Ingenieria Civil Industrial
Universidad de Talca, Chile

- 27 Ene 2009, 16:25 #139743

Enhorabuena monstruo!

• 
• 
• 
• 
• 
• 

Para colgar una imagen en un mensaje, pulsa aquí
Para introducir un enlace en un mensaje, pulsa aquí
Si eres nueva en el foro, preséntate aquí. Y págate unas cervezas al hacerlo.