A bio-inspired algorithm for a classical water resources allocation problem based on Adleman–Lipton model

The shortage of water resources has always been one of the difficult problems that plagued world economic development and social stability. The imbalance and uneven distribution of water resources between regions exacerbate this contradiction. Therefore, the optimal economical and reasonable water resource design method has become the hope for solving the problem of water resource shortage. As a classic resource allocation and scheduling problem, the rural postman problem has been widely used in practice. The problem includes finding the minimum cost tour after traversing all edges in the required edge subset at least once in an undirected graph, but so far, there is no effective algorithm to solve this problem. Based on bio-heuristic computing model and deoxyribonucleic acid (DNA) molecular operations, a parallel bio-computing algorithm for rural postman problem is proposed in the paper. We use a DNA algorithm to solve the rural postman problem with n vertices in O(n 2 ) time complexity. Then, we prove the feasibility of the algorithm in theory and verify the authenticity of the algorithm in the simulation experiment. Compared with previous algorithms, DNA computing algorithm not only has higher computational efficiency and lower error rate but also has huge storage capacity and parallel computing ability, which makes the algorithm has better applicability in dealing with large-scale problems.