Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

AGENTE VIAJERO

No description
by

miguel lozada

on 15 February 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of AGENTE VIAJERO

PROBLEMA DEL AGENTE VIAJERO EL PROBLEMA ENCONTRAR LA RUTA MAS CORTA PARA VISITAR UN NÚMERO N DE CIUDADES RESTRICCIONES VISITAR CADA CIUDAD UNICAMENTE UNA VEZ.
REGRESAR AL PUNTO DE PARTIDA. PROBLEMA DEL AGENTE VIAJERO
¿Como resolverlo? ODISEO (ULISES) Travesía de Odiseo Resultado: 653,837,184,000 Rutas diferentes!!!
Enumerandolas todas (utilizando una super computadora) ,tardaríamos alrededor de 92 horas en encontrar la solución óptima... SOLUCIÓN POR FUERZA BRUTA:
ANALIZA TODAS LAS RUTAS POSIBLES 16 CIUDADES HEURISTICA DEL VECINO MAS CERCANO EL HELICOPTERO HARÁ UNOS OCHENTA RECORRIDOS EN LOS 5 DIAS, ENCONTRAR LA RUTA MAS CORTA PERMITE RECABAR MAYOR INFORMACIÓN QUE AYUDARÁ A SALVAR VIDAS. ¿COMO SE APLICA EN LA VIDA REAL? EN LAS ULTIMAS SEMANAS UN INCENDIO FORESTAL HA CONSUMIDO MAS DE CIEN MIL HECTAREAS DE BOSQUE EN COAHUILA. LOS EQUIPOS TERRESTRES TARDARÁN AL MENOS CINCO DIAS EN LLEGAR

ES IMPOSIBLE LLEGAR POR AIRE ESTE HELICOPTERO CUENTA CON EL COMBUSTIBLE NECESARIO PARA HACER UN RECORRIDO COMPLETO Y RECABAR INFORMACIÓN VITAL PARA LA OPERACIÓN.

LUEGO DEBE REGRESAR POR SUMINISTROS. EL INCENDIO COMIENZA A REPRESENTAR PELIGRO PARA LAS COMUNIDADES DEL MAPA H A B C D
H 0 100 95 140 130
A 0 25 80 180
B 0 70 120
C 0 85
D 0
ESTAS SON LAS DISTANCIAS ENTRE LAS COMUNIDADES UTILIZANDO LA HEURISTICA DEL VECINO MAS CERCARNO H A B C D
H 0 100 95 140 130
A 0 25 80 180
B 0 70 120
C 0 85
D 0
H A B C D
H 0 100 95 140 130
A 0 25 80 180
B 0 70 120
C 0 85
D 0
H A B C D
H 0 100 95 140 130
A 0 25 80 180
B 0 70 120
C 0 85
D 0
95 95+25=130 130+80=210 210+85=295 TOTAL
295+130=425 0 EL PROBLEMA DEL VIAJERO ES DEL TIPO NP-COMPLETO; ESTO IMPLICA QUE SU COMPLEJIDAD COMPUTACIONAL CRECE EXPONENCIALMENTE RESPECTO AL AUMENTO EN EL NÚMERO DE CIUDADES. INCONVENIENTE DE UTILIZAR FUERZA BRUTA: 1800 1954 1962 1977 1987 1987 1987 1994 ALGORITMO DE COLONIA DE HORMIGAS HEURISTICA DE PATCHING SE UTILIZA PARA TSP NO SIMETRICOS, ES DECIR CUANDO LA DEISTANCIA DE A HACIA B ES DIFERENTE A LA DE B HACIA A 1998 2001 2004 INICIA SELECCIONANDO UNO DE LOS NODOS ALEATORIAMENTE SI HAY CIUDADES SIN VISITAR, LA SIGUIENTE ES LA MAS CERCANA A LA ACTUAL SI NO QUEDAN MAS CIUDADES, SE REGRESA A LA PRIMERA
Full transcript