An interview question

sqyuan

I went to the interview today, and the examiner gave me a question. Find the shortest distance on the map. The effect to be achieved is to randomly appear 50 points, and then pick any two points. Make the shortest path and draw it ...

Which expert has a simpler answer? Ask for it ...

iswipyud

It's the shortest if two points are directly connected. . .

ly_1112

Is it a greedy algorithm to test the data structure,

evefry

What is a greedy algorithm? ? ?
It shouldn't be solved in a straight line, right?
Isn't the specific environment of the question in LZ clearly stated? Looking forward to the master's solution

魂天使

It is the algorithm of data structure diagram, single source shortest path algorithm

ly_1112

The greedy algorithm (greedy algorithm) invented by Dijkstra can solve the shortest path problem. The main idea of ​​the algorithm is to find the shortest path step by step, and each step generates a shortest path to the new destination vertex. The target vertex that can be reached in the next step is selected by the following greedy criterion: among the vertices that have not produced the shortest path, the target vertex with the shortest path is selected.
　　 Set up the vertex set S and continue to make greedy choices to expand this set. The vertex belongs to the set S if and only if the shortest path from the vertex to the vertex is known. Initially, only source is included in S.
Let u be a vertex in G, we call the path from the source point to u and passing only the vertices in the set S as a special path from the source to u, and record this special path (for example, dist[i in the program , J]).
　　 Each time the vertex u with the shortest special path length is selected from V-S, u is added to S, and the special path length is modified as necessary. Once V=S, the shortest path from the source to all other vertices is obtained, and the solution of the problem is obtained.

lrb1985

Learn

binghe

There are quite a lot of discussions on the algorithm. If the host is interested in this algorithm, you can try Google it: postman problem, quenching problem, genetic algorithm, heuristic algorithm, etc., basically all discussions of this algorithm

The basic idea:
A significant sign of judging the shortest path is that there must be no two crossing lines.

algorithm:
Use Dijkstra to generate the initial node. After that, randomly extract two line segments, exchange vertices, for example, line segments ab and cd, which become ad and bc after the exchange, and then calculate whether the sum of the two line segments is shortened. The number of extractions determines the final ideality.
After the number of exchanges reaches a critical value, the results cannot be optimized.
This algorithm has a relatively large flaw. In such a connection graph, there must be a line segment connecting from one side of the graph to the other side. That is, the optimal solution will never be obtained.

improve algorithm:
Requirements: probability theory and mathematical statistics.
For the improvement of the above-mentioned exchange algorithm, in the exchange process, it is not strictly determined whether to shorten, but to allow a certain degree of total increase in the exchange process, and the increase ratio can be calculated. Then, the algorithm requires recording a few steps of the exchange process, and, after a few steps, there is no reduction in the back. Use iteratively until it reaches that there is no cross between any two connections, and the optimal solution result is reached.

All relevant mathematical models have not been listed due to space reasons, but just a general idea, I believe it should be able to satisfy your interviewer!

jjyhktc10

The shortest path of the graph
There are two ways~