论文摘要
在计算机科学的理论领域中,有一个尚未解决的著名的难题：NP（Non-deterministic Polynomial）问题,也就是多项式复杂程度的非确定性问题。一些计算问题可以通过公式的推导得出计算结果,这些问题被称之为确定性的。但是有些问题是无法通过计算来得到结果的,只能通过间接的方式,比如“猜想”来得到结果,这一类问题就称之为非确定性的。虽然非确定性问题没有算法可以为其来解答,但是对于某个可能的结果是正确的还是错误的仍然是有算法可以判断的。如果这个算法可以在多项式时间内计算出来,该问题就叫做多项式非确定性问题。而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,该问题就叫完全多项式非确定问题。完全多项式非确定性问题可以用穷举法得到计算结果,但是这样算法的复杂程度是指数级了,因此计算的时间随问题的复杂程度成指数倍的增长,很快便变得不可计算了。为了研究这个问题,本篇论文从对NP完全问题研究的发展和国内外情况入手,提出并研究MANIP网络结构——一个处理完全多项式非确定问题的并行机。接着引出分支界定算法的概念,通过对分支界定算法的前序准备工作的筹备以及算法本生基本特征的研究分析得出单处理系统是用来解决广泛多样的NP完全问题最通用的技术,并且在NP完全问题中融入并行的思想,得出并行的分支界定算法。并行分支界定算法要求组合排序和合并,但是一个普通内存进行大量处理器的排序可能成为系统的瓶颈,针对这一问题,论文对并行分支界定算法的两种体系配套支持进行分析与讨论,并以urn模型为实例,对该实例的性能做出分析。通过对系统中完整式分布下限的复杂度的计算与分析,进行硬件优先队列的网络优化,最后得出一个分布式智能系统,以便可以进行分布式的排序,从而达到MANIP网络体系在处理NP完全问题效率上的改进。