论文部分内容阅读
机构运动链的构型自动综合一直为众多机构学者研究的热点,目前的构型综合方法都需要伴随大量同构判别以及刚性子链检测。其中,同构判别问题还未被证明是P问题或NP问题,但由于近年来大量机构学以及图论学者的努力,同构判别已取得了突破性进展,部分学者提出了较有效的同构判别算法。而刚性子链问题可规约为子图同构问题,实质上是个NPC问题,理论上无多项式复杂度算法,且较同构判别而言,刚性子链方面的国内外文献较少,使得刚性子链检测算法的研究大大滞后于同构判别的研究,最终导致机构运动链构型综合方法受到刚性子链检测算法的制约而效率低下。因此对运动链构型综合中刚性子链的研究需得到广泛的重视。本文针对于构型综合中现存的问题,给出了一种新的反映运动链环路信息的数学描述:素数积序列,该序列不仅能反映环路的顶点信息也能反映环路的边的消息。在此基础上提出一种基于回路组合的新的刚性子链快速检测算法,该算法是将图分解为一组基本回路,然后将基本回路按照一定规律进行组合,生成一种新的数据结构:稳定配置状态生成树,遍历该树图,进行刚性子链检测。对于同构判别,对混合图中的赋权以及方向分别用素数进行区分,运用同构判别的邻接矩阵动态修改法,完善了赋权混合图的同构判别算法。最后,针对于叠加杆组法的缺陷,提出了一种新的无需刚性子链检测的构型综合算法,且能综合出叠加杆组综合方法无法综合的构型,该算法需将图布置成一封闭圆环以及若干二副杆,在圆环上叠加二副杆,每叠加一次依据“二副杆定理”进行刚性子链检测,直至二副杆全部叠加完毕,算法复杂度为多项式级别。并给出了300杆单自由度不含刚性子链运动链的部分图谱。利用面向对象技术开发了机构运动链的构型自动综合辅助软件,为运动链构型综合提供了新的辅助工具。