Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Knuth Algorithm

  1. Jun 3, 2012 #1

    woundedtiger4

    User Avatar

    Hi all, at http://en.wikipedia.org/wiki/Knuth's_Algorithm_X in the example I don't understand that why not "A" is in the final solution & only B, D & F are in the final solution whereas "A" was selected at Level 1
     
    woundedtiger4, Jun 3, 2012
  2. jcsd
    Phys.org - latest science and technology news stories on Phys.org
  3. Jun 3, 2012 #2

    woundedtiger4

    User Avatar

    [STRIKE]bump[/STRIKE]

    plus why at the level 1 the branch containing "D" (i.e. containing 0, 1, 1, 1 in columns 2, 3, 5 & 6) was terminated unsuccessfully?
     
    Last edited: Jun 3, 2012
    woundedtiger4, Jun 3, 2012
  4. Jun 3, 2012 #3

    NemoReally

    User Avatar

    The intent, as far as I understand it, is to find a combination of rows that include every number from 1 to 7 but where each number only occurs in at most one row.

    The algorithm seems to work by picking the row (A) that has the most numbers in it and then trying to find a combination of the other rows that have the numbers that aren't in A.

    Having selected A (in this case), it proceeds by removing any sets that have a number in common with A (in this case, B,C,E and F). This is because any combination of B,C,E or F with A will have at least one multiple of '1', '4' or '7'. This only leaves row D as a possible match for A.

    However, row D doesn't contain a '2' and neither does A, so the combination of A and D is not an exact cover, hence the algorithm terminates and goes to test for another combination.

    NR
     
    NemoReally, Jun 3, 2012
  5. Jun 4, 2012 #4

    woundedtiger4

    User Avatar

    thank you sooooooooooo much, you really helped me in understanding it.
     
    woundedtiger4, Jun 4, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for Knuth Algorithm Date
C/++/# Is there a flaw in my longest common subsequence algorithm? Feb 24, 2018
C/++/# Finding duplicates algorithm Jan 20, 2018
Perceptron algorithm initial vector Dec 28, 2017
C/++/# What should I be most familiar w/for C++ Data Structs & Algorithms Dec 1, 2017