共查询到10条相似文献,搜索用时 15 毫秒
1.
2.
3.
众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质. 相似文献
4.
分布式环境下多任务调度问题的分析与求解 总被引:6,自引:0,他引:6
将约束条件归纳为任务约束、链路约束和资源约束,在允许任务复制的情况下,建立了问题的约束与目标的完整数学模型;提出了一种基于任务复制的模拟人类社会中关系演化过程的簇调度算法IREA,包括前沿调度、动态分簇和分离图三个子算法.IREA采用全新的优先级规则,定义了关系数、依赖度、归并度等表示簇的优先级.通过对两个经典算例的计算,发现IREA能求出比算例所在文献算法所得解更优的解;对MJD算例,还得到了一个不同于原文献所给理论最优格局的一个新的最优格局. 相似文献
5.
停机位分配问题的顶点着色模型及算法 总被引:1,自引:0,他引:1
给出了停机位分配问题顶点着色模型及其分解算法.通过改良一种时间冲突算法,构建了航班使用停机位的时间冲突集合.以"先到先服务"原则为基础,把停机位分配问题转化为顶点着色问题,并建立了相应模型.利用笔者独创的分解算法,停机位的作业能力可得到改善.算法的计算复杂度为O(n2).该算法的特点在于:1)将顶点、颜色划分为若干个不同等级的集合;2)将顶点按照所属集合的等级、度进行分解,得到顶点的分解序列.在用一种颜色ck(1≤k≤K;K是可用颜色数)给顶点着色时,优先给这样一个顶点着色:该顶点能被着ck色,且其分解序列号最大.最后将该算法应用于一个算例,得到了最优解. 相似文献
6.
7.
复杂网络中的社团发现和探测是当前复杂网络分析领域中的一个热点研究问题,并且具有非常广泛的应用前景。但是,传统的社团划分算法主要以无向、无权网络为对象进行分析,不能够适用于现实世界中更多的有向网络、赋权网络等。以有向网络为研究对象,研究其中的社团划分算法。鉴于前人提出的有向网络中社团划分算法存在着计算时间复杂度问题,引入模拟退火算法对其进行改进,并在改进算法中考虑了节点的网络结构属性。通过对不同规模的计算机生成的有向网络进行算法测试,验证了本文算法的正确性。最后,对一个实际复杂网络进行了社团划分,进一步验证了算法的有效性。 相似文献
8.
针对现有虚拟网络映射存在开销较大、资源利用不够合理的问题,提出了一种基于二分图最优匹配的虚拟网络映射算法。首先以虚拟节点和物理节点为顶点构建二分图,将节点映射问题转化为二分图最优匹配问题;其次将节点资源评价最高的物理节点与节点需求评价最高的虚拟节点优先匹配,并利用Kuhn-Munkres算法求解二分图最优匹配,依据匹配结果进行节点映射;最后利用 k-最短路径算法实现链路映射。实验表明,与以往的映射算法相比,提出的映射算法在保持较高映射成功率的同时,提高了长期收益开销比,且资源利用更加合理。 相似文献
9.
10.
本文提出了若干受顶点数限制的最短路问题。引入非支配路的概念,用双标号和取字典序最小方法,给出求解问题的多项式算法。 相似文献