Algorithm for constructing line lines effectively

Question

I found answers to the following algorithms online, but did not find an effective solution. This was asked in a Google interview. The question is:

For the sequence of lines to be built (each line has a start and end point),
give an algorithm that helps you build lines in the least amount of time.
It is not necessary that the line be built only from the starting point.

There was one approach that treated each line as a node on the chart.
And the edge between two nodes is the distance between the end of the node of the first row
and launch node of the second line. After that, if we calculate the minimum spanning tree,
he will give the optimal answer.

But I’m not sure that this gives an optimal solution all the time, since it assumes that the line is built in only one direction.

Can someone tell me how to solve this problem?

Answer 1

Assuming that the interpretation of the Steve314 plotter in the commentary is correct (as indicated by the OP), then the problem is a definite generalization of the traveling salesman problem, which is known to be NP-complete.

Evidence. If all lines are 0 in length, i.e. reduced to points, the problem is this: each point should be affected by the pen, and the total distance traveled by the pen should be minimized. This is precisely the problem of the Euclidean traveling salesman.

So, you should look for an approximation algorithm (you cannot find the optimal solution efficiently). Some of the approximation algorithms for the Euclidean TSP are based on the miminum spanning tree and can be modified to solve your problem. It may also be possible to prove that the resulting algorithm will give you a path that does not exceed X (= two?) Multiplied by the length of the optimal path.

EDIT : here is a complete example adapted from the "simplest" metric TSP solution algorithm on Wikipedia

• Interpret the lines you want to draw as the edges of an undirected (possibly disabled) graph whose vertices are the specified endpoints
• Runs to the minimum bound (spanning) graph containing the required edges (using the Prim algorithm)
• Convert to directed graph and find Euler scheme

This should give you a solution (follow the edges of the path drawing if necessary), which is no more than twice as long as the optimal path. It can be further optimized in different ways, for example, using a shortcut and skipping a vertex on the path whenever the next edge does not need to be drawn (again or at all).

Answer 2

For a minimal spanning tree, you will have to use the Djikstra algorithm, which will select the shortest path and compare it with all the others associated with the same node, recursively, until all nodes are processed. Actually, I'm just re-reading the question, and since your path should not start from a certain point, you can use Prim, which has the same idea as above but starts from any node. Both use a priority queue that allows you to perform a breadth-first search.

Answer 3

This is a pretty nasty problem. This is the shortest Hamiltonian path, but you have a ton of edges (all edges (u, v), where u is the endpoint of some line and v is the starting point of another line), and the distances are not symmetrical. The elegant ZDD method described in TAOCP 4A is not really applied, I think it will be loaded in all these parts.

Here's an idea (not optimal, but in any case, it seems like a pretty good idea), borrowing from TSP:

For every line s Schedule = empty sequence For every line n insert n in the optimal position in Schedule Apply 2-opt (see TSP) to the Schedule Take the best Schedule. 

Be very careful with this 2-opt. This is often described for the case of symmetrical distances, which allows optimizing the calculation of "distance change". Here you cannot here.

Here's another idea, borrowing heavily from TSP:

Solve a ton of problems with ILP. For each node s and t (not equal):

• boolean for each edge.
• weights are the lengths of these ribs.
• every node n that is not s or t gives a form constraint of "the sum of all edges adjacent to n == 2"
• for nodes s and t , this sum instead of 1
• It is lazy to add restrictions that everything should be a single communication component, that is:
  • discovery of connected components. If there is 1, this is the solution.
  • if for each connected component is greater than 1,
  • if it contains s or t , add the restriction that the sum of all edges adjacent to this connected component must be 1.
  • otherwise, this amount should be 2.

Take advantage of all these solutions. This may take some time.

Answer 4

Not sure if I fully understand your question. One approach might be to start with the drawing area, say, a 640X480 image. Then for each position in the image you check to see if the pixel (x, y) is on at least one line (you only need to execute one line using a linear equation and some suitable value for epsilon), if so, then you print a 1 else a 0. All lines are drawn.