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

Question

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?

Answer 1

Such search algorithms would generally be called informed search algorithms (or methods, techniques, etc.), or simply heuristic search algorithms. We might also call them guided search algorithms.

An example would be A* search, which uses precisely what you call "airplane distance" (more commonly referred to as the straight-line distance) as a heuristic.

Best-first search techniques would be somewhat closely-related, but they may have a slightly different meaning (they may, for example, use statistics / information gathered earlier during the same process for guidance during a later part of the search process, rather than heuristic domain knowledge given a priori).