This paper deals with methods exploiting tree-decomposition approaches for solving constraint networks. We consider here the practical efficiency of these approaches by defining five classes of variable orders more and more dynamic which preserve the time complexity bound. For that, we define extensions of this theoretical time complexity bound to increase the dynamic aspect of these orders. We define a constant k allowing us to extend the classical bound from O(exp(w + 1)) firstly to O(exp(w + k + 1)), and finally to O(exp(2(w + k +1)-s~-)), with w the "tree-width" of a CSP and s~- the minimum size of its separators. Finally, we assess the defined theoretical extension of the time complexity bound from a practical viewpoint.
展开▼
机译：本文探讨了利用树分解法求解约束网络的方法。我们在这里通过定义越来越多的动态五种变量阶来考虑这些方法的实际效率，这些变量阶保持了时间复杂性。为此，我们定义了这种理论上的时间复杂度的扩展，势必会增加这些订单的动态方面。我们定义一个常数k，使我们可以将经典界从O（exp（w + 1））扩展到O（exp（w + k + 1）），最后扩展到O（exp（2（w + k +1） ）-s〜-）），其中w表示CSP的“树宽”，而s〜-表示分隔符的最小大小。最后，我们从实际角度评估时间复杂度的定义理论扩展。
展开▼
