How to solve the problem with a simple algorithm?
-
There are a total of P levels. For any level p, there are Jp nodes. Any two nodes on the same level are not connected. And the unidirectional path weight between any two nodes Ai and Bj is D(i,j). What is the shortest distance required from the first layer to the _P_th layer? (** Note that P is generally large and it is not recommended to traverse all possible situations **) If this problem is abstracted as a graph, then what is actually required is the shortest path from the first layer to the last layer of a fully connected network. What I have tried: Use deep search, Dijkstra algorithm, Floydw algorithm, etc. to search the shortest path from all J1 nodes in the first layer to the last layer in turn, and select the minimum value from the J1 values. What I want to know is if there is a simpler algorithm to solve this problem?
-
There are a total of P levels. For any level p, there are Jp nodes. Any two nodes on the same level are not connected. And the unidirectional path weight between any two nodes Ai and Bj is D(i,j). What is the shortest distance required from the first layer to the _P_th layer? (** Note that P is generally large and it is not recommended to traverse all possible situations **) If this problem is abstracted as a graph, then what is actually required is the shortest path from the first layer to the last layer of a fully connected network. What I have tried: Use deep search, Dijkstra algorithm, Floydw algorithm, etc. to search the shortest path from all J1 nodes in the first layer to the last layer in turn, and select the minimum value from the J1 values. What I want to know is if there is a simpler algorithm to solve this problem?
If I understand this correctly, you're looking for a unidirectional path from the first layer to the _p_th layer, a path that includes each layer only once. I would start with the second layer. Assign each node its shortest distance from the first layer, and record the first layer node whose edge was selected. Then proceed through each layer in the same way: for each node, find its shortest distance from the nodes in the previous layer (the current weight of a previous node plus its edge to the current layer). Eventually you will find the shortest distances to nodes in the _p_th layer, and thus the shortest path to that layer.
Robust Services Core | Software Techniques for Lemmings | Articles
-
There are a total of P levels. For any level p, there are Jp nodes. Any two nodes on the same level are not connected. And the unidirectional path weight between any two nodes Ai and Bj is D(i,j). What is the shortest distance required from the first layer to the _P_th layer? (** Note that P is generally large and it is not recommended to traverse all possible situations **) If this problem is abstracted as a graph, then what is actually required is the shortest path from the first layer to the last layer of a fully connected network. What I have tried: Use deep search, Dijkstra algorithm, Floydw algorithm, etc. to search the shortest path from all J1 nodes in the first layer to the last layer in turn, and select the minimum value from the J1 values. What I want to know is if there is a simpler algorithm to solve this problem?
-
There are a total of P levels. For any level p, there are Jp nodes. Any two nodes on the same level are not connected. And the unidirectional path weight between any two nodes Ai and Bj is D(i,j). What is the shortest distance required from the first layer to the _P_th layer? (** Note that P is generally large and it is not recommended to traverse all possible situations **) If this problem is abstracted as a graph, then what is actually required is the shortest path from the first layer to the last layer of a fully connected network. What I have tried: Use deep search, Dijkstra algorithm, Floydw algorithm, etc. to search the shortest path from all J1 nodes in the first layer to the last layer in turn, and select the minimum value from the J1 values. What I want to know is if there is a simpler algorithm to solve this problem?
Simpler than Dijkstra? Seriously? Dijkstra is the obvious choice. You may be able to find a faster algorithm, but not a simpler one, unless you use brute force. P.S.: I wasn't familiar with the Floyd-Warshall algorithm[^] (assuming that is what you were referring to). It seems like it is simply a specialiced version of Dijkstra applied to a weighted graph. Sounds like it's a perfect fit for this problem.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
-
Simulated Annealing[^] could be effective. I don't know if it belongs to the 'simple algorithm' category. :-)
Unfortunately it can in general not guarantee that it will find the global optimum. You can find a good guess very quickly, or you can slow the annealing to the pace of continental drifts and have a higher chance to find the correct answer, but you can never be 100% sure unless you test all options, i. e. brute force.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
-
Unfortunately it can in general not guarantee that it will find the global optimum. You can find a good guess very quickly, or you can slow the annealing to the pace of continental drifts and have a higher chance to find the correct answer, but you can never be 100% sure unless you test all options, i. e. brute force.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
