The simplest example of an LTS and an admissible and non-consistent heuristic is simply an LTS built on a chain $a\to b\to c$ where $c$ is the only goal state. Suppose that the transitions cost $1$. Then $h(a)=2$, $h(b)=0$, $h(c)=0$ is an admissible heuristic that is not consistent because $h(a)-h(b)=2-0=2>1$. However, this simple LTS and the heuristic cannot puzzle GBFS, as only a single path goes from $a$ to $c$.

Consider the following LTS $\Theta=\langle S,A,T,G\rangle$ where $S=\{a,b,c,d\}$, $A=\{\alpha,\beta,\gamma,\delta\}$, $G=\{d\}$, and the transitions $T$ are shown in the digraph below:

The costs of the actions are defined:

The heuristic $h$ is defined:

It is easy to check that $h$ is admissible. To see that it is not consistent, consider the transition $\langle b,\beta,c\rangle\in T$. We have $h(b)-h(c)=3-0=3> \mathsf{cost}(\beta)$.

As an initial state, we choose $a\in S$. GBFS employs two data structures to keep its state of the computation: the priority queue $Open$ for states to be expanded, a set $Closed$ for already expanded states, and $Parent$ storing for each expanded state its predecessor and action. The elements of the priority queue are pairs of the form $(p,s)$ where $p$ is the priority and $s$ is a state.

In the final iteration, the goal state $d$ is removed from $Open$, and the algorithm terminates. Thus the plan returned by GBFS is $\pi=\gamma,\delta$ and $\mathsf{cost}(\pi)=3+2=5$, i.e., non-optimal plan.

A$^*$ replaces $Closed$ with gScores.

Note that the 2nd iteration expands the state $b$ and must reopen $c$ again as the path through $b$ is cheaper than the direct path from $a$. In the 3rd iteration, the algorithm expands $c$, finds a cheaper path to $d$, and updates the priority of $d$ in $Open$.

In the final iteration, the goal state $d$ is removed from $Open$, and the algorithm terminates. Thus the plan returned by A$^*$ is $\pi^*=\alpha,\beta,\delta$ and $\mathsf{cost}(\pi)=1+1+2=4$, i.e., the optimal plan.