Printer Friendly

Computing by committee: sharing searches.

Teamwork underlies a wide range of human activities, from the founding of a company to assemble and market a new product to the gathering of a group to solve a problem. Teams provide a means of sharing not only the work but also the information gleaned by individual members as they pursue specific tasks.

Experience suggests that for solving certain kinds of problems, cooperation can substantially improve performance, permitting the completion of these tasks faster than could be accomplished by an individual or a group in which members work in isolation. The same principle may apply to solving problems by computer, especially in situations where there are no efficient, step-by-step procedures, or algorithms, available, and where finding the answer requires searching through a large number of possibilities.

Using computer simulations of cooperative problem solving, a team of computer scientists at the Xerox Palo Alto (Calif.) Research Center has now provided some of the first quantitative estimates of the degree to which information sharing can speed up searches for answers to certain types of problems. Scott H. Clearwater, Bernardo A. Huberman and Tad Hogg describe their findings in the Nov. 22 SCIENCE.

As a simple test problem, the reserchers chose a type of cryptarithmetic puzzle that requires finding the digits that correspond to certain letters of the alphabet so that the number represented by the given words add up correctly. For example, for what digits would the sum DONALD+GERALD = ROBERT be true? This particular problem has one solution, which is given by A = 4, R = 7, and so on.

Cooperation in solving this puzzle takes the form of reading and writing hints on a central "blackboard" accessible to all the "individuals" (in this case, computer programs) working on the puzzle. Hints consist of lists of letter-digit assignments that add up correctly for at least one column in the given sum. Starting at different points, each individual constantly checks the blackboard for hints, randomly generating and testing new combinations whenever all hints are exhausted or none is available.

Compared with noncooperative strategies, such searches bring a striking overall improvement in performance, the reserchers found. The actual speedup varies greatly from run to run because the time needed to solve the puzzle depends strongly on the quality of the first few hints posted on the blackboard. Nonetheless, shared information reduces the number of possibilities that need to be considered by focusing the problem solvers on more plausible courses of action.

In computer science, this work suggests that instead of seeking a single, ideal algorithm for solving a certain problem, a better strategy would involve developing a set of relatively simple computer programs that work on the program concurrently while communicationg their partial results. "You might be better off sometimes having a bunch of dump processes cooperating," Huberman says.

"These results also have implications for problem solving in general," he adds. "In a sense, this is a simple simulation of a model of something like a society."
COPYRIGHT 1991 Science Service, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1991, Gale Group. All rights reserved. Gale Group is a Thomson Corporation Company.

Article Details
Printer friendly Cite/link Email Feedback
Author:Peterson, Ivars
Publication:Science News
Date:Nov 30, 1991
Words:494
Previous Article:Many doctors would shun AIDS patients.
Next Article:Fickle fields: EMFs and epidemiology.
Topics:


Related Articles
Smart stops on the Web.
NOVEMBER CONFERENCE TACKLES TEXT RETRIEVAL SYSTEMS.
SUPERINTENDENT CHOICES SLIM FEW QUALIFIED WANT TO RUN VAST DISTRICTS.
CRITERIA SOUGHT FOR NEW SUPERINTENDENT.
PANEL TO HELP FIND SUPERINTENDENT.
PANEL NAMED TO PICK SCHOOL SUPERINTENDENT.
NATIONAL SEARCH URGED FOR HEAD OF LAUSD.
Transition at the top: an ending is also a beginning. (On Leadership).
DOWNLOADS A THREAT TO SECRETS.
The art of the executive search: a search firm can help universities avoid trouble when trying to fill a high-level post.

Terms of use | Copyright © 2016 Farlex, Inc. | Feedback | For webmasters