Research On Symbol Algorithms Of Weighted Constraint Satisfaction Problems Based On RDS Technology

Many problems in computer science and artificial intelligence such as map coloring problem, production scheduling, product configuration, routing, logistics planning, resource allocation can be formulated as instance of the WCSP. WCSP solving goal is to find a fully assignment of the variables to domain values such that the total generation constraints value is minimized. The most basic method for solving WCSP is a depth-first branch and bound(DFBB) algorithm. RDS algorithm is obtained by modifying DFBB algorithm framework, which can improve the upper and lower bounds, but the efficiency of RDS algorithm depends on the efficiency of each problem. Structural records is one of the effective techniques to avoid redundant search, store the information which has solved in the search process, to determine whether you can reuse structural records already stored, thus improving computational efficiency.Because the RDS algorithm once only handle one constraint value, it can not simultaneously handle multiple constraint values, for the introduction of Algebraic Decision Diagram(ADD), which can efficiently represent and process data pooled, combination of state and can slow down due to the scale of the problem caused by excessive explosion. Therefore, we do the research based on RDS symbol algorithm of WCSP, the main research results are as follows:(1) Give improved RDS symbolic ADD algorithm. Based on RDS algorithm, we introduce an improved RDS symbolic algebraic decision diagram algorithm which replaces one search in DFBB by m successive searches on nested sub-problems. Through improving the most constraining variable(MCV) method of variable selection, a concept of RDS variable is introduced and conducted to nested decomposition of the original problem, and then decrease the number of sub-problems. In order to improve the efficiency of solving sub-problems, the bucket elimination algorithm is exploited to eliminate the non-RDS variables, which lead to decrease the number of variables in the sub-problem and improve the lower bound. For further improve the efficiency of the algorithm in the paper, with the ADD symbolic representation for WCSP, give the improved RDS Symbol ADD algorithm for WCSP.(2) Give the hybird RDS symbolic ADD algorithm. By study the relationship between the RDS variables, the RDSV-T sub-problem decomposition method is proposed. For solving the sub-problem, based on structural relationship between sub-problems, the structural records of sub-problems is stored, and convenience to reuse this structural records in subsequent sub-problem solving, thence the problem solving efficiency is improved. With the ADD symbolic representation for WCSP, the hybird RDS symbolic ADD algorithm is gived.(3) Experiments on random problems are tested, and the results show that the proposed algorithm outperform the RDS algorithm, EDAC-FC-DFBB algorithm and DFBB-ADD algorithm.