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?
T63. Id Pregunta: 1788. Búsquedas.
- BeneGesserit
- PreparaTIC25
- Mensajes: 44
- Registrado: 06 Abr 2010, 14:02
- Agradecido: 0
- Agradecimiento recibido: 0
- vfrades
- PreparaTIC XXI
- Mensajes: 631
- Registrado: 16 Jun 2008, 15:40
- Agradecido: 0
- Agradecimiento recibido: 0
Re: T63. Id Pregunta: 1788. Búsquedas.
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.
- BeneGesserit
- PreparaTIC25
- Mensajes: 44
- Registrado: 06 Abr 2010, 14:02
- Agradecido: 0
- Agradecimiento recibido: 0
Re: T63. Id Pregunta: 1788. Búsquedas.
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..!
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..!
- Miguelinho
- Usuario registrado
- Mensajes: 787
- Registrado: 16 Sep 2013, 00:28
- Agradecido: 0
- Agradecimiento recibido: 0
Re: T63. Id Pregunta: 1788. Búsquedas.
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
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
- BeneGesserit
- PreparaTIC25
- Mensajes: 44
- Registrado: 06 Abr 2010, 14:02
- Agradecido: 0
- Agradecimiento recibido: 0
Re: T63. Id Pregunta: 1788. Búsquedas.
¡O sea, que aún hay que hilar más fino de lo que yo imaginaba!
Gracias de nuevo, Miguelinho.
Gracias de nuevo, Miguelinho.