一种基于多级查找表的高效Huffman编码算法

本文研究了适用于数字信号处理器的一种高效的Huffman编码算法的问题.利用多级查找表建立规则,并将Huffman树分割为若干子树且为分割后的所有子树建立一个统一的查找表的方法,获得了可用较小的查找表来存储Huffman树且能对比特流进行快速解码的结果.     

顾客为子树结构的树上反中心选址问题

顾客为子树结构的树上反中心选址问题是在树T上寻找一点(位于顶点处或在边的内部),使得该点与子树结构的顾客之间的最小赋权带加数距离尽可能地大.给出了该问题的一个有效算法,其时间复杂度为O(cn+sum from j=1 to m n_j),其中n_j为各子树T_j的顶点个数,c为不同的子树权重个数,n为树的顶点数.     

字典序地生成有序根树的一个算法

§1.引言由于树的生成在计算机科学中有着重要应用,近年来许多文章研究了树的生成,其中大多数文章是讨论2分树及 k 分树的生成.研究一般有序根树的文章尚少.文献[1]给出了有序根树的一个序列表示法,并描述了一个生成有序根树的算法.文献[2]及[3]讨论了生成2分树及 k 分树的算法.本文用0,1序列表示有序根树,并给出了一个字典序地生成具有 n 个顶点的所有有序根树的算法.本文的表示法及算法与文献[1]中所提方法不同.本算法亦可用来生成具有 n 个叶子的所有2分树.它比[2]中的算法更简单.本文中未加说明的术语皆见[1].     

一些图的生成树数

图 G 的生成树是它的连通子图(子树).本文精确地计算出了一些图的生成树的数目, 例如双心轮图、双柄扇图等等.     

机助故障树分析的统一算法

本文提出一种机助故障树分析的统一算法。该算法能给出原故障树的全部模块子树,各模块子树及其对偶模块子村的不交蕴涵族,原故障树的质蕴涵族,完成常规的定量计算和某些新的定量分析。它与Willie的算法相比较功能更全也更为有效。     

最小度生成树的一种近似算法

最小度生成树问题是一个NP难问题.本文给出了求最小度生成树的一种近似算法,这种算法得到的生成树的度数比最优解至多大1.     

一种基于边交换的贪心算法求解md-MST问题

通过对最小度限制最小生成树(md-MST)问题性质进行分析,提出了一种基于边交换的贪心算法.算法先用贪心算法生成一棵生成树ST,然后对生成树ST经过边交换调整,得到满足问题约束条件的可行解,再对生成树ST进行进一步边交换优化,得到md-MST问题的最优解或接近最优解的近似解.实验证明,算法能在短对间内求出大规模顶点随机图的md-MST,是一种非常实用的求解md-MST问题的精确算法.     

改进的生成树遗传算法及其在物流配送成本优化中的应用

针对物流配送成本优化问题的特点,建立了数学模型,并对基本的生成树遗传算法进行了改进,同时详细阐述了改进的生成树编码的遗传算法在物流配送成本优化问题中的运用等关键技术.最后根据此算法设计了一个物流配送优化系统,解决了一个物流配送成本优化问题,效果良好.此系统对于中小型物流公司设计最优物流策略和降低物流成本有着很大的应用前景.     

多目标度约束最小生成树的蚁群优化算法求解

多目标最小生成树问题与度约束最小生成树问题分别是网络优化中两个NP难题,在实际中一直有着重要的应用.本文针对同时考虑多目标和度约束情况下的最小生成树求解问题,采用蚁群优化算法思想,设计了一种求解方案,并在计算机上用Delphi予以实现.经大量数值算例求解测试,验证了算法的有效性和可行性.     

次限制拟阵基的排序算法

§1 引言本文对一般的拟阵,给出在一个子集上具有次限制所有拟阵基的排序算法。著名的“greedy”算法是求连通图最小权的支撑树的好算法。在连通图上特别指定了一个顶点,求在该顶点次限制的最小权的支撑树,Glover—Klingman也给出了好算法。Burns—Haff给出了图的支撑树权的大小进行排序的生成算法,并且指出能够把它推广为拟阵基的排序算法。本文对一般的拟阵,给出在一个集上具次限制的所有拟阵基的按权的大小进行排序的生成算法。     

有向树上的可加枚举问题

作者在[1]中提出了简单生成树族上的可加枚举问题,并建立了统一的求解模式,有向树族不是一个简单生成树族,就是说,它的生成函数 A(z)=sum from n=1 to ∞(a_nz~n) (1)(a_n——具有n个节点的有向树的个数)不满足任何函数关系     

字典序地生成有序森林的一个算法

