求解約束滿足問題的MDDc和STR3算法
大小：1.26 MB 人氣： 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é)點的有效出邊和STR3中檢測并刪除無效元組是耗時最多的操作．分別對MDDc和STR3提出一種自適應(yīng)查找有效出邊和檢測刪除無效元組的方法AdaptiveMDDc和AdaptiveSTR，對于同一操作，可以根據(jù)回溯搜索不同階段的局勢，自適應(yīng)地選擇代價最小的實現(xiàn)方法．得益于較低的判斷代價以及回溯搜索不同階段采用不同方法的效率差異，AdaptiveMDDc和AdaptiveSTR相比，原算法速度提升顯著，其中，AdaptiveSTR在一些問題上相比STR3提速3倍以上．
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%