A Memoized Strategy for Preference Logic Programs

摘要

Preference logic programming (PLP) is an extension of constraint logic programming for declaratively specifying problems requiring optimization or comparison and selection among alternative solutions to a query. PLP essentially separates the programming of a problem itself from the criteria specification of its optimal solutions. The main challenge to implement a PLP system is that how the defined solution preferences take effects automatically on pruning suboptimal solutions and their dependents during the computation. In this paper, we present a tabled resolution, which applies dynamic programming strategies on solving PLP programs. Solution preferences can be properly propagated into recursionthrough a memoized recursive algorithm, so that a given recursive subgoal only needs to be solved once and always returns the preferred solutions. The strategy has been successfully implemented on a logic programming system. The experimental results show preference logic programming provides a declarative method for optimization problems without sacrificing efficiency.