CODEWITHSUNDEEP
javaalgorithmartificial-intelligence
Skyler Gunn
Skyler Gunn

Reputation: 59

Backtracking search for constraint satisfaction problem implementation

For a homework assignment, my goal is to have a backtracking search using minimum remaining values, a degree heuristic, and forward checking. Needs to solve a Boolean satisfiability problem consisting of sets of 3 Boolean variables or'd with each other, and each set must evaluate to true. As my current implementation stands, I believe it will eventually solve it, but it takes so long to finish that I end up with a java heap out of memory error.

With that out of the way, my implementation is as follows:

The back search returns an array of values, and takes in an array of values and an array of domains

First checks each constraint in the list to make sure the domain for each variable works to make it true. If none of them work, set 0th flag and exit. Additionally, if 2 variables have a domain that makes the the third variable have to be true in order to make the statement work, changes the domain of that variable.

After it passes that step, it checks if each variable in the vals array has an assigned value, ending the program on a success.

Next it makes a temporary array to keep track of values it's tried, and begins a loop. Inside, it adds each variable that has a domain of the smallest domain found (MRV) and doesn't have a value/hasn't been tried, adding it to the list, and exiting the recursion if it can't find any. It then selects from the variables the one that appears the most based on the degree heuristic array. On a tie, it picks the last one that appears in the tie, and sets a flag so we don't try that variable again in the same recursion.

Still inside the loop, it first tries to set the domain and value of that variable as true if the domain isn't only false, and false otherwise. It checks to see if that value combination for the variables has been done before, and if it has it reselects. If it hasn't, it adds that value combination to the list and does a recursive step. If that recursive step returns a stop flag, swap back the values to what they were for the domain and value of selected variable, and tries again, this time making the domain and value false, but first it adds it to the list of tried combinations, reselecting if its already there, and resets the domains of all variables that don't have a value yet, then does the recursive step. If that also fails, resets the values of the variable selected domain and value and tries to select a different variable in the same loop. The loop breaks once it's complete or has failed for all combinations, and then returns the values array.

I can tell that it's not repeating itself but I don't know how I can fix/speed up my implementation so that it runs at a reasonable time.

Upvotes: 1

Views: 779

Answers (1)

Manuel Rodriguez
Manuel Rodriguez

Reputation: 782

The first step is to create a knowledge model for the domain. This can be done with a domain specific language (DSL). In the DSL syntax a possible solution to the problem is formulated. The wanted side effect of a domain specific language is, that a grammar has to be created which can parse the language. This grammar can be used in the reverse order which is called a "generative grammar". The aim is to include as much domain knowledge as possible in the DSL which makes it easier for the solver to test out all states.

Unfortunately, the question has only a few information about the domain itself. According to the description there are three variables which can be on or off. This would generate a possible statespace of 2x2x2=8 which seems a bit too easy for a domain, because the solver is done if he tested out all 8 states. So i would guess, that the problem is bit harder but not explained in the description. Nevertheless, the first step is to convert the problem into a language which can be parsed by a grammar.

Upvotes: 0

Related Questions