kumar@uunet.UU.NET (Vipin Kumar) (06/29/88)
Unversity of Texas, Computer Science Department Colloquium:
Searching and Parallelism
Harold Stone
IBM TJ Watson Research Center
(hstone@ibm.com)
Problems that involve searching are commonly found in Operations Research
and Artificial Intelligence applications. They tend to be rather costly,
and in the worst case the cost per solution grows exponentially in the size of
the problem.
One approach to solving such problems has been to use paralllelism. In this
talk we show where parallel computation is very costly and inefficient, and
where it holds promise. The major difference in the two cases is whether
or not each parallel process produces useful information. In some cases
most of the information obtained is redundant and very little is actually
useful in spite of many processors expending a massive number of cycles to
obtain the redundant information.
An alternate approach is to seek efficient search techniques for serial
computers. We show an example in which a simple search strategy produces
a solution the N-Queens Problem for N = 96 extremely fast, over 50 orders
of magnitude faster than a lexicographic search.
Time: WEDNESDAY, JUNE 29th at 11:00am-noon, coffee at 10:30am
Place: Faculty Lounge, TAY 3.128.
Host: Vipin Kumar.