1 of 7

Heuristic Search�(informed)

Incorporates expert rules, empirical, experimental to streamline the search engines.

​

  • They are guesses or assumptions.
  • Not have to guarantee optimality.
  • Must work well in several problems.
  • Can fail.

​

Heuristic Function:

Let  be a problem in artificial intelligence and its state space E, a function that associates each state of E a real number, this is:

f: E → R,

Heuristic function is called associated to .

Heuristic function measures the usefulness of information

associated with each additional state.

​

​

2 of 7

Heuristic Function

Examples:

Problem Heuristic Function

Game Utilidad asociada a cada posible

juego

Traveling Salesman Distance associated with each

possible to visit city

Three in line Increased number of X collinear� (case plays X) where no 

Water Vessel Atingir liters missing for the� solution

Project Selection Utility associated with each project -  most useful

​

3 of 7

Búsqueda en Profundidad Limitada

Se usa aún cuando no haya función heurística de los estados.

La idea es suponer que el camino a la meta nunca será

demasiado largo. Si el camino que se explora lo es, entonces

se busca otro.

​

Se lleva un solo camino

​

  • Si la solución actual es la meta: FIN
  • Si no lo es:
    • Si la profundidad es menor que P, tomar el primer arco y seguir la búsqueda
    • Si no, dar por acabada la búsqueda en esa rama

​

Incluye la posibilidad de retractarse.

​

​

4 of 7

Search limited depth

TREE 1

¿ and P=2 ?

P =3, Travel:a,b,e,f,c,g,d,h,z Road:a,d,z

Begin

End

5 of 7

Search restricted by threshold

Used when heuristic function of the states that give His estimate of quality (close to the target).

​

The idea is to assume that if the current node is bad, then the path does not lead to the goal. If the path that explores what it is, then look elsewhere.

​

It takes a single path.

Each node has an associated heuristic value.

​

  • If the current solution is the goal: END
  • If it is not:
    • If the heuristic node is less than U, take the first arch and continue the search.
    • If not, give finished searching for that branch.

​

Includes the ability to retract.

​

6 of 7

Search restricted by threshold

Begin

End

U=6, Travel:a,b,c,g,s,z Road:a,c,g,s,z

7 of 7

Bibliography

  • Winston, P. H., “Inteligencia Artificial” , Addison-Wesley Iberoamericana, Tercera Edición, 1994, pp. 69-78.
  • Rich, E. y Knight, Artificial Intelligence, McGraw-Hill, Segunda Edición, 1991, pp. 29-44.
  • Russel, S. y Norving, P, Inteligencia artificial, un enfoque moderno, pp. 3-15, 1997.

​