Lesson 2

Let us now describe the algorithm more precisely.

We maintain a set of discovered configurations that have not yet been processed. This set is usually called the open set. For each configuration \(v\), we store:

• the value \(g(v)\);


• the value \(f(v)=g(v)+h(v)\);


• the previous configuration on the currently best known path to \(v\).

Initially, the open set contains only the starting configuration \(s\). We set \[g(s)=0\] and compute \(f(s)=h(s)\).

Then we repeat the following steps:

1. Take from the open set a configuration \(v\) with the smallest value of \(f(v)\).
2. If \(v\) is the target configuration, stop: a shortest path has been found.
3. Otherwise, consider all configurations that can be obtained from \(v\) by one move.
4. For each such neighbor \(u\), check whether the path through \(v\) improves the currently known value of \(g(u)\).
5. If it does, update \(g(u)\), recompute \(f(u)=g(u)+h(u)\), remember that \(v\) is the predecessor of \(u\), and add \(u\) to the open set if necessary.

After the target configuration is reached, we reconstruct the answer by following the predecessor pointers backwards.