1
$\begingroup$

I want to solve the two partition problem (https://en.wikipedia.org/wiki/Partition_problem) using an uninformed search algorithm (BFS or uniform cost).

The states can be represented by three sets S1,S1,S where the set S contains unassigned values and S1 and S2 the values assigned to each partition respectively. At the initial state S will contain all values and S1 and S2 will be empty. The actions consist in moving a value from S to S1 or S2. The objective is to find a complete assignation (S is empty) where abs(sum(S1)-sum(S2)) is minimum. As you can see I have all elements but the cost of the actions.

  • How can I assign costs to the actions in order to apply one of those algorithms? (Costs must be positive.)

I know it is not the best way to solve this problem but there must be a way to do it because the problem is formulated this way in the book.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.