T63. Id Pregunta: 1788. Búsquedas.

Temas relacionados con el examen de test
Cerrado
Avatar de Usuario
BeneGesserit
PreparaTIC25
Mensajes: 44
Registrado: 06 Abr 2010, 14:02
Agradecido: 0
Agradecimiento recibido: 0

T63. Id Pregunta: 1788. Búsquedas.

Mensaje por BeneGesserit »

59) Al realizar la búsqueda en un espacio de estados, el método de backtraking …
a) Solo se puede usar para búsquedas ciegas
b) Permite ahorrar recursos de computación
c) Permite recorrer los árboles solo en anchura
d) Permite recorrer los árboles solo en profundidad

Correcta, la b)
Yo creo que se refiere a que en lenguajes como Prolog no existen instrucciones de control, por lo que su ejecución se basa en dos conceptos: la unificación y el backtracking (retroseguimiento). Gracias a la unificación, cada objetivo determina un subconjunto de cláusulas susceptibles de ser ejecutadas. Cada una de ellas se denomina punto de elección. Prolog selecciona el primer punto de elección y sigue ejecutando el programa hasta determinar si el objetivo es verdadero o falso. En caso de ser falso entra en juego el backtracking, que consiste en deshacer todo lo ejecutado situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección. Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Todos los objetivos terminan su ejecución bien en verdadero, bien en falso.
A mí me parece que esto no ahorra recursos de computación, sino lo contrario.
¿Tenéis alguna otra interpretación?

Avatar de Usuario
vfrades
PreparaTIC XXI
Mensajes: 631
Registrado: 16 Jun 2008, 15:40
Agradecido: 0
Agradecimiento recibido: 0

Re: T63. Id Pregunta: 1788. Búsquedas.

Mensaje por vfrades »

Aquí lo que habla es del backtracking en algoritmos de búsqueda. Tal como yo lo tengo entendido, es una variante de una búsqueda en profundidad en la que comienza a explorarse una rama y, si la rama no parece "prometedora" (normalmente se aplica algún tipo de heurística) se vuelve al nodo anterior (backtracking) y se comienza a explorar una nueva rama en lugar de explorar hasta el final la rama poco "prometedora". Ahorra recursos de computación en el sentido de que no se pierde el tiempo en buscar allí donde parece improbable encontrar nada. Lo que no ahorra es recursos de memoria, porque obliga a mantener traza de dónde se ha hecho backtracking por si al final hay que volver a explorar ramas que ya habían sido abandonadas.

Avatar de Usuario
BeneGesserit
PreparaTIC25
Mensajes: 44
Registrado: 06 Abr 2010, 14:02
Agradecido: 0
Agradecimiento recibido: 0

Re: T63. Id Pregunta: 1788. Búsquedas.

Mensaje por BeneGesserit »

Muchas gracias, vfrades.
Había descartado el backtracking de la búsqueda en profundidad porque había contestado la d) y estaba mal (supongo que por la palabra "solo"), y estaba buscando si se referiría a otra cosa...
¡a veces hay que hilar tan fino..!

Avatar de Usuario
Miguelinho
Usuario registrado
Mensajes: 787
Registrado: 16 Sep 2013, 00:28
Agradecido: 0
Agradecimiento recibido: 0

Re: T63. Id Pregunta: 1788. Búsquedas.

Mensaje por Miguelinho »

Hola a ambos,

Lo que describe vfrades sería "ramificación y poda" que es un tipo de backtracking. Por tanto, su explicación es impecable y correcta.

Sin embargo, creo que incluso el "backtracking puro", es decir, el backtracking sin poda de ramas, también permitiría ahorrar recursos de computación, en este caso, memoria. Lo ilustro con un ejemplo.

Considérese el problema de mostrar por consola todas las permutaciones de un array. Un algoritmo que NO diese "marcha atrás", que sólo avanzase incesantemente, necesitaría un array por cada permutación (una matriz). Sin embargo, con backtracking, al dar marcha atrás, podemos reutilizar el mismo array. Avanzamos hacia una solución, cuando la alcanzamos, mostramos la permutación correspondiente y entonces, damos vuelta atrás para construir otra permutación diferente, pero siempre con el mismo array. Ahorramos, por tanto, memoria que es un recurso computacional.

Un saludo,

Miguel

Avatar de Usuario
BeneGesserit
PreparaTIC25
Mensajes: 44
Registrado: 06 Abr 2010, 14:02
Agradecido: 0
Agradecimiento recibido: 0

Re: T63. Id Pregunta: 1788. Búsquedas.

Mensaje por BeneGesserit »

¡O sea, que aún hay que hilar más fino de lo que yo imaginaba!
Gracias de nuevo, Miguelinho.

Cerrado

Volver a “PRIMER EXAMEN 2014”