******
A-Star
******

*  We have seen how Dijkstra's algorithm can help to find the shortest path in a graph.
*  However, it requires to visit every node which is time consuming.
*  We will now introduce a new concept **heuristic search**.

Heuristic search
================

*  Heuristic search is the name given to algorithms that are using a heuristic function to find the solution.

.. admonition:: Definition
    :class: important

    *Heuristic function* or *heuristic* is a function that provides an estimation of the unknown solution.

*  Using heuristic functions allow us to prune suboptimal solution, thus saving time.

A-Star
======

*  The :math:`A^*` algorithm was created to solve path planning problem for robots in environments that could contain obstacles.
*  It was the first algorithm implementing tree pruning.
*  Instead of search in order of closeness from the source, it searches in order of closeness to the goal.
*  We had two arrays, :math:`h[v]` and :math:`f[v]`:

   *  :math:`h[v]` will contain the distance to the node :math:`v` calculated by the heuristic function.
   *  :math:`f[v] = d[v]+h[v]` is the estimated distance from :math:`s` to :math:`v`.

*  It selects the node with the smallest :math:`f`.

How is it working?
------------------

*  We will consider the following graph:

.. figure:: ./img/astar/graph.drawio.png
    :align: center

|

*  The source node is :math:`A` and the goal is :math:`J`.

.. figure:: ./img/astar/astar_01.drawio.png
    :align: center

|

*  Using :math:`A^*`, we will start from :math:`J`.
*  We explores the adjacent edges.

.. figure:: ./img/astar/astar_02.drawio.png
    :align: center

|

*  We visit the closest node :math:`D` and explore the adjacent edges.

.. figure:: ./img/astar/astar_03.drawio.png
    :align: center

|

*  The smallest value :math:`f` is for the node :math:`I`.
*  We visit :math:`I` and check the edges.
*  We update :math:`H`, because it's new value :math:`465` is smaller than the previous :math:`610`.

.. figure:: ./img/astar/astar_04.drawio.png
    :align: center

|

*  The smallest value is :math:`776` for the node :math:`H`.
*  We visit this node and check the edge leading to :math:`F`.
*  The new value :math:`590` is smaller than the previous value :math:`615`.

.. figure:: ./img/astar/astar_05.drawio.png
    :align: center

|

*  Now, the node with the smallest estimated distance is going through  :math:`C`.
*  We are updated the adjacent nodes that are not visited yet, so :math:`A` and :math:`B`.

.. figure:: ./img/astar/astar_06.drawio.png
    :align: center

|

*  Since the distance to :math:`A` is smallest that the other estimation, we stop.

.. figure:: ./img/astar/graph_after.drawio.png
    :align: center

|

Algorithm
---------

*  Now, we can discuss the pseudocode:

.. code-block::

    Initialize V–S with all vertices except the starting vertex s.
    for all v in V–S:
        p[v] = s
        if there is an edge (s, v):
            d[v] = w(s, v)
            f[v] = d[v] + h(v)
        else:
            d[v] = inf
            f[v] = inf

    while V–S is not empty:
        u = find the smallest f[u]
        if u == destination:
            break
        Remove u from V–S
        Add u to S
        for all v adjacent to u in V–S:
            if d[u] + w(u, v) < d[v]:
                d[v] = d[u] + w(u, v)
                f[v] = d[v] + h(v)
                p[v] = u