Dynamic Programming with Tabling

Dynamic programming is the name for a general strategy used in algorithms when one organizes the computation to be done in such a way that sub-problems are evaluated only once instead of many times. With this description of dynamic programming, one can see that the tabling strategy of Prolog systems is a dynamic programming strategy. That is, regardless of how the computation is structured by the programmer, tabling ensures that sub-problems are evaluated only once. So this suggests that problems amenable to dynamic programming solutions might be particularly appropriate for evaluating with tabling.

The task of this work is to write Prolog programs that take advantage of tabling to solve the two problems described below. The work must be described in a report and sent by email to Ricardo Rocha until February 22, 2008. The report should contain the following contents:

Student identification.
Brief description of the algorithms used (for each problem).
The Prolog code that solves the problem (for each problem).
Experiments with different inputs showing the running times with and without tabling (for each problem). To run the experiments you can use the XSB Prolog system or the Yap Prolog system.

Problem I: Knap-Sack

The first problem we will consider is the knap-sack problem. The idea is that we have a knap-sack and a bunch of items of various sizes to put in it. The question is whether there is a subset of the items that will fit exactly into the knap-sack. We will represent the items and their sizes by using a set of facts item/2, where item(3,5) would mean that the third item is of size 5.

Write a Prolog predicate ks(+NI,+SK) to solve the problem, where NI is the number of items and SK is the size of the knap-sack. The predicate should return true if there is a subset of items 1,...,NI that sums to SK, and no otherwise. The ks/2 predicate just finds whether a packing of the knapsack exists; it doesn't return the exact set of items that fit. Write a different predicate ksi(+NI,+SK,-LI) that returns in the third argument, LI, the list of items that fit in the knap-sack. Note that if you table ksi/3 that might then build an exponential-sized table. For example with every item of size one, there are exponentially many items to include to make a sum. So instead of simply tabling ksi/3, you should only table ks/2 and then use it in the definition of ksi/3.

Example

% Prolog representation for the items
item(1,3).
item(2,7).
item(3,5).
item(4,2).
item(5,1).


% Considering the items above and a knap-sack of size 11 then the answer is yes
?- ks(5,11).
yes


% ... and the list of items that sum to 11 is [5,2,1] and [5,4,3,1]
?- ksi(5,11,L).

L = [5,2,1] ;
L = [5,4,3,1] ;
no

Problem II: Sequence Comparisons

Another interesting problem where dynamic programming can be applicable is in the comparison of sequences. Given two sequences A and B, consider that we want to determine the minimal number of operations needed to turn A into B. The allowable operations are: insert a new symbol, delete a symbol, and replace a symbol (each operation costs one unit).

Write a Prolog predicate turn(+SA,+SB,-N) to solve the problem, where SA and SB are the sizes of sequences A and B, respectively, and N is the output argument that gives the minimal number of operations needed to turn A into B. Consider that the sequences A and B are represented by a list of facts, a/2 and b/2 respectively, where the first argument gives the position in the sequence of the symbol represented in the second argument.

Example

% Prolog representation for sequence A: 'abbcbab'
a(1,a).
a(2,b).
a(3,b).
a(4,c).
a(5,b).
a(6,a).
a(7,b).


% Prolog representation for sequence B: 'babba'
b(1,b).
b(2,a).
b(3,b).
b(4,b).
b(5,a).


% Considering the two sequences above then the minimal number of operations needed to turn A into B is 4
?- turn(7,5,N).
N = 4