Tip:
Highlight text to annotate it
X
Así, hemos visto dos algoritmos de búsqueda.
Uno, la búsqueda en anchura, en el que siempre expandimos primero
los caminos más superficiales, los caminos más cortos.
En segundo lugar, la búsqueda del menor costo, en la que siempre expandimos primero el camino
con el menor costo total.
Y voy a aprovechar esta oportunidad para introducir un tercer algoritmo, la búsqueda en profundidad,
que es en cierto modo lo contrario de la búsqueda en anchura.
En la búsqueda a profundidad, siempre ampliamos primero el camino más largo,
el camino que tiene el mayor número de longitudes.
Ahora, lo que quiero pedirles que hagan es para cada uno de estos nodos en cada uno de los árboles,
dígannos en qué orden se expanden,
primero, segundo, tercero, cuarto, quinto y así sucesivamente, poniendo un número en la casilla.
Y si hay algún empate, pongan el número y resuelvan el empate en orden de izquierda a derecha.
Entonces quiero preguntarles algo más o respóndanme una pregunta más
la cual es, ¿Son estas búsquedas óptimas?
Es decir, ¿garantizan encontrar la mejor solución?
Y para la búsqueda en anchura, óptimo significaría encontrar el camino más corto.
Si piensan que está garantizado encontrar el camino más corto, marquen aquí.
Para el de menor costo primero, significaría encontrar el camino con el menor coste total de la ruta.
Marquen aquí si está garantizado que lo haga.
Y vamos a permitir que la suposición que todos los costos tienen que ser positivos.
Y para la búsqueda en profundidad, el más barato u óptimo sería, de nuevo,
así como en la búsqueda de anchura, encontrar el camino más corto posible, en cuanto al número de longitudes.
Marque aquí si piensan que la búsqueda en profundidad siempre lo encontrará.