排序方式: 共有47条查询结果,搜索用时 15 毫秒
1.
一个时延约束的动态组播路由算法 总被引:1,自引:0,他引:1
分析了时延约束的动态最小代价组播路由问题,然后基于贪婪思想设计了一个动态组播树生成算法DCDG(Delay—Constrained Dynamic Greedy Algorithm),用于在动态环境下构造时延约束的低代价组播树。该算法通过节点动态贪婪地选择满足时延约束的最短路径加入组播树来降低代价;若时延不满足要求,则通过合并DDSP(Destination-Driven Shortest Path Algorithm)最小时延路径来产生一个满足时延约束的低代价组播树。仿真实验表明:DCDG算法动态生成的组播树代价较低、性能稳定,而计算复杂度仅为O(n);在严格的时延约束下会话成功率高。 相似文献
2.
一种基于禁忌搜索方法的作业车间调度 总被引:2,自引:0,他引:2
提出了一种解决作业车间调度最短完工时间问题的启发式算法.该算法中采用了变禁忌表长度策略的禁忌搜索方法.在禁忌搜索过程中利用完工时间(makespan)的一个下界作为判断一个解好坏的辅助量,由于得到该下界所需的计算量远远小于完工时间的,因此大大地减少了禁忌搜索过程的计算时间.从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,得到了比当前没有使用转换瓶颈技术的最好的禁忌搜索算法之一的TSAB算法更好的结果. 相似文献
3.
给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质.解决了Hamming距离下逆问题(改进问题)中的部分问题,有助于设计出更多的求解Hamming距离下单位型树型网络最短路改进问题的算法. 相似文献
4.
研究了新工件到达锁定初始调度的单机重调度问题.即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完毕,形成初始调度且已锁定,此时有一组释放时间为零的新工件到达,且需要插入初始调度进行加工,其优化目标为最小化新工件的完工时间和.文中研究了新工件的加工过程可中断和新工件的加工过程不可中断,共2类新工件到达锁定初始调度的单机重调度问题.分析了重调度问题的复杂性,针对第一类重调度问题提出了多项式算法并证明了其最优性.证明了第二类重调度问题为NP完全问题,提出了一个多项式算法,并证明了该算法的有效性和最优解的特征,解决了企业实际问题并进一步丰富了重调度理论. 相似文献
5.
将拟物方法与邻域搜索过程结合,得到求解不等圆Packing问题的拟物型邻域搜索算法(QP—NS).拟物方法用于连续优化,可从任一初始格局收敛至对应的局部最优格局;邻域搜索过程迭代地将当前格局替换为其邻域中的最优格局,直至无法继续改进当前格局为止.QP—NS可在不严重破坏当前格局的前提下稳定地改进当前格局,鲁棒性较强.基于14个国际公开算例的计算实验表明:QP-NS可在60S内改进10个算例的此前最优解,并与其余4个算例的此前最优解持平. 相似文献
6.
TSP组合优化问题随着问题规模的增大,其潜在解的搜索空间增长速度比指数函数增加的速度还快.TSP问题的NP-hard使得求解这些问题的最优解非常困难.提出了通过改进经典遗传算法来求解TSP问题近似解的一个算法.仿真结果验证了该算法的有效性. 相似文献
7.
姚朝灼 《福州大学学报(自然科学版)》2001,29(1):8-11
设计了解顶点覆盖问题的贪心算法 ,并证明其相对比率 η≤H(d) ,d为图中最大的顶点度数 ,H(d) =∑1/ j(j =1,2 ,…… ,d) .当d ≤ 3时 ,解的精确度有明显改善 . 相似文献
8.
图着色问题是图论中比较热门的NP难问题之一。针对该问题,有许多启发式求解算法,但都存在求解的质量不高,计算时间较长等问题。近些年提出的膜进化算法,在处理NP难问题中展现出了独特的优势。基于膜进化算法框架,提出了解决图着色问题的膜进化算法,把图着色问题和膜结合,设计了复制、融合、分裂、溶解、融合分裂、禁忌搜索6种膜进化算子。这些算子在演变的过程中使膜和膜结构发生进化,从而找到更优解,最后求得解决方案。在DIMACS的40个挑战数据集上面进行了实验,与3个最新的图着色算法比较的结果表明:在保证解的质量的情况下,文中提出的膜进化算法能有效降低求解的时间,其中有58%的实例占优。 相似文献
9.
Using a small quantity of DNA molecules and little experimental time to solve complex problems successfully is a goal of DNA computing. Some NP-hard problems have been solved by DNA computing with lower time complexity than conventional computing. However, this advantage often brings higher space complexity and needs a large number of DNA encoding molecules. One example is graph coloring problem. Current DNA algorithms need exponentially increasing DNA encoding strands with the growing of problem size. Here we propose a new DNA algorithm of graph coloring problem based on the proof of four-color theorem. This algorithm has good properties of needing a relatively small number of operations in polynomial time and needing a small number of DNA encoding molecules (we need only 6R DNA encoding molecules if the number of regions in a graph is R). 相似文献
10.
We address the problem of optimizing a distributed monitoring system and the goal of the optimization is to reduce the cost of deployment of the monitoring infrastructure by identifying a minimum aggregating set subject to delay constraint on the aggregating path. We show that this problem is NP-hard and propose approximation algorithm proving the approximation ratio with In m 1, where is the number of monitoring nodes. At last we extend our modal with more constraint of bounded delay variation. 相似文献