Mary Burke Week 6

This last week we finished with our backtrack search algorithm.  I mentioned in my last post that we had issues comparing our search algorithms due to differentness in the way we implemented our search heuristics.  One of the problems we ran into was with using the degree heuristic.  I used the current degree, while my colleague used the future degree.  In my implementation, I simply searched through the list of variables for the variables and sorted them based on the number of ‘neighbors’ the variable had.  I the other implementation, after a variable is found to have the largest number of neighbors it is added to the list than its neighbors’ degree is decremented.  After we discovered this, we decided to run both types of degree orderings.  Additionally, we ran our backtrack search on random instances with varying tightness.  Since these instances were much larger, we had to obtain a special accounts and run our script on the supercomputer at UNL!

Also, during the course of the week, we studied more thoroughly the forward checking algorithm and its hybrids.  We went through the pseudocode of forward checking and studied the data structures and methods used in the algorithm.  We discussed sufficient conditions for the backtrack search, backjump search, conflict-direct backjump search, and forward checking search.  Finally, we began implementing the conflict directed backjump search and will compare results this week.

-Mary Burke