3

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.

  • Just to be clear: you are asking us a question from the US Computing Olympiad, aren't you? And you expect us to offer you solutions, right? Is seeking outside help permitted in the rules of the Olympiad? – Deer Hunter Aug 30 '13 at 7:33
  • 2
    @DeerHunter: you read the line below the question saying "Contest has ended. No further submissions allowed"? Otherwise I would not have answered this one. – Doc Brown Aug 30 '13 at 7:41
2

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.

  • but the worst case runtime of the algorithm will be the same – 2147483647 Aug 30 '13 at 8:12
  • 1
    @A.06: the worst case runtime of standard quicksort is O(n^2), nethertheless in most practical scenarios its extremely fast. And you asked for a practical solution for a given input size of 12 elements - just try and check if it will be quick enough in your case. – Doc Brown Aug 30 '13 at 8:58
  • I'm sorry but the algorithm still fails on two of the cases, is it possible to do better? – 2147483647 Aug 30 '13 at 11:11
  • 1
    @A.06: see my changed edit above, presorting of the free "vertice slots" may help (it includes the simple idea I wrote there before, so I removed it). – Doc Brown Aug 30 '13 at 12:33
  • 1
    @A.06: see my description how to use A* for this problem. – Doc Brown Aug 30 '13 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.