zbMATH — the first resource for mathematics

Extremum-searching hierarchical parallel probabilistic algorithms. (English) Zbl 0647.68061
Summary: Considering a large finite set A together with a mapping f which takes A into a set with linear ordering, the extremum-search problem for \(<A,f>\) consists in searching for an element of A for which f attains the minimum (or maximum) value. Simple randomization or “non-idealized” parallelism are proved not to improve the situation substantially when compared with a systematical exhaustive inspection. Therefore, hierarchical parallel probabilistic algorithms for the problem in question are suggested and their time computational complexity is investigated and minimized.

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: Link EuDML
[1] W. Feller: An Introduction to Probability Theory and its Applications, Vol. I. John Wiley and Sons – Chapman and Hall, New York–London 1957 · Zbl 0077.12201
[2] U. Manber, M. Tompa: The complexity of problems on probabilistic, non-deterministic, and alternating decision trees. J. Assoc. Comput. Mach. 32 (1985), 3, 720-732. · Zbl 0631.68044 · doi:10.1145/3828.3838
[3] J. Reif: On synchronous parallel computations with independent probabilistic choice. SIAM J. Comput. 13 (1984), 1, 46-55. · Zbl 0558.68038 · doi:10.1137/0213004
[4] I. Kramosil: Hierarchical connection of probabilistic approach and parallelism in searching tasks of artificial intelligence. Aplikace umělé inteligence AI’ 87, 23-31. In Czech.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.