2
$\begingroup$

I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach?

In AIMA they give the recursive version of backtracking.

function BACKTRACKING-SEARCH(csp)
  return BACKTRACKING({}, csp)

function BACKTRACK(assignment, csp)
  if assignment is complete then return assignment
  var ← SELECT-UNASSIGNED-VARIABLE(csp)
  for each value in ORDER-DOMAIN-VALUES(var, assingment, csp) do
  if value is consistent with assignment then
    add { var = value } to assignment
    inferences ← INFERENCE(csp, var, value)
    if inferences ≠ failure then
      add inferences to assignment
      result ← BACKTRACK(assignment, csp)
      if result ≠ failure then
        return result
  remove { var = value } and inferences from assignment
  return failure

They have said backjumping can be built by a little modification to this algorithm with conflict set but I don't think so.

Backtracking is just a recursive algorithm and it has to use stack stack. But, in backjumping the stack sequence is trouble in jump. The worse is that java does not support goto statement.

So am i missing here something. Please advice me how to get backjumping by modification of backtracking as shown in figure.

$\endgroup$
2
$\begingroup$

When a conflict is found during a recursive constraint satisfaction search there may be assignments and inferences in the call stack that have no connection to the conflict. Instead of backtracking through these ineffectual assignments at exponential cost it is better to jump backward over them in the call stack directly to the most recent assignment that made the conflict inevitable. This is backjumping.

To implement backjumping in the algorithm above, you would do three things:

  1. Make the BACKTRACK function maintain a counter storing the depth of its call stack.
  2. Instead of simply returning failure, have BACKTRACK also return a number representing the stack depth whose BACKTRACK function should resume execution. This number would be determined by careful examination of the assignments and inferences that led to the conflict.
  3. Have all calls to BACKTRACK at stack depths greater than the returned number simply return the number rather than continue iterating through ORDER-DOMAIN-VALUES.

All the ORDER-DOMAIN-VALUES assignments between the current level and the backjump target level will no longer happen. This gives exponential computational savings with a cost only linear to the size of the backjump.

$\endgroup$
  • $\begingroup$ @ Kyle Jones If so,which version of conflict based backjumping people mostly used? Am,i too pushy effort to unrealistic thing. $\endgroup$ – Cecelia Feb 4 at 7:27
0
$\begingroup$

How about adding the additional data structure of conflict set union just as like prosser?

$\endgroup$
  • $\begingroup$ Thanks for your participation. We're not a coding site, and we're not looking for answers that consist solely of code. We'd prefer to see concise pseudocode, accompanied by explanation of the ideas, justification, and/or proof of correctness. Thank you! $\endgroup$ – D.W. Feb 4 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.