Research On Improved Algorithm Based On Constraint Satisfaction Problem Solving Algorithm

Constraint satisfaction problems have a wide range of applications in the field of artificial intelligence.At present,there are many methods for solving the constraint satisfaction problem.In this paper,the commonly used maintenance arc-matching algorithm for solving the constraint satisfaction problem is improved,and the two parts that are crucial for solving the constraint satisfaction problem are arc-compatible.The heuristics have been improved separately,and the efficiency of solving the constraint satisfaction problem is improved overall from two aspects.In this paper,by analyzing the constraint-satisfied problem,the coarse-grained sustain arc-compatible solution algorithm is executed in the arc-compatible(AC)process.It is found that there is a redundant arc-return operation in the arc-correction check algorithm and the arc is The redundant return gives a complete proof.Heuristics are an important part of the solution to the problem of constraint satisfaction.It selects and determines the variables and values through certain strategies to search for solutions that satisfy the problem.At present,there are many mature variable heuristics that can select search paths for specific problem attributes.However,because of the strong pertinence,once the characteristics of the solved problem are not obvious,the corresponding heuristics cannot play a selective role,sometimes even The problem solving efficiency is greatly reduced.Based on this,consider designing a robust heuristic to avoid the cliff-like solution efficiency fluctuations.The improvement of the solution to the constraint satisfaction problem in this paper is mainly reflected in the following two aspects:(1)Based on the AC3 algorithm,an improved algorithm AC_AO is proposed to avoid the operation of the redundant arc back to the queue by guaranteeing the uniqueness of the arc.This mode of improving the arc-compatible algorithm by maintaining the uniqueness of the arc can form a framework and is applicable to AC series algorithms,including AC3 algorithm,AC2001 algorithm,AC3 rm algorithm.The improved algorithm framework AC_AO proposed in this paper is applied to AC3,AC2001,AC3 rm.The algorithm is compared with the original algorithm.The experimental results show that the AC series algorithm after applying the AC_AO algorithm framework can check 77% of the arc at most,and can reduce the CPU solution time by up to 30%.The AC_AO algorithm reduces the correction by reducing the arc check.The number of times the function is called,thereby improving the execution efficiency of the AC and shortening the execution time of the arc compatible algorithm.Applying the AC_AO algorithm to the process of maintaining the arccompatible algorithm is very meaningful for improving the efficiency of the solution.(2)A heuristic method based on genetic selection is proposed,which can adaptively select appropriate heuristic guidance variable selection for problem attributes.In this paper,the method is analyzed and described in detail,compared with the most commonly used default heuristic domOverWdeg heuristic and activityBased heuristic in the latest version of Choco solver,and two heuristic algorithms for genetic selection are made respectively.In the group experiment,one set of arc compatible algorithm selects AC3 algorithm,and the other set of arc compatible algorithm selects AC_AO algorithm to solve the problem of constraint satisfaction.The experimental results show that AC_AO algorithm is better than AC3 algorithm in solving the constraint satisfaction problem.The heuristic algorithm based on genetic selection has the highest efficiency of 2.35 times that of domOverWdeg heuristic and 2.26 times of activityBased heuristic.It is also superior to other heuristic algorithms in the robustness of solution efficiency.