| Constraint satisfaction problem(CSP)is an important research problem in the field of artificial intelligence.It provides enough general tools for modeling and solving complex problems in the fields of computer,mathematics,practical production and life.The problem of constraint satisfaction is a classical NP hard problem in the field of computer.To solve the problem of constraint satisfaction is to obtain one or more groups of solving examples in the large solution space,or to prove that there is no solution.Constraint network is an important model to solve constraint satisfaction problem.In constraint network,vertex represents variable and edge represents constraint relationship between variables.The algorithm of constraint satisfaction problem is to assign values to variables and maintain consistency on the constraint network according to a certain propagation strategy,so that all constraints associated with network variables are satisfied.Different communication strategies have a serious impact on the efficiency of problem solving.The defect of traditional propagation strategy is that when the constraint network changes locally(variable domain Revision),the compatibility will be destroyed and the search space will be expanded again.Therefore,this thesis presents a dual propagation mode which is divided into two stages.The results show that compared with the existing propagation mode,it can effectively reduce the redundant operation and improve the efficiency of maintaining arc compatibility.Compared with the traditional propagation strategy,the two-way propagation strategy proposed in this thesis can eliminate redundant revisions with low cost,reduce the average number of revisions to expand a single node,further reduce the cost of maintaining arc compatibility,and obtain an improvement in solution speed.Compared with the traditional method,the two-way propagation strategy has the lowest revision times in the standard test data set.For the constraint network with high connectivity,the constraints between variables are more closely related and the cost of maintaining compatibility is higher.The number of revisions of this method is significantly reduced.In some test data sets,the average number of revisions of this method is 17% less than that of the traditional method,and correspondingly,the overall solution time is 10% less.In addition,the existing arc compatibility algorithm design ideas are based on the idea of "propagation",that is,the constraint network changes locally,and then the compatibility is destroyed,causing the modification of other parts of its association to re realize the compatibility.This idea has good incremental operation properties,but also limits the ability to achieve parallel arc compatibility maintenance.In order to solve this problem,this thesis proposes One method is to design arc compatibility as a global iterative maintenance process,using matrix operation to maintain arc compatibility,sacrificing the characteristics of incremental operation,but the whole process achieves complete parallelism.The operators of matrix operation are implemented in the existing widely used frameworks(such as numpy,python,tensorflow).Therefore,with the help of these frameworks,the algorithm design is greatly simplified.Because the whole process of consistency maintenance is expressed as matrix operation,the consistency maintenance can be completely performed on GPU.The experimental results show that the efficiency of this parallel arc consistency maintenance method is significantly improved compared with the existing algorithms on the dense connected complex constraint network.When the number of variables reaches 700,the number of revisions of the traditional serial method reaches 180000,while the number of iterations of the parallel method is basically between 3.5 and 4.5.Accordingly,comparing the average time of expanding a node,the performance of parallel operation method is 100 times higher than that of traditional method. |
PDF Full Text Request