Jump to content
  • Advertisement
Sign in to follow this  
Storyyeller

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!