论文部分内容阅读
已有的Johnson算法是求解组合问题的一种随机近似算法，可以用于求解MAX—CNF问题。基于该算法，提出新的随机近似算法RCNF求解MAX—CNF问题。概率推导和实验数值均表明，RCNF具有盎好的近似比和稳定的性能。在构成难可满足问题的CNF实例上，将新算法与演化算法结合，进一步提出扩展算法E—RCNF。扩展算法利用演化算法的并行性。可以在较短时间内。简单有效地求出最多可满足子句数的近似值。