Funciones heurísticas

• h1, el número de casillas que están en posición incorrecta. h1 = 7 en el ejemplo
• h2, la suma de las distancias verticales y horizontales (distancia Manhattan). h2 = 18 en el ejemplo
• IF para todos los estados n entonces h2 domina a h1
• si h2 domina a h1, h2 es más eficiente que h1
  • se expande todo nodo con
  • lo que es decir que se expande todo nodo con
  • ya que todos los nodos que expande h2 también los expande h1, y h1 puede expandir más
  • por tanto, es mejor tener heurísticas con valores altos siempre y cuando no sobreestimen
• inventando nuevas heurísticas
  • normalmente el coste de una solución exacta para un problema menos restrictivo es una buena heurística para el problema original
  • problema original. Se puede mover de A a B si:
    • A y B son adyacentes y B es la casilla en blanco
  • problema menos restrictivo. Se puede mover de A a B si:
    • A y B son adyacentes
    • B es la casilla en blanco
    • ninguna condición
• usar el máximo de un conjunto de heurísticas
• usar información estadística