The research on the improved light version max restricted path consistency algorithm with the learned value ordering heuristics

摘要

In order to further improve the efficiency of the existing maxRPC algorithm, this paper proposes a simple maxRPC3 algorithm, maxRPC3+, which is more suitable for searching, and combines these algorithms with learning value ordering heuristics. On the basis of the current maxRPC (max restricted path consistency) algorithm, an improved light version named maxRPC3+ is proposed, which uses the idea of survivors-first. The proposed algorithm abandons two data structures named LastAC and LastPC which are in the current maxRPC algorithm. While looking for the AC (arc consistency) supports and PC (path consistency) supports, the proposed algorithm always performs the consistency checks from the first value in the domain of variables, which not only preserves the search frame of the current maxRPC3 version, but also avoids adding additional data structure. The algorithm is easy to implement and understand. Experiment results show that the improved algorithm with the learned value ordering heuristics overwhelms the current version maxRPC over the best-known benchmark instances such as qcp, qwh, bqwh and random constraint satisfaction problem instances.