Node constraint routing algorithm based on reinforcement learning
Weihang Dong, Wei Zhang, Wei Yong Yang · 2016
Also named as the path-finding algorithm, the routing algorithm aims at finding a good way between the source point and destination point under some constraint conditions (the path “cost” is the lowest). Specifying part of necessary nodes by the algorithm, the node constraint routing algorithm finds the “good” path and must pass the necessary nodes without the loop; otherwise, the path is invalid. The node constraint shortest path problem is regarded one HP-Hard problem, and the current research generally adopts the violent algorithm or the screening function approach (screen out some paths passing the most of the currently necessary nodes); however, these methods have the loop or own much high time complexity or space complexity, which easily causes the intermittent interruption of the path loop or the network. For the end-to-end node constraint path-finding problem of the common directed network graph, this thesis designs one heuristic search algorithm based on the reinforcement learning the breadth-first traversal; the algorithm adopts thought of combining the breadth-first search and the greedy algorithm to expand the path, adopts the reinforcement learning to predict and screen the importance degree of the path as well and finally gets the path passing all the necessary nodes. The simulation experiments result demonstrates that the algorithm proposed by the thesis can be applicable to the network graph with the larger scale, has good performance in the path weight and the computing time and is regarded as one practically applicable algorithm.