An empirical heuristic

Our second heuristic, $h^{\mathrm{emp}}$, was originally proposed by Och et al. och2001 in the context of machine translation. To construct the heuristic $h^{\mathrm{emp}}$, we first run A$^*$ search using $h^{\mathrm{adm}}$. For each state $w_1^l$ that is evaluated by this first search, we update the best-encountered probability for $v=w_l$: $p^*(v) \leftarrow \max\left(p^*(v), p(w_l\vert w_{l-4}^{l-1})\right)$, where $p^*(v)$ is initialized to $-\infty$. The second time we run A$^*$ search, we use these probabilities in the heuristic: $h^{\mathrm{emp}}(w_1^l) = \sum_{v \in \mathbf{x}\backslash w_1^l} \log p^*(v)$. The heuristic $h^{\mathrm{emp}}$ is not admissible, but it is intended to give a more realistic estimate of future path cost than $h^{\mathrm{adm}}$ does, and thus reduce the fraction of search space that needs to be explored.