资源受限最小赋权树形图的一种贪婪分解启发式算法

资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.     

双权树形图的多项式算法

本文根据—个实例建立了在赋双权的有向图中求带参数的双权树形图的网络模型，通过求解一系列的问题P2(λ)，我们得到了求解该问题的多项式算法。     

两类网络连接问题中的最小费用算法及其应用

利用MergeSort算法对加权图中任意两点之间的权值进行排序,把这些权值从小到大进行排列放在一个队列,再利用Kruskal算法求该队列的最小生成树,并将该方法运用于城市交通网络的费用计算;而对于供水管道铺设的最小费用问题可通过最小树形图算法来解决。     

一类有理时变线性系统的齐次扩容时变精细算法

就一类特殊的非周期有理时变线性系统，突破这类问题常用的“区间精细算法”，设计出一种“一步计算，终生使用”型齐次扩容时变精细算法（HHPD—P）．这一算法不仅避免了HHPD—F算法中的矩阵求逆，计算量小，还易于推广、实现．两个典型算例表明，该算法的数值结果令人满意．     

TD-SCDMA中联合检测的块傅立叶算法

TD-SCDMA已被ITU和3GPP批准为第三代移动通信国际标准之一，而联合检测是TD-SCDMA中的一项关键技术，它可以等效为一个求最小二乘解的问题，由于其中涉及的数据繁多，使得计算量十分巨大。目前的一些算法(如Cholesky算法、Schur算法及Levinson算法等)充分利用了其系统矩阵的块Sylvester结构来减少计算量，研究了一种能更显著减少联合检测计算量的方法——块傅立叶算法的算法复杂度，并在算法复杂度方面与其他几种算法进行比较，展示其有效性。     

两个图算法的改进

Minty算法和Mayeda—Seshu算法是求无向连通图树清单的两个直观算法,它们都比矩阵算法节省计算时间。然而,它们仍然较复杂。本文分别对这两个算法提出了改进措施,大大降低了计算复杂性。改进后的算法既简单又直观易懂。对于Minty算法,我们提出了一个不完全算法;对Mayeda—Seshu算法,我们则避开了求基本割集这一复杂步骤。     

弧约束最优树形图问题

本文给出了求弧约束最优树形图的一个有效算法。     

TD-SCDMA中联合检测的块傅立叶算法

TD-SCDMA已被ITU和3GPP批准为第三代移动通信国际标准之一,而联合检测是TD-SCDMA 中的一项关键技术,它可以等效为一个求最小二乘解的问题,由于其中涉及的数据繁多,使得计算量十分 巨大。目前的一些算法(如Cholesky算法、Schur算法及Levinson算法等)充分利用了其系统矩阵的块 Sylvester结构来减少计算量5研究了一种能更显著减少联合检测计算量的方法——块傅立叶算法的算法 复杂度,并在算法复杂度方面与其他几种算法进行比较,展示其有效性。     

区间精细算法与长效精细算法的对比研究

如何应用精细算法求解非齐次或非线性问题是计算力学中的热点问题，通常采用区间精细算法，但这一方法的精细传递矩阵与t步长的区间有关，计算量很大．能否设计出“一次计算，终生使用”的长效精细算法是一个倍受关注的问题，尤其是针对非线性的情况．以Burgers方程为模型设计出一种能解决二次非线性困难的长效精细算法．这类技巧不难推广至一般的二次非线性PDE（偏微分方程），且有广泛的应用，还建立了相应算法的基础理论与误差分杯两个算例表明，计算结果十分令人满意．     

简单凹多面体的Minkowski和

在欧几里德三维空间中,求两个多面体的Minkowski和是一项重要的几何操作,它等同于求两个多面体中所有点的矢量和。本文在之前提出的简单凹多边形的凸剖分算法基础上,给出了基于多面体剖分的简单凹多面体的Minkowski和算法。分析表明,该算法由于减少了计算Minkowski子和的数目,从而能够提高整个求和算法的速度。