# Data structures for constraint satisfaction and optimization?

This topic is 2587 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

What data structures are commonly used for constraint satisfaction and optimization problems? Obviously, the problem specification will be a graph of some kind, either linked or with indices to neighbors. The problem is how to handle recursion, as is commonly used in backtracking search methods.

In all but the simplest cases, backup data needs to be stored while searching. This is especially problematic when using constraint propagation because each test variable assignment can potentially update large parts of the graph. Do you just copy the entire graph before each recursive call? That seems a bit wasteful. Do you maintain a separate stack inside each node? How is this commonly done?

##### Share on other sites
There are many types of problem that would fit the description "constraint satisfaction and optimization", some of them not even involving graphs. In order to talk about data structures, we need to narrow it down a lot. Can you give us an example of the type of problem you are thinking of?

##### Share on other sites
Well in this particular case, I am trying to use it for the AI Challenge. The problem is to assign moves to a group of ants to minimize combat losses, distance to food, etc. subject to the constraint that two ants can't occupy the same space.

##### Share on other sites
I don't think you need any fancy data structures for this type of problem. Do you just want to enumerate all the possible assignments of moves to the ants and pick the one that maximizes some function?

##### Share on other sites
Yes, but the naive algorithm is too slow for large numbers of ants.

##### Share on other sites
The only data structure that I think you need here is an assignment of moves to all the ants. If your ants are indexed 0 <= i < n_ants, all you need is a vector of moves. You need a function that evaluates an assignment and returns a single real number indicating how happy we are with the assignment.

Once you have 10 or 12 ants, it will be impractical to explore all the possible assignments exhaustively. But you can easily write a randomized optimization. For instance, you can use simulated annealing: start with any assignment and then consider hypothetical small changes to the assignment (say, change the move for a single ant). Check how much the evaluation function would change. If it improves, accept the change to the assignment. If it doesn't, accept the change with probability P = exp(-worsening_score/T). T here is a parameter called "temperature" that should go from a large number to 0 slowly over the time you have for your optimization.

As you see, none of this requires any fancy data structures.

##### Share on other sites
It is practical with a decent algorithm (i.e. branch and bound with backtracking search). I've done it with 50 ants before.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633709
• Total Posts
3013481
×