State compression replaces a dynamic programming history by a smaller summary that retains everything needed to determine future legal choices, costs and transitions. Histories may be merged only when their summaries make all relevant continuations equivalent.
For selecting a subset of objects, an -bit mask stores membership in one integer. A path problem may additionally need the final vertex: two partial paths visiting the same subset can have different continuation costs if their endpoints differ. Compression saves storage by discarding irrelevant history; omitting relevant state changes the problem rather than optimizing its solution.
Articles by others on the same topic
There are currently no matching articles.