
January 8th, 2011, 10:55 AM
#1
3 backtracking problems
Hello, I have a huge list of problems but I'm having difficulties with some of them. I need algorithms for these 3 problems (pseudocode, c++, java or c#) as I can't find solutions for them:
1. For a set of n integer elements, generate all the subsets of that set that have the sum of all their elements an odd number.
2. Generate all the decompositions of a natural number n in sums of prime numbers.
3. For a given integer, n, generate all the growing functions f : {1, 2, 3, ..., n} > {1, 2, 3, ..., n} with the property: f(x)<=x for any x in {1, 2, ..., n}.
Any help is appreciated! Thank you.

February 5th, 2011, 04:43 PM
#2
Re: 3 backtracking problems
These appear to be homework problems, so I won't provide their solutions. I am, however, happy to explain how backtracking works. Algorithms that find solutions to constraint problems by backtracking all work by constructing a solution and at each step in the construction check to make sure that no constrains prevent further construction. If they are, it goes back a step and tries a different construction. For example:
Suppose you have for workers who can each work on the following days of the week, and only one worker may work on any given day:
Code:
Alice MTWR
Bob TW
Carl M W
Dory MT
A backtracking algorithm to assign them days to work would execute as follows:
(1) Start with Alice and assign her to work on the Monday (the first option)
(2) Check: Does everyone else still have a day they can work on? Yes.
(3) Assign Bob (2nd person in the list) to work on Tuesday.
(4) Check: Does everyone still have a day they can work on? No, Dory cannot, so...
(5) Backtrack: Assign Bob to work on the next day available instead (Wednesday)
(6) Check: Does everyone still have a day they can work on? No, Carl cannot, so...
(7) Backtrack: Assign Bob to work on the next day available for him, but  oh no  he is out of days to work, so...
(8) Backtrack: Assign Alice to the next day to work (Tuesday).
(9) Continue with Bob... The algorithm flow should be clear by now...
Does that help? You should be able to apply the 'construct solution and check constrains at each step' procedure to your problems. For more information, I recommend Russell and Norvig's excellent book on Artificial Intelligence or the Backtracking Wikipedia page or this tutorial.
I hope that gets you started!
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

February 5th, 2011, 04:47 PM
#3
Re: 3 backtracking problems
I should also add that you can get better performance out of backtracking solutions if you try to make assignments to the most constrained choices first. In my example, that means assigning days to Bob, Carl or Dory (because they each have 2 possible days they can work) before assigning Alice (since she is the least constrained). This makes sense and is how you would do this in your head: 'Okay, Let Dory have Monday, and that'd mean Carl'd have to work Wednesday (b/c now Carl is only one option left after the assignment to Dory we assigned him after Dory), ....'
If you want to program for fun, backtracking algorithms are popular ways of solving Sodoku puzzles programatically.
Last edited by BioPhysEngr; February 5th, 2011 at 04:48 PM.
Reason: fix error in example
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
