[Solved]: Algorithm for sorting with constraints

ignougroup
Problem Detail: I’ve got 30 elements which has to be grouped/sorted into 10 ordered 3-tuple. There are several rules and constraints about grouping/sorting. For example: Element $A$ must not be in the same tuple same unit $B$. Element $C$ must not be right in front of element $A$, etc. I am searching for an approximated algorithm:

  1. We don’t need to achieve the exact optimum
  2. It is OK for some rules not to be satisfied, if it helps to fulfill more rules.

Do you know of any algorithm/proceeding that solve this problem or a similar one? I fear to solve it in an optimal way, you have to try out every possible solution-> $2 ^ {30}$ EDIT: Sorry for the bad explanation. I am trying to make it a bit clearer: I got 30 elements for example: ${1,2,3,ldots,30}$. I need to group them into 3-tuples so that i get something like: $(1,2,3)$, $(4,5,6)$,$ldots$,$(28,29,30)$. There are several constraints. For example:

  • 1 cannot precede 2 in an ordered tuple, so, for instance $(1,2,3)$ is not a valid tuple.
  • 5 must be together with 4.

Those constraints can be broken and its possible that there is no solution where all rules can be fulfilled.
An solution is considered as good if the amount of rules broken is “low”. Hope that makes it clearer and thanks for the help so far.

Asked By : Tim SP

Answered By : Tim SP

Just to let anyone know, who got a similiar problem. I found genetic algorithm as an solution to it.

  1. Create a population by creating multiple individuals. This is done by setting the elements on a random spot in a vector.
  2. Generating the fitness of the individuals by checking how many rules are broken. The fitness is reduced by 1 per rule broken.
  3. Checking if the solution is acceptable(Either fitness = 0 or termination criteria satisfied)
  4. Doing tournament selection with suitable size(i chosed 3) on the population -> Getting the tournament winner -> Reproduct it, Mutate it or 1-Point-Crossover 2 of them and add it to the limbo. -> Repeat 4. till the limbo got population size
  5. Goto 3.

Hope you get the idea of it. Thanks for the comments on the original question. If you got any question, feel free to ask.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18312  Ask a Question  Download Related Notes/Documents