Application of game-tree searching algorithms to parallel selection

点击翻译按钮获取中文摘要

This research is concerned with the computational complexity of parallel selection problems, with specific interests in applying game-tree searching algorithms to obtain new results. Let U(n, t) be the minimum number of parallel comparisons required to select the t largest of n elements in the worst case on the parallel disjoint comparison model. Similarly, V(n, t) and W(n, t) are defined to be the minimum number to select the t-th largest element and the sorted t largest elements, respectively. We derive a new upper bound of U(n, t) for t 【greater than or equal】 4. This is proved by theoretical analysis, along with computational results obtained by our searching algorithms. Among other new techniques, a distributed shared-hashing method is designed and implemented on a parallel PC cluster. We also derive several upper, lower and optimal formulas of U(n, t) for some particular values of t. We show several relations between U, V and W, and make a table of the values of U, V and W for n 【less than or equal】 16. In this table, several nontrivial optimal values are determined. In the proof, our searching programs are also used. Finally, we show some results in other problems than selection by applying our searching algorithms.