CODEWITHSUNDEEP
algorithm
Honza Brabec
Honza Brabec

Reputation: 37598

AC-3 algorithm and backtracking

I have solved a CSP problem using the following approach:

  1. Run AC3 to reduce variable domains
  2. Use simple backtracking to find solutions.

It works really well and fast for all my testcases, but a friend of mine asked me this: "What if the initial AC-3 doesn't reduce anything?" and is implying that I shall run AC-3 at every step of the backtracking.

I have a feeling that it wouldn't help me much in such case, but somewhere I've seen that the AC-3 can be used both ways, but with no further explanation. Can I get some more info about this?

PS: Actually it isn't bearable in my case to run AC-3 everytime because it runs about 2 seconds long. But I am asking this question out of curiosity and it can be useful when I will solve some other problems.

Upvotes: 0

Views: 3383

Answers (1)

Honza Brabec
Honza Brabec

Reputation: 37598

Since this question is dead for about a month I think I will answer it myself. There really is a benefit in running AC-3 in every step of the backtracking. I've encoutered such problems where the initial AC-3 didn't reduce much but the subsequent ones with some variables fixed were far more successful.

Upvotes: 1

Related Questions