java - 数据结构的图要求经过指定一些边，求最优解？

Question

数据结构的图要求经过指定一些边，求最优解？能帮忙指点一下应该怎么去网上找资料吗，比如和哪个问题类似，应该用什么算法？这个问题是这样的,货运公司必须经过某一些城市,题目给出各个城市之间的花费,让用A*算法...

大家讲道理 · Answer

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*

大家讲道理 · Answer

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-> 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.

伊谢尔伦 · Answer

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