# Keywords/terminology for using “extra” information in search problems?

I am trying to find references on a particular idea, but I don't know which keywords to use in a google search.

the idea is: as an example, consider graph search. maybe the problem is: find a path from node $$X$$ to node $$Y$$. We can consider two versions of this problem:

1. For any node $$n$$, we can query only the information: which other nodes are connected to it?

2. For any node $$n$$, we can additionally query the information: what is the "airplane distance" between $$n$$ and $$Y$$.

Clearly, if we have the additional information from (2), we can construct a larger set of possible search algorithms, in particular, ones that are faster.

My question is: What terminology/keywords do I need to search to read about this phenomenon that some search algorithms have more "heuristic" information at their disposal than others, and can therefore employ better search heuristics?

• One might be relaxation, which is the step where the core operation of the algorithm is applied. For example in Dijkstra it's the step where you compare distances and sum up the new distance – narek Bojikian Dec 18 '18 at 12:32