求解MAX-CNF问题的一种随机近似算法

摘要

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