排序方式: 共有24条查询结果,搜索用时 15 毫秒
1.
2.
3.
布尔可满足性问题(SAT)是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题(k-SAT),从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O((2-2/k)n),当k=3时,最好算法时间复杂度为O(1.308n).而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题(3-RSSAT),证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O(1.890n)判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O(1.890n)精确算法,该算法与子句长度无关. 相似文献
4.
任意曲面间跟踪求交的有效算法 总被引:3,自引:0,他引:3
提出了一种基于微分方程的跟踪算法,该算法采用基于交线微分形式的跟踪公式,解决了求交中难于处理的分支问题,和已有跟踪法相比,该算法稳定性更强,效率更高,而且适用于任意参数曲面及解析曲面。 相似文献
5.
6.
网络并行计算系统中基于多处理机任务的资源调度模型 总被引:4,自引:0,他引:4
简要描述了网络并行计算系统中任务调度问题和经典的多处理机任务调度研究现状,并将两者结合到一起建立网络并行计算系统中的新型调度模型,较详细地论述了多处理机任务的定义,然后还讨论了该模型求解的近似调度策略及其近似优化问题,给出了其特例Pm|fix|Cmax问题的最优调度的时间跨度下界。 相似文献
7.
并行任务调度不论是从理论上还是应用上近年来都倍受关注。但是目前出现的大量算法很难应用于实际,基于此,论文探讨了典型的调度问题P3|fix|Cmax,这类问题是强NP-难的。论文在Goemans的研究基础上,给出了一个很简单的线性算法,构造出调度性能为9/8的半规则调度,改进了Goemans的7/6的结果。 相似文献
8.
基于组织目标的分解和分析,应用经典的统计过程控制(SPC)技术,建立了基于目标的软件过程性能定量评价模型(G-SPPAM)。通过分析组织目标(Goal)、度量指标(Indictor)和软件子过程(Sub process)之间的映射关系,实现每一个子过程的定量评价。还给出了该模型的应用方法,并结合实例分析了该模型。 相似文献
9.
独立多处理机任务静态调度问题的近似算法 总被引:1,自引:0,他引:1
研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中所有任务都是单位处理机时间的特殊情形Pm|fix,p=1|Cmax的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题Pm|fix,p=1|Cmax的√2m +1近似算法和问题Pm|fix|Cmax的2√m 近似算法,优于目前已有文献的最好结果. 相似文献
10.
黄金贵 《计算机工程与应用》2009,45(6):48-51
网格计算是网络并行计算的发展新趋势,网格系统中的分布式资源管理和调度一直是研究的热点和难点。对于网格应用作业的多资源调度问题,一个网格作业往往要分成多步骤进行,每个步骤都需要占用多个资源。首先将该问题抽象为典型的多处理机任务调度模型Pm|fix,p=1,chain|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行,而且每个任务都需要一个单位的处理时间,并根据优先关系形成链约束。该问题被证明为NP难问题。利用宽度优先技术和首次满足方法,构建了几个多项式时间近似算法,并通过模拟实验分析算法性能,实验结果显示算法是实用的。 相似文献