排序方式： 共有29条查询结果，搜索用时 15 毫秒
1.
2.
旅行售货员问题(Traveling salesman problem)是计算机算法中的一个经典的难解问题,已被证明是一个NP-C(Nondeterministic Polynomial-Completeness)问题,其计算复杂度O(n!),无法找到一个多项式算法解决此类问题。本文利用最优化理论中的模拟退火法,简述了TSP问题的近似算法。 相似文献
3.
本文主要研究基因无方向的基因组重排的反转排序问题.本文算法基于断点图的概念,给出一个时间复杂性为O(maxb3(π),nb(π)),空间复杂性为O(n)的求解近似最优解的算法,其中n为基因组中基因个数,π=(π1,π2,...πn)表示n个基因的一种排列,b(π)表示排列π中的断点数.数据试验的结果表明,该近似算法可以求得较好的结果. 相似文献
4.
主要研究了一种带拒绝费用的排序问题。目标函数是在不超过总拒绝费用阀值的前提下使最大完工时间最小。首先,证明了该问题是N P-难的;然后我们针对这个问题设计出了伪多项式时间的动态规划算法,并给出了FPTAS。 相似文献
5.
王骁力 《南阳师范学院学报》2008,7(12)
把定义在一个圈上的超图的每个超边映射为这个圈的一条路,每条超边的顶点均在对应的映射中,要求使圈中的任一边经过的路的最大次数最小,称此问题为超图在圈中的最小嵌入问题.将此问题归结为最近串选取问题,从而证明该问题存在多项式时间近似算法. 相似文献
6.
矩形件排样优化问题是一个多目标优化问题,一方面要考虑到材料的利用率,另一方面要考虑到生产时的下料效率,而且还要满足“一刀切”的工艺要求。在基于最低水平线的搜索算法的基础上,提出了一种新的矩形排样算法,结果证明了该算法是灵活和有效的。 相似文献
7.
在基于802.16j的无线中继网络中,考虑路由和调度的联合优化问题,最小化系统总调度时间. 首先采用线性规划的方法建立路由,进行链路业务速率分配,然后基于平移和交换思想提出一种链路调度算法. 理论分析证明所提算法的性能在最坏情况下,不会超过最优性能的1.5倍. 仿真结果表明,所提算法的平均性能非常接近最优性能. 相似文献
8.
给出了在实数范围内求解多背包约束条件下下模集函数最大值问题的一种改进的近似算法,是MaximSviridenko所给出的整数范围内求解单背包约束下下模集函数最大值的扩展.该算法的时间复杂性为:O(kn4),其性能保证为(1-e-1/D). 相似文献
9.
2004年孙春玲等研究了一维装箱问题,给出了一个近似程度最好的近似值为3/2的近似算法-交叉算法.遗憾的是他们的交叉算法的近似值分析是错误的,本文通过两个反例说明了他们的错误所在,并给出一个正确的近似值分析. 相似文献
10.
唐庆晨 《济宁师范专科学校学报》2008,29(6):31-34
本文主要研究了平行机上时间一致时极小化工件配送时间的分批排序问题,该问题是传统的分批排序与当代的物流相结合而产生的一类新的问题.一般情况下当工件有不同的到达时间时该问题是强NP-难的,但对工件有有限个到达时间及机器台数有限时,若所有的输入数据均为整数,本文给出了问题的伪多项式时间算法,从而说明了在这种情况下问题不是强NP-难的.当输入数据是有理数时,本文给出了问题的FPTAS算法.并给出了时间一致时一般情形的PTAS算法. 相似文献