Efficiency of Constraint Learning
The efficiency of constraint learning algorithm is balanced between two factors. On one hand, the more often a recorded constraint is violated, the more often backtracking avoids doing useless search. Small inconsistent subsets of the current partial solution are usually better than large ones, as they correspond to constraints that are easier to violate. On the other hand, finding a small inconsistent subset of the current partial evaluation may require time, and the benefit may not be balanced by the subsequent reduction of the search time.
Size is however not the only feature of learned constraints to take into account. Indeed, a small constraint may be useless in a particular state of the search space because the values that violate it will not be encountered again. A larger constraint whose violating values are more similar to the current partial assignment may be preferred in such cases.
Various constraint learning techniques exist, differing in strictness of recorded constraints and cost of finding them.
Read more about this topic: Constraint Learning
Famous quotes containing the words efficiency, constraint and/or learning:
“Nothing comes to pass in nature, which can be set down to a flaw therein; for nature is always the same and everywhere one and the same in her efficiency and power of action; that is, nature’s laws and ordinances whereby all things come to pass and change from one form to another, are everywhere and always; so that there should be one and the same method of understanding the nature of all things whatsoever, namely, through nature’s universal laws and rules.”
—Baruch (Benedict)
“In America a woman loses her independence for ever in the bonds of matrimony. While there is less constraint on girls there than anywhere else, a wife submits to stricter obligations. For the former, her father’s house is a home of freedom and pleasure; for the latter, her husband’s is almost a cloister.”
—Alexis de Tocqueville (1805–1859)
“To raise a son without learning is raising an ass; to raise a daughter without learning is raising a pig.”
—Chinese proverb.