The PreOrderBestMatchProblem is a generalization of a class of problems of the following form:
Assume a set S and a binary relation <= over S which is a PreOrder?: Now assume an element X in S, and a (non-empty) set of elements Y such that for all elements Y in Y, Y is in S and X <= Y. The problem is to find the member of Y which is a "best match" for X.
We leave "best" undefined for now, other than to note a couple of trivial cases:
- If Y contains only a single element, than that is defined to be the best match.
- If Y contains X, then the answer is trivially X. (Any element is it's own best match).
Less trivial, but commonly enforced:
- If there is an element Q in Y such that for all Y in Y, Q <= Y is true, then Q is the best match. (The previous rules can be viewed as special cases of this one). In this case, Q can be said to dominate all other elements of Y. Note that there are some sets for which the <= relation might be undecideable or intractable to compute (an example is if the elements of S are predicate functions, and the <= operation is defined to mean that the truth of one function at a particular value implies the truth of the other function at the same point--the VorherrschaftsProblem).
Despite these special cases; it frequently arises that the best match is
ambiguous--there is no dominant member of
Y, in which case additional rules may come into play (dependent on the specific application). Common ways of resolving ambiguities:
- Declaring them to be erroneous.
- Imposing a secondary ordering (usually a TotalOrder) on elements of Y (this ordering may be ad-hoc), used to select between possible best matches. This secondary ordering may be defined as another relationship over S; it can also be imposed by re-defining Y to be an (ordered) tuple rather than an (unordered) set, and simply choosing the first (or last) element.
- In case where the "path length" between X and elements of Y can be determined, choosing the "closest" element of Y.
This problem is a generalization of several problems found in programming languages, such as:
Pre Order Best Match Problem