Diferencias

Muestra las diferencias entre dos versiones de la página.

--- ai:techniques:search_algorithms [2010/10/24 08:49]
alfred
+++ ai:techniques:search_algorithms [2020/05/09 09:25] (actual)
@@ Línea 28: / Línea 28: @@
     - De todos los nodos de la lista de nodos cerrados escogemos el de //f// más baja.
   - Si el estado actual es el estado objetivo ya hemos acabado. Si no, volvemos al paso 1.
@@ Línea 82: / Línea 83: @@
+===== IDA* =====
+  - Realizamos el cálculo de coste para el nodo 1, ese será el coste (o profundidad) inicial y máximo permitido.
+  - Nos ponemos en el primer nodo.
+  - Vamos al siguiente nodo (moviéndonos siempre en profundidad, es decir, siempre abriremos el último nodo.
+  - Si el siguiente nodo no pasa del coste máximo actual lo cogemos como nodo actual y hacemos el paso 3.
+  - Miramos el siguiente que toque (desde un nodo anterior).
+  - Si ningún nodo puede expandirse por superar todos el coste máximo, incrementamos este y vamos al paso 2.
+{{ ai:ida.png |}}
 ===== Hill-Climbing =====
@@ Línea 101: / Línea 103: @@
 <code>
 function Hill-Climbing (problema) retorna una posible solución
-  entrada: problema
+  entrada:
-  utiliza: currentNode, nextNode
+    problema
-  currentNode = getInitialState (problem)
+  utiliza:
-  loop do
+    currentNode
-    nextNode = currentNode.getSuccessors().getNodeWithMaximumValue()
+    nextNode
-    if (nextNode.value < currentNode.value)
+  ejecución:
-      return current
+    currentNode = getInitialState (problem)
-    currentNode = nextNode
+    loop do
-  end loop
+      nextNode = currentNode.getSuccessors().getNodeWithMaximumValue()
+      if (nextNode.value < currentNode.value)
+        return current
+      currentNode = nextNode
+    end loop
 </code>
 ==== Variantes ====
-  * **Stochastic hill climbing**
+  * **Stochastic hill climbing**, escoge aleatoriamente entre los siguientes pasos que mejoran la solución actual. Esto generalmente es un ascenso lento pero en algunos problemas puede dar mejores soluciones.
-  * **First-Choice hill climbing**
+  * **First-Choice hill climbing** es un stochastic hill climbing pero en la generación de futuros estados. Va generando pasos siguientes hasta que encuentra uno mejor, es decir, será el primer estado mejor el que escoja. Es una buena estrategia cuando el estado tiene muchos sucesores.
-  * **Random-restart hill climbing**
+  * **Random-restart hill climbing**, genera varios estados iniciales de forma aleatoria (en sí ya es un problema ya que no es trivial), a partir de estos inicia distintas soluciones.
-===== Simulated annealing =====
+===== Simulated annealing =====
+Es un hill climbing pero que permite la bajada. El hill climbing tiene el el inconveniente que puede quedarse atascado en una máxima local, pero si, al contrario de esto, realizasemos un movimiento puramente aleatorio sería extremadamente ineficiente a pesar de que podría alcanzar el problema óptimo en algún momento. En metalurgia "annealing" es el proceso para calentar metales y vídrios, moldearlos y luego enfriarlos. Simulated annealing consiste en eso, en subir y bajar la temperatura o, en el caso de un hill climbing, la colina.
+<code>
+función SimulatedAnnealing (problema, organización) retorna un estado solución
+  entrada:
+    problema
+    organización, asigna la relación tiempo\temperatura
+  ejecución:
+    current = getInitialState (problem)
+    for t = 1 hasta infinito hacer:
+      T = organización (t)
+      if T = 0:
+        return current
+      next = current.getRandomSuccessors()
+      ∧E = next.Value - current.Value
+      if ∧E > 0:
+        current = next
+      else if getProbability(∧E, T) > random(0,1):
+        current = next
+</code>
+El loop interno es similar al del hill climbing, pero en vez de escoger el mejor movimiento escoge uno aleatorio, si dicho movimiento mejora la situación será siempre aceptado pero si no a cada paso que se haga será, por probabilidad, más difícil que se siga. Es decir, la mala calidad de la solución hace que la temperatura (//T//) baje y, por lo tanto, la cantidad de evaluación (//∧E//) menor.

Programming

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página