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.


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.