4 ms·
I can see why you might be confused. Here's my attempt at an explanation: The goal is to find the permutation of blocks that minimizes the total length of the
by jcranmer 6y ago
I can see why you might be confused. Here's my attempt at an explanation:
The goal is to find the permutation of blocks that minimizes the total length of the table. Each block contributes an amount of that length--the amount that did not overlap with the previous block. This amount is only dependent on the interaction between the block and its previous block. So we can make a graph where each node is a block to be encoded, each node has an edge to every other node, and the weight of that edge is the amount of overlap [1]. Compute an ordering of the nodes to visit that maximizes overlap, and you've a) done a TSP traversal and b) computed the optimal permutation.
[1] Equivalently, non-overlap, gets you a minimum-weight problem, as in classical TSP. But the notes suggest it's framed as a maximal problem, finding the path that maximizes overlap--which is certainly easier to code.