Ejercicios Métodos de búsqueda

Instrucciones:

Realizar los ejercicios que se enlistan a continuación presentando:

Grafo del camino de solución Definición formal del problema Método de búsqueda de solución más optimo Conclusión (justificar porque se seleccionó ese método)

Ejercicio #1.- Llaves perdidas.

Imagine que ha perdido las llaves de su coche. Sabe que están en algún lugar de la casa, cuyo plano está en la

figura 1. La X indica que usted está en la puerta principal. Presente el resultado más óptimo para la búsqueda de

llaves.

Figura 1. Plano de la casa

Ejercicio #2.- Agente de viajes con rutas ADO GL

Imagine que usted es agente de viajes y un cliente bastante molesto quiere que le reserve un boleto de Salina

Cruz a Ciudad Reynosa con la línea de autobuses ADO-GL. A pesar de que usted le dice al cliente que la línea de

autobuses ADO-GL no tiene rutas directas, éste insiste en viajar exclusivamente con ADO-GL R. Mirando la lista

(supuesta) de rutas de ADO-GL R, encuentra que es posible (véase tabla1). Entonces puede verse que hay una

forma de llegar de Salina Cruz a Ciudad Reynosa con la línea de autobuses ADO-GL R usando trasbordos. Así pues

reserva un boleto para el cliente.

La información extraída del libro de rutas del ADO-GL puede ser trasladada al grafo no dirigido mostrado en la figura 2.

Utilice todas las técnicas vistas en clase para resolver este problema y defina en su conclusión la más óptima:o Primero en profundidado En amplitud o Primero el mejor

Figura 2. Árbol parcial de rutas ADO GL

Origen Destino Distancia Kms en línea recta de Origen a Ciudad Reynosa

Salina Cruz Tehuantepec 23 Kms 1181 KmsTehuantepec Oaxaca 248 Kms 1160 Kms

Juchitán Tehuantepec 26 Kms 1120 kms

Juchitán Ixtepec 19 Kms 1120 Kms

Ixtepec Ixtaltepec 4 Kms 1115 Kms

Juchitán Tonalá 172 Kms 1120 Kms

Tonalá Pijijiapan 76 Kms 1240 Kms

Pijijiapan Huixtla 93 Kms 1300 Kms

Huixtla Tapachula 42 Kms 1340 Kms

Tonalá Tuxtla Gutiérrez 173 Kms 1240 Kms

Tuxtla Gutiérrez Villahermosa 252 Kms 1237 Kms

Comitán San Cristóbal 88 Kms 1296 Kms

San Cristóbal Ocosingo 88 Kms 1260 Kms

Ocosingo Palenque 103 Kms 1242 Kms

Palenque Villahermosa 145 Kms 1200 Kms

Salina Cruz Huatulco 153 Kms 1181 Kms

Huatulco Puerto Escondido 106 Kms 1175 Kms

Oaxaca Puebla 342 Kms 1022 Kms

Villahermosa Cárdenas 49 Kms 1077 Kms

Villahermosa Ciudad del Carmen 170 Kms 1077 Kms

Ciudad del Carmen Campeche 206 Kms 1120 Kms

Campeche Mérida 174 Kms 1178 Kms

Mérida Cancún 310 Kms 1172 Kms

Cancún Playa del Carmen 68 Kms 1378 Kms

Playa del Carmen Chetumal 328 Kms 1350 Kms

Campeche Chetumal 372 Kms 1168 Kms

Cárdenas Coatzacoalcos 128 Kms 930 Kms

Coatzacoalcos Minatitlán 22 Kms 1040 Kms

Minatitlán Acayucan 52 Kms 1050 Kms

Acayucan Córdoba 251 Kms 1100 Kms

Acayucan Juchitán 206 Kms 1100 Kms

Córdoba Orizaba 26 Kms 758 Kms

Orizaba Puebla 149 Kms 770 Kms

Puebla Cd. de México 124 Kms 804 Kms

Acayucan Veracruz 255 Kms 1100 Kms

Veracruz Xalapa 102 Kms 915 Kms

Veracruz Poza Rica 249 Kms 915 Kms

Poza Rica Tuxpan 52 Kms 720 Kms

Tuxpan Tampico 180 Kms 690 Kms

Tampico Matamoros 508 Kms 420 Kms

Matamoros Reynosa 86 Kms 84 Kms

Tabla 1Distancias aproximadas entre terminales de la línea ADO GL

Seleccione la mejor técnica de búsqueda y resuelve los ejercicios del 3 – 5.

Ejercicio # 3.- Problema del agente viajero

Un vendedor tiene una lista de ciudades cada una de las cuales debe visitar solamente una vez; existen carreteras directas entre cada par de ciudades de la lista. Se debe encontrar la ruta que el vendedor debería seguir para que, siguiendo el camino más corto posible, visitara todas las ciudades, comenzando por cualquiera de ellas y volviendo a la misma. Un ejemplo de éste tipo de problemas para seis ciudades se plantea en la figura 2.

Tabla 2. Matriz de Distancias

1 2 3 4 5 61 13 1

218 7 14

2 13

21

26 15

25

3 12

21 11 6 4

4 18

26 11

12

14

5 7 15 6 12 96 1

425 4 14 9

Ejercicio # 4.- Problema del agente viajero

Imagine que usted es un agente de viajes y que un cliente le pide que le reserve su pasaje en algún vuelo de Nueva York a Los Ángeles, pero con la aerolínea XYZ ya que el cliente tiene un pase de cortesía; usted observa la lista de vuelos de XYZ y encuentra que no existe un vuelo directo y que tendrá que hacer la reservación utilizando transbordos.

Figura 3. Grafo de rutas de la aerolínea XYZ

Ejercicio # 5. El problema del laberinto.

En las figuras 6 se muestra un ejemplo del problema a resolver (salida de un laberinto) y la gráfica de su espacio de estados. Traza la ruta para salir del laberinto sabiendo que el punto de partida es 1 y 21 es la meta.

Figura 4. Laberinto