The optimal value function is an evaluation function which encapsulates complete knowledge of the best expected search outcome attainable from each state:
Such an evaluation function is ideal in that a greedy local search with respect to will always make the globally optimal move. This section reviews the literature on computing , and motivates and describes our new approximation algorithms for this problem.