基于函數變換的求解SAT問題的新算法

胡顯偉 任世軍

摘要： 提出了一種基于函數變換的求解ＳＡＴ問題的新算法，這個新算法利用ＳＡＴ問題自身的特點將判定問題轉化為連續函數的求極值問題。隨機選取一組初始值，利用最速下降法求解變換后的連續函數在每個初始值鄰域內所能達到的局部極值，如果這個局部極值為０，則該ＳＡＴ問題就是可滿足的。實驗結果表明：與現有的求解ＳＡＴ問題的算法相比，基于函數變換的求解算法在求解速度、成功率和求解問題的規模等方面都有明顯的提高。