胡顯偉 任世軍

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