亚洲国产日韩欧美一区二区三区,精品亚洲国产成人av在线,国产99视频精品免视看7,99国产精品久久久久久久成人热,欧美日韩亚洲国产综合乱

This is a relatively open problem. I personally think it is still a part of graph theory, but it cannot be solved by existing shortest path related algorithms such as SPFA and dijkstra algorithm. Zeng Jin seems like a friend asked me what kind of competition question it was for Huawei. It is definitely possible to use the A* algorithm for this question. The key is how to design this heuristic function?
You can search for related knowledge
1. Shortest path algorithm through a specified set of intermediate nodes
2. Heuristic search algorithm A*

I don’t think this question has a polynomial solution. (Welcome to slap in the face)
Suppose the number of points is n, the number of edges is m, the number of edges that must be passed is k, n<=500, m<=5000, k<=500.
Consider the brute force approach, O(n^3) to preprocess the shortest path between any two points (of course you can also optimize dijkstra with n times of heap, but this is not a bottleneck), O(k!) to enumerate the k edges passed by Arrange and calculate the answer, the total complexity is O(k!*k), which is obviously unacceptable.
Note that the optimal solution does not necessarily need to be obtained by enumerating all permutations. You can use randomized algorithms such as simulated annealing to obtain a better solution. Using appropriate parameters should be able to obtain the optimal solution most of the time.
I want to try to prove that this question is NPC or NPH.
Record the m edges of the original problem as from[i] to to[i].
Create a new graph with k points. For the i-th and j-th of the k specified edges, if to[i] can reach from[j], then connect a dis[ from i to j in the new graph. The edge of to[i]][from[j]]. So the original problem is reduced to a new problem in polynomial time: find a repeatable path through all points in a graph of k points to minimize the path length. This new problem looks a lot like NPC or NPH. (Funny)
But I haven’t figured out how to reduce the new problem back to the original problem. The current idea is that for each point i of the new problem, connect an +inf edge between i<<1 to (i<<1)|1 of the original problem, and for each edge i-&gt of the new problem ;j, connect a disi edge from (i<<1)|1 to j<<1 of the original problem, but there seems to be some problems, and I haven’t thought about it clearly yet.

I don’t understand the algorithm, but I know a general framework for solving this type of CSP problem. You can take a look: Optaplanner