Decomposable Probability-of-Success Metrics in Algorithmic Search

There are three components to a search problem. The first is the finite discrete search space, Ω, which is the set of elements to be examined. Next is the target set, T, which is a nonempty subset of the search space that we are trying to find. Finally, we have an external information resource, F, which provides an evaluation of elements of the search space. Typically, there is a tight relationship between the target set and the external information resource, as the resource is expected to lead to or describe the target set in some way, such as the target set being elements which meet a certain threshold under the external information resource. Within the framework, we have an iterative algorithm which seeks to find elements of the target set, shown in Figure 1. The algorithm is a black-box that has access to a search history and produces a probability distribution over the search space. At each step, the algorithm samples over the search space using the probability distribution, evaluates that element using the information resource, adds the result to the search history, and determines the next probability distribution. The abstraction of finding the next probability distribution as a black-box algorithm allows the search framework to work with all types of search problems.