Need some help implementing backjumping algorithm

[ThuriyaThwin]

I am using aima csp solver in my project.But,I need an implementation of Backjumping algorithm with aima python.I have read the AIMA book and the book says Backjumping algorithm can be implemented by with a little modification of Backtracking algorithm.But,I don't see.So,let's develop aima csp solver better by adding backjumping algorithm.

Thanks, Rgd, Thwin

[dmeoli]

Hi @ThuriyaThwin

the backjumping or non-chronological backtracking is a simply backtrack of more than one level in the search tree. This technique allows to prune the search space faster and converge more quickly to the solution.

This is easy to understand but, in fact, the algorithm structure changes completely because, while a recursive algorithm is enough to implement a backtracking search and the backtrack stack is maintained through the stack of recursive calls to the algorithm, in the case of backjumping it is necessary to implement the algorithm iteratively and manage the backtrack stack explicitly to backtrack more than one level!

Therefore, ultimately, you should use a data structure of type graph (DAG) to represent the search tree. I recommend the python networkx library used in other project files and present in the requirements.txt file.

Regards, Donato

[ThuriyaThwin]

I have heard that conflict set can be built by forward checking algorithm.How could be?

[dmeoli]

@ThuriyaThwin I think you have some confusion. All known inference methods (forward-checking and MAC) can supply the conflict-directed backjumping with no extra work, so they are to be used alternately to each other and not together. Backjumping occurs when every value in a domain is in conflict with the current assignment, but forward checking detects this event and prevents the search from ever reaching such a node! In fact, it can be shown that every branch pruned by backjumping is also pruned by forward-checking. Hence, as mentioned above, simple backjumping is redundant in a forward-checking search or, indeed, in a search that uses stronger consistency checking, such as MAC.

[ThuriyaThwin]

@DonatoMeoli If so,please explain me how (forward-checking and MAC) can supply the conflict-directed backjumping with no extra work.I really troubles in this for my exam.There is a little lack of resource about conflict-directed backjumping.It will help others who stuck like me if you explain with aima csp code.

[ThuriyaThwin]

@DonatoMeoli This is the conflicted direct backjumping algorithm right?

[ThuriyaThwin]

@DonatoMeoli So, conflict directed backjumping can be built with recursive data structure?