Diferencias

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

--- ai:techniques:search_algorithms [2010/10/24 08:56]
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>
@@ Línea 119: / Línea 125: @@
-==== Simulated annealing ====
-Es un hill climbing pero que permite la bajada. El hill climbing tiene el el inconveniente que puede quedarse atascado
+===== 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