Shulou(Shulou.com)06/01 Report--

This article is to share with you about how to understand LNS, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

Today, the editor will talk about the large-scale neighborhood search (Large NeighborhoodSearch referred to as LNS) algorithm. Next, the editor will go straight to the topic without beating around the bush. LNS essentially improves the initial solution step by step by alternately using destroy and repair. So what exactly is destroy, what is repair, and how to use these two methods, don't worry and listen to the editor say slowly: destroy as the name implies means "destroy" and repair means "repair". The editor also takes the TSP problem in five cities as an example, assuming that the initial solution is 12345. In the first step, we use the destroy method for the initial solution. The editor uses the most basic method of randomly selecting several cities to destroy the initial solution. For example, if you choose 2 and 5, then the 2 and 5 cities are removed from the initial solution, and the remaining cities are arranged in the initial order. In the second step, we use the repair method to repair the solution after destroy, that is, we reschedule the two cities 2 and 5 into 134. here, we can randomly select a city from 2 and 5 to insert into 134. for example, we choose 2 to insert into 134. there are three possibilities: 2134, 1234 and 1324 (1342 and 2134 have the same effect, so they are not repeated) If we choose the best of the three possible solutions, such as 1324, then we choose 1324, and then insert 5 into 1324, there are four possibilities: 51324, 15324, 13524, 13254, and then choose the best solution from the four solutions. Of course, the editor explains the most basic ideas of destroy and repair. The following editor gives the flow chart of LNS for solving TSP problem.

The above is how to understand LNS. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.