| In the field of computer science theory, there is a famous unsolved problem:NP problem (Non-deterministic Polynomial), is a non-deterministic polynomial complexity of the problem. Some computational problems can be obtained through the formula of calculation, these problems are called deterministic. But some problems can not be calculated to get the results, only through indirect means, such as "conjecture" to get the result, this type of problem is called non-deterministic. Although non-deterministic algorithm for the problem is not answered, but a likely outcome is right or wrong is still a method can be judged. If this algorithm can be calculated in polynomial time, the problem is called non-deterministic polynomial problem. And if all the possible answers to this question, can all be correct in polynomial time, then checking whether or not, the problem is called non-deterministic polynomial complete problems. Nondeterministic polynomial complete problems can be calculated using exhaustive method, but the complexity of this algorithm is exponential, so the calculation of the time with the complexity of the issues increase exponentially, and soon becomes incalculable.In order to study this problem, this thesis research from the development of NP complete problems start at home and abroad situation, proposed and studied MANIP network structure-a non-deterministic polynomial complete problems dealing with parallel machine. Then leads to the concept of branch and bound algorithm, branch and bound algorithm by pre-order the preparation and the preparation of the basic characteristics of the algorithm of Benson draw a single processing system is used to solve a wide variety of NP complete problems are most common technology, and NP complete problem in parallel in the integration of ideas, draw a parallel branch and bound algorithm. Parallel branch and bound algorithm requires that the combination of sorting and merging, but an ordinary sort of memory for a large number of processors may become the bottleneck of the system, to solve this problem, the paper parallel branch and bound algorithm for the two systems support the analysis and discussion of matching, and urn model as an example, an analysis of the performance of the instance. Integrity of the system by Distributed limit the complexity of the calculation and analysis, hardware priority queue of network optimization, and finally arrive at a distributed intelligent system that can be distributed to sort, so as to achieve MANIP network system in dealing with NP-issue efficiency improvements. |