本文给出有序森林的一种序列表示法,并描述了一个字典序地生成具有n个顶点的所有有序森林的一个算法.它是[1]中算法的推广.§1 有序森林的序列表示法文献[1]给出了有序根树的一种序列表示法.本文利用[1]中的表示法给出有序森林的一种序列表示法及生成它们的算法.本文中未加说明的术语皆见[1].若F的每一个连通     

书本图与齿轮图的子树计数及渐进密度特性分析

图的子树数拓扑指标对指导可靠性网络设计和分析化合物的物理与化学性质均具有重要意义.本文基于生成函数、结构分析及矩阵映射的方法给出书本图B_(n,2)(n≥2)和齿轮图G_(n,1)(n≥3)的子树数生成函数,并分析了B_(n,2)(n≥2)和G_(n,1)(n≥3)的子树密度的渐进特性,本研究为探索复杂圈图和分子的结构新特性提供了新的视角和方法.     

K_（1，r）－free图的次限制树多项式算法

设Ｇ＝（Ｖ，Ｅ）为一连通图，ｄ＞０整数．Ｇ中存在生成树Ｔ，使得Δ（Ｔ）小于ｄ吗？这一问题已被证明是ＮＰ－完全的，故不太可能有多项式解法．本文证明了当Ｇ是Ｋ１，ｒ－ｆｒｅ时，则有Ｏ（ｎ２）的算法求出Ｇ的生成树Ｔ，使Δ（Ｔ）≤ｒ，并用一个例子显示了这一结果是最好可能的     

小波树逼近及其应用

利用“构造性贪婪算法(CGS)”构造目标函数的小波树逼近. 首先定义了一个函数类, 对此函数类中的每个函数, 由CGS生成的分片多项式逼近都具有给定的收敛阶. 其次通过研究所定义函数类的嵌入性质讨论了该函数类和其他已知函数空间的关系. 在小波树逼近领域, 给出了使小波树逼近达到最优收敛阶的一个充分条件. 最后证明, 如果树结构是用CGS生成的, 则相应的小波树逼近具有最优收敛阶.     

在有向网络中寻找最小支撑入树的计算方法

本文研究了有向网络中支撑入树的性质 ,提出了在有向网络图中寻找以某一指定点为根的最小支撑入树的一种较简便的算法 ,并给出了应用该算法的一个实际算例     

基于最小生成树的二维图像深度分配

随着三维视频资源需求的增长,二维转三维(2D-3D)转换技术成为三维(3D)图像处理技术研究的焦点.由于2D视频中没有包含深度信息,2D-3D转换技术的关键在于2D视频中深度信息的提取.提出一种基于最小生成树的二维图像深度分配方法.利用最小生成树的方法对图像进行分割,然后先验理论对分割区域进行深度分配以产生合适的深度图像.最小生成树的方法不需要设置较多参数,对于不同场景的图像有较强的自适应性,而且最小生成树算法具有算法简单,运行速度快的优势.     

预报式模糊控制器及其应用

本文是文［１］的继续与发展，本文发现，在经典的比例微分式模糊控制（ＣＦＣ）算法中，隐含着一种预报控制的思想。因此，其矩阵形式的控制表完全可简化为等价的向量形式。据此，本文提出了一种预报式模糊控制算法ＰＦＣ。对ＰＦＣ作过大量的仿真试验，并将其应用于一个造纸过程控制系统。结果表明，ＰＦＣ具有内存少，收敛快，计算简便，精度高等优点。     

基于模拟植物生长算法构造Steiner最优树问题研究

Steiner最优树问题是指对于给定区域内的点集,通过引入Steiner点集将区域中的点连接并保证连通的网络达到最小.该问题已成为经典的优化组合问题之一.提出一种基于模拟植物生长算法生成Steiner最优树的连通算法来实现网络连通.通过对实例的实验及结果分析,结果表明本算法不仅可获得最优解,精度和性能也有提高,明显优于其它方法.     

铁路客运网络列车开行方案优化模型的列生成算法

列车开行方案的设计是铁路旅客运输组织规划中的一个重要环节。本文首先给出了一个综合考虑铁路旅客运输的经济效益和公共服务性的优化模型,以铁路旅客运输的公共效益最大化为目标,对整个铁路客运网络上不同始发-终到和不同停站方式的列车开行方案进行优化。然后提出了一个求解此模型的启发式列生成算法,该算法与标准列生成算法相比,可以减少迭代次数并缩短收敛时间。最后给出一组利用随机生成的网络和需求进行求解的算例,验证本算法可以在较短时间内求解较大规模的铁路网络列车开行方案优化问题,并能有效缩小问题规模。