Application of game-tree searching algorithms to parallel selection

这项研究关注并行选择问题的计算复杂性，特别关注应用博弈树搜索算法来获得新的结果。设U(n，t)是在并行不相交比较模型的最坏情况下选择n个元素中最大的t个元素所需的最小并行比较次数。类似地，V(n，t)和W(n，t)被定义为分别选择第t个最大元素和排序的t个最大元素的最小数目。对于t[大于或等于]4，我们得到了U(n，t)的一个新的上界。理论分析和我们的搜索算法得到的计算结果都证明了这一点。在其他新技术中，一种分布式共享散列方法被设计并在并行PC集群上实现。对于某些特殊的t值，我们还导出了U(n，t)的几个上、下、最优公式，证明了U、V和W之间的几种关系，并制作了n[小于或等于]16时U、V和W值的表。在这个表中，确定了几个非平凡的最佳值。在证明中，我们的搜索程序也被使用了。最后，将我们的搜索算法应用于选择以外的其他问题，给出了一些结果。

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.