\input zb-basic
\input zb-ioport
\iteman{io-port 04090815}
\itemau{Nageshwara Rao, V.; Kumar, Vipin}
\itemti{Superlinear speedup in parallel state-space search.}
\itemso{Foundations of software technology and theoretical computer science, Proc. 8th Conf., Pune/India 1988, Lect. Notes Comput. Sci. 338, 161-174 (1988).}
\itemab
[For the entire collection see Zbl 0656.00031.] When N processors perform depth-first search on-disjoint parts of a state space tree to find a solution, the speedup can be superlinear $(i.e.,>N)$ or sublinear $(i.e.,<N)$ depending upon when a solution is first encountered in the space by one of the processors. It may appear that on the average, the speedup would be either linear or sublinear. Using an analytical model, we show that if the searchspace has more than one solution and if these solutions are randomly distributed in a relatively small region of the search space, then the average speedup in parallel depth-first search can be superlinear. If all the solutions (one or more) are uniformly distributed over the whole search space, then the average speedup is linear. This model is validated by our experiments on synthetic state-space trees and the 15-puzzle problem. The same model predicts average superlinear speedup in parallel best-first branch-and- bound algorithms on suitable problems.
\itemrv{~}
\itemcc{}
\itemut{parallel algorithm; searching; state space tree; speedup; parallel depth- first search; parallel best-first branch-and-bound algorithms}
\itemli{}
\end