0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – narek Bojikian Dec 18 '18 at 12:32
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.