DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
AD1195699
Title:
Design and Analysis of Parallel Random Search Strategies to Find a First Solution
Report Date:
2023-03-14
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 Type:
Conference:
Journal:
Pages:
7
File Size:
1.26MB
Contracts:
Grants:
Distribution Statement:
Approved For Public Release
