Algorithm to arrange objects so that the total length of edges between them is minimized?

Question

We are given a list of edges between a set of N vertices. There are atmost three edges joining a vertex. We have to arrange all the vertices on a straight line with the positions numbered from 1 to N so that the sum of the length of all the edges is minimized.
The length of an edge a,b is the difference between the positions of vertices 'a' and 'b' on the line. There are atmost 12 vertices. The algorithm should work within the time limit of 1 second.

This is the actual problem.

I have tried solving this problem by trying all the permutations and finding out the total cost of each edge. But this work only for 8 out of the 12 test-cases to the problem. Because in the worst case the total number of operations is proportional to 12! * 18.

The size of N is very small so I think the solution might be similar to trying all the possibilities.
I don't need the complete solution to this problem because I want to try to come up with it myself but only a hint on how can I optimize my algorithm so that it works within the time limit. Thanks.

Answer 1

I would try to attack this problem similar to the eight-queens puzzle

• generate permutations incrementally

• for each placing of the elements 1,..,k, k<N, you can easily calculate a lower bound for the final score without generating all of the final placings of k+1,...,n. For example, you could ignore the fact that k+1,...,n have to be placed on different spots and calculate their scores assuming each of that vertices could be placed at the "optimal spot"

• completed permutations give you an upper bound for the final score; this upper bound will decrease the more permutations you generate

• whenever the lower bound for a partial placing exceeds the upper bound, you can cut the search tree here and stop further placings of k+1,...,n

This technique is also called branch-and-bound.

EDIT: there are of course further optimizations possible. For example: when looking for a place for vertice k, don't try the empty slots from left to right, but pre-sort the empty slots, so that the places with lowest score increasement will be tried first. This will most probably bring the upper-bound quickly, which improves the chance to cut the search tree.

EDIT2: permutation generation defines a search tree. One node consists of k elements already placed in a slot, and the siblings of this node are the (n-k) nodes where one more element is placed in a free slot. You can assign each node a lower-bound score, as I wrote above. But instead of making a depth-first search through this tree, you put the nodes into a priority queue. The algo then takes the node with minimum score first out of the prio-queue, generates the siblings, calculates the lower bound score for each sibling and inserts those nodes into the prio-queue again. When you reach a node where all vertices are placed in a slot, you have found the optimal solution. This is called A* search. It is easy to implement when you have a ready made priority queue at hand.