Informed Search Strategies

Informed Search Strategies

To improve the efficiency of search algorithms, problem-specific information must be incorporated to solve complex issues with a large number of potential states.

Heuristic Evaluation Functions

They work out the cost of the cheapest way between two points. For sliding-tiles games, a heuristic function is calculated by calculating the number of movements each tile makes from its target state and adding this value for all tiles.

Pure Heuristic Search

It extends nodes in the order in which their heuristic values appear on the graph. It generates two lists: a closed list for previously raised nodes and an empty list for nodes that have been generated but have not yet been enlarged.

Each iteration produces all of the child nodes of the node with the lowest heuristic value and places them in the closed list. The heuristic function is then applied to the child nodes, and their heuristic value is used to determine where they belong in the open list. Shorter routes are kept, whereas longer paths are discarded.

A * Search

It's the most well-known variation of the Best First search. It avoids extending already-expensive routes, instead prioritising the most promising ones.

  • f(n) = g(n) + h(n), where g(n) is the cost of getting to the node thus far.
  • f(n) estimated total cost of the journey via n to goal h(n) expected cost to go from node to target. It is implemented by raising f and utilising a priority queue (n).

Greedy Best First Search

It enlarges the node that is thought to be closest to the target. It extends nodes using the formula f(n) = h. (n). A priority queue is used to implement it.

It can become trapped in loops, which is a disadvantage. This isn't ideal.