Thursday, March 07, 2013

[ksgvnzch] Optimization over permutations

Consider the task of compressing a set of records which do not need to remain in any particular order.  Apply simulated annealing:  Pick an ordering.  Evaluate how well it compresses.  Apply a permutation: perhaps swap two records, or cut the deck, or remove a middle section and place it at the beginning or end, or the inverse operation.  (In two dimensions.) Evaluate the new ordering.

Maybe genetic algorithm, though don't know how to do crossover.

More elaborate is each record consists of subrecords which also may be reordered, but subrecords must remain contiguous within a record.

No comments :