3 backtracking problems
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: 3 backtracking problems

  1. #1
    Join Date
    Jan 2011
    Posts
    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 (pseudo-code, 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.

  2. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,000

    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.

  3. #3
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,000

    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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center