求解約束滿足問題的MDDc和STR3算法
大小：1.26 MB 人氣：0 2017-12-22 需要積分：3
標(biāo)簽：
廣義弧相容是求解約束滿足問題應(yīng)用最廣泛的相容性，MDDc．STR2和STR3是表約束上維持廣義弧相容應(yīng)用較多的算法，其中，MDDc基于對約束壓縮表示的思想，將表約束表示成多元決策圖，對各個元組之間存在較多交疊部分的約束具有很好的壓縮效果：STR3同STR2 -樣，基于動態(tài)維持有效元組的思想，當(dāng)元組集規(guī)模縮減較慢時，STR3維持廣義弧相容的效率高于STR2．通過深入分析發(fā)現(xiàn)，MDDc中查找節(jié)點(diǎn)的有效出邊和STR3中檢測并刪除無效元組是耗時最多的操作．分別對MDDc和STR3提出一種自適應(yīng)查找有效出邊和檢測刪除無效元組的方法AdaptiveMDDc和AdaptiveSTR，對于同一操作，可以根據(jù)回溯搜索不同階段的局勢，自適應(yīng)地選擇代價(jià)最小的實(shí)現(xiàn)方法．得益于較低的判斷代價(jià)以及回溯搜索不同階段采用不同方法的效率差異，AdaptiveMDDc和AdaptiveSTR相比，原算法速度提升顯著，其中，AdaptiveSTR在一些問題上相比STR3提速3倍以上．
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%
