Which class of problems is this?

Question

I’m working on a problem which I will try my best to describe:

• You have a stack of 5 blocks: labelled A, B, C, D and E.

• You also have a set of rules giving points if certain conditions are met, for example: B is above D (1 point), D is above A (0.75 points), A is above D (0.25 points) etc.

• The goal is to stack the blocks in such a way as to maximise the number of points from the goals. Some goals are contradictory so not all goals can necessarily be met.

I would like to understand which kind of general class of problems it is, in order to find a general way to solve it. Is it a graph traversal, bin packing or some other class of problems?

Answer 1

There are different ways to classify this problem. For example:

• combinatorics : it’s about choosing and combining elements in a way to comply with rules/constraints (combinatorial analysis) and find an optimal solution (combinatorial optimization).
• graphs: the blocks are nodes, the possibility to stack them is a directed edge between two nodes, and a stack is a path in that graph. It is then an optimal path finding problem.