APACS: A performance measurement architecture for constraint satisfaction

摘要

This paper presents a performance measurement architecture for objectively evaluating constraint atisfaction techniques. It examines and analyses the overheads involved in using the assumption-based dependency directed backtracking for solving constraint satisfaction problems. The problem of using a functional representation of contraints in the evaluation is described. To overcome this, an interactive performance measurement architecture has been developed to allow the benchmarking of new algorithms, for which assumption-based directed dependency backtracking, chronological backtracking, forward checking, conflict-directed backjumping and forward checking with conflict-directed backjumping are used for preliminary experimentation.