Method for solving enumerative search problems using message pas

Details Method for solving enumerative search problems using message pas Method for solving enumerative search problems using message pas

1993-05-24

1996-07-16

Treat, William M.

Boots, shoes, and leggings

39520003, 395800, 364DIG1, G06F 15163

Patent

active

055375936

ABSTRACT:
A method and apparatus for solving enumerative search, graph search or combinatorial optimization problems using parallel digital processors. Various nodes, representing decision points in the problem, are distributed among a plurality of digital processors. The nodes are expanded and bound values for the nodes are communicated among the processors. Non-productive solution parts are pruned to eliminate unnecessary expansion of the state space. Updated bound values are communicated in both directions along the search graph and a plurality of messages are developed to provide communication in a loosely coupled processor environment.

REFERENCES:
patent: 4210962 (1980-07-01), Marsh et al.
patent: 4218582 (1980-10-01), Hellman et al.
patent: 4466060 (1984-10-01), Riddle
patent: 4495559 (1985-01-01), Gelatt, Jr. et al.
patent: 4575798 (1986-03-01), Lindstrom et al.
patent: 4583164 (1986-04-01), Tolle
patent: 4719571 (1988-01-01), Rissanen et al.
patent: 4837735 (1989-06-01), Allen, Jr. et al.
patent: 4860201 (1989-10-01), Stolfo et al.
patent: 4905144 (1990-02-01), Hansen
patent: 4918621 (1990-04-01), Nado et al.
patent: 4949243 (1990-10-01), Mohamed Ali et al.
patent: 4982340 (1991-01-01), Oyanagi et al.
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5072379 (1991-12-01), Eberhardt
patent: 5170393 (1992-12-01), Peterson et al.
Dehne et al., "Parallel Branch and Bound on Fine-Grained Hypercube Multiprocessors," IEEE, 1989, pp. 616-622.
Megiddo, N. "Applying Parallel Computation Algorithms in the Design of Serial Algorithms", Journal of the Association for Computing Machinery, vol. 30, No. 4, Oct. 1983, pp. 852-865.

Affiliated with

Also associated with

Rating

Method for solving enumerative search problems using message pas does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for solving enumerative search problems using message pas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for solving enumerative search problems using message pas will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1792712