求解約束滿足問題的MDDc和STR3算法

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