共查询到20条相似文献,搜索用时 0 毫秒
1.
A temporal network is a directed graph in which each arc has a time label specifying the time at which its end vertices communicate. An arborescence in a temporal network is said to be time-respecting, if the time labels on every directed path from the root in this arborescence are monotonically non-decreasing. In this paper, we consider a characterization of the existence of arc-disjoint time-respecting arborescences in temporal networks. 相似文献
2.
3.
We present a generally applicable method for the modeling of covalent amorphous networks. The algorithm proceeds by generating random close packings of anions, followed by an optimal placement of the cations. As examples, we apply the algorithm to a-SiO2, a-Si3N4, a-SiO3/2N1/3, and a-B2O3. 相似文献
4.
本文对“0/1背包问题”采用贪婪算法、动态规划、回溯法、分枝限界四种不同方法进行求解和算法分析,并通过各种算法的实现,研究了0/1背包问题的实质。 相似文献
5.
背包问题(Knapsack Problem, KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.本文对近十余年来利用EAs求解KP的研究情况进行一个较为详细的总结,它一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面为今后进一步利用最新提出的EAs求解KP问题提供一个可借鉴的思路. 相似文献
6.
简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0/1背包问题,给出了具体的算法描述和求解过程。对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间。 相似文献
7.
8.
本文对“0/1背包问题”采用贪婪算法、动态规划、回溯法、分枝限界四种不同方法进行求解和算法分析.并通过各种算法的实现.研究了0/1背包问题的实质。 相似文献
9.
10.
多背包问题的遗传算法求解 总被引:13,自引:0,他引:13
本文提出了一种新的组合优化问题—多背包问题,并给出了它的基于0/1规划的数学模型;提出了解决多背包问题的遗传算法。该算法以目标函数加约束惩罚函数作为适应值函数,交叉算子选用了一致交叉的方法,仿真的结果表明该遗传算法在求解多背包问题上的表现是良好的。 相似文献
11.
12.
13.
林鑫 《计算机技术与发展》2005,15(10)
简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0-1背包问题,给出了具体的算法描述和求解过程.对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间,发现模拟退火算法是相对最优的算法. 相似文献
14.
In this paper, we study the online unweighted knapsack problem with removal cost. The input is a sequence of items u 1,u 2,…,u n , each of which has a size and a value, where the value of each item is assumed to be equal to the size. Given the ith item u i , we either put u i into the knapsack or reject it with no cost. When u i is put into the knapsack, some items in the knapsack are removed with removal cost if the sum of the size of u i and the total size in the current knapsack exceeds the capacity of the knapsack. Here the removal cost means a cancellation charge or disposal fee. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack minus the total removal cost occurred. In this paper, we consider two kinds of removal cost: unit and proportional cost. For both models, we provide their competitive ratios. Namely, we construct optimal online algorithms and prove that they are best possible. 相似文献
15.
16.
无限制背包问题的爬山算法 总被引:3,自引:0,他引:3
给出了一种求解整数背包问题的爬山解法 ,并对该算法的计算复杂度及最坏情形进行了理论分析 .通过与经典的求解背包问题方法的对比研究 ,给出了该算法的适用范围并展示其优越性 .数值实验表明 ,该算法简便易行 ,在其适用范围内具有计算复杂度低 ,近优程度高等优点 . 相似文献
17.
18.
收缩背包问题是标准背包问题的一个扩展,其中背包的容量为所装物品数量的非增函数。本文提出了基于分子生物技术的求解收缩背包问题的DNA算法,首先将其约束条件进行分解;然后设计一系列与物品重量相对应的寡聚核苷酸片断及其链接模板,在链接酶的作用下将它们进行链接反应,生成代表任意物品组合的DNA链;再通过基本的生物操
作筛选出可行解;最后比较各个可行解对应的目标函数值,进而得到最优解。 相似文献
作筛选出可行解;最后比较各个可行解对应的目标函数值,进而得到最优解。 相似文献
19.
20.
基于背包问题的身份认证方案 总被引:2,自引:0,他引:2
一、引言 随着计算机网络的不断扩展和信息高速公路的建设,信息的安全问题也变得十突出了,所有的信息处理系统和信息交换系统必须具备以下的安全防 相似文献