Design and Analysis of Parallel Random Search Strategies to Find a First Solution
Abstract
Many problems involve the exploration of a large state space to find a solution - examples of such problems include automatic test vector generation for digital logic circuits, the traveling salesman problem, associative search, and cryptography. In most cases it is sufficient to stop the search after the first acceptable solution is found. This paper discusses some new results concerning the negative hypergeometric distribution and applies this distribution to the analysis of "sampling without replacement" search strategies. To shorten long run times, a search can be parallelized by assigning partitions of the search space to different processors. It is shown in this paper that linear average speedup of a search for a first solution is impossible even in the absence of such considerations as communication, contention, or load balancing, and even under the most favorable partitioning of solutions in the search space.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 14, 2023
- Accession Number
- AD1195699
Entities
People
- Warren H. Jr Debany
Organizations
- Air Force Research Laboratory