Recently I’ve been working on implementing AC2001 as and MAC. The implementation of AC2001 went fairly smoothly especially since I had already implemented AC1 and AC3 previously this semester. I had a few debugging problem most of which came from confusion about when to I was adding arcs to the queue. I tested my implementation of AC2001 on about 15 instances (including the 3,4,5,6-queens problems and a few different instances of the zebra problem). The next step was implementing MAC (Maintaining Arc Consistency) with my currently implemented forward checking algorithm. At first it seemed simple: run FC and if it does not fail form a queue with all constraints between the future variables and run AC2001. This task has been a lot more challenging than I expected. I currently have the algorithm working correctly for finding one solution both with dynamic and static ordering. I’ve noticed that in comparison to FC and FCCBJ, MAC seems to have quite a few more consistency checks but less nodes visited, backtracks, and CPU time. Right now I am working on finding all solutions.
-Mary
No comments:
Post a Comment