基于任务分配与调度的GSAT算法求解3-SAT问题
【出 处】:
【作 者】:
付慧敏
[1]
徐扬
[2]
何星星
[2]
宁欣然
[1]
【摘 要】基于不同分配策略的云计算任务调度以及任务分配与调度的主要目的,提出了一种新的算法-求解3-SAT问题的基于任务分配与调度的GSAT算法.该算法将3-SAT问题中的每一个变量形成一个任务,在GSAT算法的基础上,引入任务分配与调度指导贪心搜索;同时,在保留原有贪心搜索的前提下,根据任务分配与调度的思想和3-SAT问题的特点,设计了两种新的策略-分配策略和调度策略共同完成整个贪心搜索过程.以标准的SATLAB库中变量个数从20~250的3 700个不同规模的标准Uniform Random-3-SAT问题对新的算法的性能进行了合理的测试,并与高效和普通性能改进的GSAT算法的结果作了比较,结果表明,该算法具有更高的成功率和更少的翻转次数.
相关热词搜索: GSAT算法 贪心搜索 任务分配与调度 3-SAT问题 分配策略 调度策略
上一篇: 基于CUDA的弱可压SPH流体建模与仿真
下一篇: 基于拟态计算机的SHA512算法高吞吐量实现