Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

what happens when backtracking?

Help
nrike6
2013-04-04
2013-10-13
  • nrike6
    nrike6
    2013-04-04

    is backtracking always removing levels from the store? what is the difference between backtracks and wrong decisions? is it possible that the solver backtracks and the store-level is increased?

     
  • kris
    kris
    2013-04-04

    First, the store level is NEVER increased when solver backtracks. It is in fact decreased. The store level is decreased and all data generated by the annulated decision are removed.

    The difference between number of wrong decisions and a number of backtracks is very subtle. The wrong decisions are are increased when the solver makes a new decision on setting a value to a variable and this decision fails. Backtracks are counted when the solver returns from the next node in the search tree with fail result. This fail might depend on a wrong decision or a new decision that basically says that variable cannot be equal a given value (the one that failed recently).

    /Kris

     
  • nrike6
    nrike6
    2013-04-10

    hi kris. thanx for your explanations.

    i am currently creating a custom selector which, at each step when an unbound variable is selected, restricts search to only a part of the variables domain (depending on the values of the previous variables). I try to do this by adding new constraints. E.g: Var_X::{1..4} -> Var_X = 1 OR Var_X = 2, thus forbidding the values 3 and 4.

    In order to remove values form the domain i call the consistency() method. Now, here is the problem:
    When there is no value possible due to the new constraint and the domain should be empty, a FailException occurs.
    In this case i would like to backtrack.

    Is there an easy way of coping with this?

    Thanx,
    Nrike

     
  • kris
    kris
    2013-04-10

    Hi!

    I have to say that I do not really understand what you are doing and how you interface with existing search but the search does backtrack when a domain becomes empty. This is achieved by checking the return value from consistency method. If consistency returns false the backtrack occurs. Basically the search removes all variables created on the current level and decreases the level for search.

    Another important thing in search. Each search decision has always negated decision that is taken if the first decision is wrong. For example, x = constant and x != constant in a standard search. In your case you can try, so called split search, implemented by SplitSelect and and IndomainMiddle. In this case the decision will be x <= middle_value and x > middle_value.

    Hope this can help.
    /Kris

     
  • nrike6
    nrike6
    2013-04-11

    Thanx Kris.

    I have another question concerning the counting of backtracks in DepthFirstSearch (lines 711-786).

    When assigning the current variable resulted in non-consistency DepthFirstSearch tries the complement/negation. If this also returns false (i.e. non-consistency) this should be counted as a backtrack as there are no possibilities left.

    Here, the code differentiates between three cases:
    1. (line 726) The choice point was based on a constraint: If the negated constraint also leads to inconsistency -> backtrack++
    2. (line 746) The choice point was based on a variable and a domain value && variable not singleton: Try complemented domain. If this leads to inconsistency -> backtrack++
    3. (line 772) Variable is singleton: The single value has already been tried and lead to inconsistency before. Here, no backtrack is counted!

    Why is there no backtrack counted when the variable was singleton and this single value lead to inconsistency?

    Many thanx,
    nrike

     
  • Hi,

    I apologize for late answer. I missed your last question.

    The measurements in JaCoP are done as proposed in the following paper -

    Bessiere, C., Zanuttini, B., Fernandez, C.: Measuring search trees. In: Proceedings
    of ECAI’04 workshop on Modelling and Solving Problems with Constraints. (2004), 31–40

    Thus, if there was a singleton then there was no decision to be taken, so reverting this decision is not a backtrack. Hope that helps.

    best regards,
    Radek