关键词: 动态值启发式, 值排序, 约束满足问题, 弧相容技术, 启发式算法

Abstract: To improve the efficiency of solving constraint satisfaction problems, an algorithm for constraint satisfaction problems based on dynamic value ordering heuristics named Backtrack Dynamic Value ordering Heuristic algorithm (BT-DVH) was proposed. In the solving process, this algorithm absorbed the advantages of the previous heuristics, and made full use of the information generated in preprocess and arc consistency checking. To achieve dynamic value ordering heuristic, variable ordering heuristic was used, and the priorities of the values were changed dynamically to instantiate the variables. The efficiencies of the static and dynamic value ordering heuristics were compared, the advantages and shortcomings of the BT-DVH were analyzed. Tested by random problems and benchmark, the result showed this algorithm had a higher efficiency than classic mainstream algorithm.

Key words: dynamic value ordering heuristic, value ordering, constraint satisfaction problem, arc consistency, heuristic algorithm