## Description

FUNDAMENTALS OF ARTIFICIAL INTELLIGENCE – CS161

Programming Assignment 3 –

DO NOT CONSULT ANY OUTSIDE REFERENCES OR SOURCES FOR THIS ASSIGNMENT

This assignment concerns the problem of number partitioning. Given a set of

integerts, the task is to divide them into two mutually exclusive and

collectively exhaustive subsets, so that the sums of the numbers in each subset

are as nearly equal as possible. For example, given the set (1 4 9 16 25), an

optimal partition divides the numbers into the sets (1 25) and (4 9 16). Since

the sum of the numbers in the first set is 26, and the sum of the numbers in

the second set is 29, the difference of the sums is 3, and this is the smallest

difference that can be achieved in this case.

Your task is to write a pure LISP program to optimally partition sets of

integers. Your top-level function, called PARTITION, must take a single

argument which is a list of non-negative integers, and return an optimal

partition of those integers. The value returned should be a three-element

list, where the first element is the final partition difference, and the next

two elements are the subsets that achieve that value. For example,

(PARTITION ‘(1 4 9 16 25)) might return (3 (1 25) (4 9 16)). The order of the

integers in the lists, and the order of the two lists, is irrelevant.

You will need to write a function to generate test data. The common-lisp

function (random n) will return a random number in the range zero to n. Number

partitioning problems generally become more difficult with increasing magnitude

of the numbers, so be sure to test your program against integers at least as

large as a million. Note that it is feasible to optimally solve instances with

very large numbers of integers if the integers are small.

This problem is NP-Complete, meaning that you (almost certainly) have to do an

exponential search to find an optimal solution. DO NOT IMPLEMENT A

POLYNOMIAL-TIME ALGORITHM, BECAUSE IT WILL NOT PRODUCE CORRECT ANSWERS FOR ALL

PROBLEM INSTANCES. You are encouraged to first implement and experiment with a

simple search algorithm to solve the problem. In order to solve instances with

more and larger integers, however, you will have to improve the efficiency of

your algorithm. Hacking your code will not buy you big gains in performance,

but thinking about and experimenting with your algorithm will. Remember that

all your partitions must be optimal. I’m not aware of any useful heuristic

evaluation functions for this problem.

If you are having trouble getting started, I suggest that you first implement a

simpler version of this assignment that only returns the numerical difference

of the final partition, and not the partition itself. If you call this

function SIMPART, and you don’t get PARTITION working correctly, then you’ll

receive partial credit for SIMPART.