Informed research:

Informed research techniques are essential in the fields of artificial intelligence, especially to solve optimization problems such as games or planning.

Here is an overview of the main methods mentioned and specific algorithms such as A*, SMA* and their variants:

1.       Heuristic Search:

Heuristic search uses a cost or evaluation function to select the most promising nodes in the search space. It is often used for routing or optimization problems. The two main types of heuristic search are:

•       Best-First Search

•       Greedy Search

1 .1 Best-First Search:

This strategy explores nodes based on their estimated heuristic cost (function h( n )) It favors nodes with the lowest estimated cost, but may lead to non-optimal solutions.

            1.2   Greedy Search:

It favors the nodes close to the solution according h( n ), without taking into account the already accumulated cost. It is fast but not optimal because it does not always guarantee the shortest path.

Specific algorithms:

a)       Algorithm A* :

Is an informed research technique that guarantees an optimal solution if a qualifying heuristic is used (i.e., it never overestimates the remaining cost to reach the target). A* uses a cost function

 f( n ) = g( n ) + h( n ) ,

where:

g( n ): is the cost to reach the current node n from the starting node.

h( n ): is the heuristic that estimates the remaining cost to reach the objective from n.

A* is widely used in finding optimal paths because of its efficiency and accuracy, but it requires memory to store all visited nodes, which can be a problem in very large search spaces.

Example :

 

  •       Use the A* algorithm to calculate the best path from A to D.

•       Best path : A, C,D

             b)      SMA* Simplified Memory-bounded A*:

The SMA* algorithm is a variant of A* that incorporates a memory limit, making it more suitable for large search spaces. SMA* works by:

1- Storing only the most promising nodes in memory based on available space.

2- Replacing the less promising nodes if memory is saturated.

3- This approach ensures more efficient exploration without exceeding memory constraints, although it may require recalculation of some paths.

c)       Extensions of A* and SMA*:

Many algorithms have been developed based on A* and SMA* to adapt to different types of problems and constraints, including:

d)      IDA (Iterative Deepening A)**:

IDA (Iterative Deepening A)** combines the iterative depth with A* to reduce memory requirements by exploring longer and longer paths, but with a memory constraint.

e)      Weighted A*:

The Weighted A* algorithm, which is a variant of A* where the heuristic is weighted by a factor  w to give more weight to heuristics and explore paths faster, sometimes at the cost of optimality. In Weighted A*, the cost function is defined as:

 f( n ) = g( n ) + w x h( n )

Or:

g( n ): is the accumulated cost of the path from the starting node to the current node n.

h( n ): is the estimated heuristic cost to reach the goal since ( n )

w: is a weighting factor (w>=1), which determines the importance of heuristics in the calculation of f( n )

f)        Theta*:

Theta*: a modified version for maps and geometric problems, allowing diagonal and more efficient movements.