Es un algoritmo que se basa en tratar la evolución de estados de un problema como si de un grafo se tratase. Los nodos de este grafo son los posibles estados del problema, y estos pueden representar cualquier cosa, desde una coordenada 2d hasta la posición de las piezas de un puzle.

Los nodos se unen por aristas, estas corresponden a los cambios que hay que hacer para cambiar de un estado a otro. De un nodo salen tantas aristas como cambios inmediatos pueden hacerse.

A cada nodo del árbol se le asigna un coste, este coste corresponde a lo cerca que está un estado del estado final, es decir, la solución. La forma de calcular el coste es distinta para cada problema y a la vez importante para su resolución. Cuando el estado final es desconocido o complejo de calcular podemos indicar que el coste del nodo corresponde a la dificultad que plantea tomarlo, por ejemplo, en una carrera un terreno plano tendrá menos costo que una subida.

Para llevar a cabo el algoritmo A* necesitaremos…

• Los tres atributos, como mínimo que tendrá cada nodo del grafo de estados:
  • , el coste de tomar ese nodo. Este es el coste de llevar a cabo la acción que representa dicho nodo más el coste de su padre.
  • , cuanto dista nodo del objetivo, este valor más que ser una distancia “física” es una función heurística que calcula “las diferencias”.
  • , el fitness del nodo, una puntuación que represente su calidad.
• Dos listas:
  • La lista de los nodos abiertos, los que aún no han sido (o no han podido ser) explorados. En él iremos colocando los nodos que vayamos encontrando pero que aún no han sido tratados.
  • La lista de los nodos cerrados, los que han sido explorados.

Partiendo de un estado que será el denominado “estado actual”…

1. Encontramos los próximos estados.
   1. Del estado actual encontramos los posibles estados siguientes.
   2. Calculamos la g y la h (1 más la h del nodo padre) de ese nodo.
   3. Guardamos estos nodos en la lista de nodos abiertos.
2. Ponemos el nodo actual en la lista de nodos cerrados.
3. Elegimos el siguiente nodo actual.
   1. De todos los nodos de la lista de nodos cerrados escogemos el de f más baja.
4. Si el estado actual es el estado objetivo ya hemos acabado. Si no, volvemos al paso 1.

Como ejemplo al estudio del A* haremos un seguimiento del algoritmo en la resolución de un puzzle de 8 fichas, un 3×3.
Se seguirá el siguiente diagrama que parte de un posible estado (1) e intenta llegar a un objetivo (4) utilizando el A*. Aunque para cada problema el cálculo del parámetro h es distinto y en él radica la calidad de la solución, en este se ha utilizado la Distancia Manhattan (aunque se podría haber utilizado cualquier otra). La forma concreta de cálculo ha sido:
Siendo el número de piezas mal colocadas en cada iteración, con esto conseguimos dar más puntuación a aquel estado que tiene más fichas mal colocadas. La i, por lo tanto sería el número de pieza.

1. Desde un estado (1) el algoritmo calcula el f,g y h de este.
2. Luego encuentra los estados posibles (2) y (3), calcula de cada uno de estos f,g y h y los introduce en la lista de abiertos.
3. Coloca el estado (1) en la lista de cerrados.
4. En la lista de abiertos comprueba qué h es más baja, la del estado (2).
5. El estado (2) es el objetivo? No, por lo que seguirá expandiendo el árbol a partir de este.
6. Del estado (2) encuentra el (4) y el (5), calcula sus f, g, h y los introduce en la lista de abiertos.
7. Coloca el estado (2) en la lista de cerrados.
8. Comprueba cual de los de la lista de abiertos ((3), (4), (5)) tiene el f más pequeño.
9. Escoge el (4).
10. Es el objetivo? Sí → fin!.

Y aquí una implementación.

El hill-climbing (también llamado rather descent si su función evalua el coste en vez de la calidad, aunque también podríamos convertir el valor de coste a negativo) intenta, sobre una solución ya existente del problema qué cambios hay que hacer hasta conseguir una solución mejor.
Representa la búsqueda que realiza como si fuese un escalador que, en medio de una densa niebla, busca la cima de un monte pero este no sabe cual es, ya que un monte puede tener varios picos y el escalador puede creer que un pico es la cima debido a la niebla.
El algoritmo consiste en un bucle que busca incrementar la calidad de una situación. Empieza con una solución inicial (generada aleatoriamente) y de forma iterativa va haciendo pequeños cambios hasta llegar a la mejor solución que pueda encontrar, entonces usa dicha solución como solución inicial y así continúa. Por lo tanto no depende de un árbol de búsqueda (nodos), es por eso que el problema le ha de permitir evaluar dichos nodos (o estados) de forma independiente. Cuando los estados a los cuales se puede acceder desde el estado actual tienen un valor equivalente el siguiente que se evaluará se seleccionará aleatoriamente. En este algoritmo se distinguen los siguientes conceptos:

• Máxima local: Consiste en un “pico” que puede ser más bajo que el pico más alto (óptimo) y es al que ha de llegar ya que, aún no siendo la mejor solución es una satisfactoria.
• Explanada: Un area en el que al evaluar los siguientes pasos tenemos un valor equivalente. La búsqueda seguirá un camino aleatorio.
• Colinas: Hay máximas locales muy próximas y la búsqueda oscila entre ellas haciendo mínimo o ningún progreso. Si esto ocurre lo mejor que puede hacerse es reiniciar en otro punto aleatorio.

Realmente el algoritmo lo que hace es iniciar en una solución aleatoria y busca una mejor y próxima solución hasta encontrar una que no pueda mejorar. Puede restringirse el número de iteraciones en las que permitiremos en las que no se haga un avance, así si hay un máximo restricción de iteraciones permitidas un reinicio aleatorio puede llegar a encontrar la solución óptima. El éxito depende de la diversidad de estados “picos”, si sólo existen pocas máximas locales un reinicio aleatorio encontrará una solución óptima bastante rápido, pero por desgracia los problemas reales tienen una superficie parecida a la de un puercoespín, muchas máximas locales. Aún así, y debido a esto, es fácil encontrar rápidamente una buena solución a pesar de que esta no sea la óptima.

function Hill-Climbing (problema) retorna una posible solución
  entrada: 
    problema
  utiliza: 
    currentNode
    nextNode
  ejecución:
    currentNode = getInitialState (problem)
    loop do
      nextNode = currentNode.getSuccessors().getNodeWithMaximumValue()
      if (nextNode.value < currentNode.value)
        return current
      currentNode = nextNode
    end loop 

• 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 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, 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.

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.

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 isProbable(∧E, T) 
        current = next

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.