3 Replies Latest reply: Feb 23, 2013 4:14 PM by rp0428 RSS

    Breadth First Search - Looking for Lesson Link, Sample Problem and Solution

    992949
      Hello and thank you all so so much!

      I'm attempting to solidify my understanding of the Breadth of First Search algorithm.
      I only know the basic idea of what this type of search is (that is, one searches the adjacent, sibling nodes before moving to the child nodes).
      I have absolutely no idea how this is implemented or kept track of or anything.

      I looked all around the net but found only the basic idea and very complex algorithm examples written in languages other than java.

      I please request a link to a good lesson that uses java that will actually teach me how to code this rather than just the concept.

      If nothing else, I want a simple problem for myself to work on so I can attempt to figure it out myself! The problem is the main thing for which I am looking.

      Edited by: 989946 on Feb 23, 2013 1:57 PM
        • 1. Re: Breadth First Search - Looking for Lesson Link, Sample Problem and Solution
          rp0428
          Welcome to the forum!
          >
          I'm attempting to solidify my understanding of the Breadth of First Search algorithm.
          I only know the basic idea of what this type of search is (that is, one searches the adjacent, sibling nodes before moving to the child nodes).
          I have absolutely no idea how this is implemented or kept track of or anything.

          I looked all around the net but found only the basic idea and very complex algorithm examples written in languages other than java.

          I please request a link to a good lesson that uses java that will actually teach me how to code this rather than just the concept.

          If nothing else, I want a simple problem for myself to work on so I can attempt to figure it out myself! The problem is the main thing for which I am looking.
          >
          Well there isn't really much to it. You have pretty much described the algorithm in your post
          >
          one searches the adjacent, sibling nodes before moving to the child nodes
          >
          What more did you think there was?

          Use a simple file folder hierarchy as an example. You start with a single ROOT folder and get a list of all children. Then you iterate the children without descending their subtree. Then you revisit each child and iterate each of their top-level folders with no descent into the subtrees.

          You keep repeating. During the process you discard any children that have been entirely processed so that you don't visit them again.

          You couldn't have looked on the net since there are plenty of links to example code and algorithms written in Java.

          Just search for 'java Breadth First Search'

          http://www.javacoffeebreak.com/tutorials/aisearch/chapter6.html
          http://blog.konem.net/java///index.php/breadth_first_search_algorithm_in_java_w?blog=1
          • 2. Re: Breadth First Search - Looking for Lesson Link, Sample Problem and Solution
            992949
            Hm. I've been looking at this whole thing a little incorrectly.
            Are trees implemented using an array?
            I don't think so anymore.

            Because an array forces everything on one "level" to be sibling and also all children to be children of every single element above them (so to speak).
            I.e.




            A

            | \

            B C

            | | \

            D E F

            Edit: Bleh, that array didn't come out with the spacing I intended. BC and children of A.
            E and F are children of C. D is a child of B.
            End of Edit.

            So if this is sort of understandable, the computer has no way to know that C and D are not in any form of relationship. And that E and B are not affiliated either.

            That first link used some sort of hierarchy class to add nodes as objects and create links between them. Is that website an official java website and is it using a class in the standard java libraries? Which one?

            I might as well give you a link to the problem I'm having. Bewary, it is rated as nearly impossible (for even professionals... or teachers. Same thing?)

            http://cemc.uwaterloo.ca/contests/computing/2012/stage1/juniorEn.pdf

            Scroll down to "A Coin Game"

            Here are two solutions:
            http://access.mmhs.ca/ccc/2012/s42012_kl.txt
            http://access.mmhs.ca/ccc/2012/J52012v2.txt

            So as you can see. Somehow I suppose one has to create the tree and then search it. Or create the children as one searches. Can you tell what they are doing?
            Don't waste your time if you can't I already appreciate the help.

            Edited by: 989946 on Feb 23, 2013 3:18 PM

            Edited by: 989946 on Feb 23, 2013 3:22 PM
            • 3. Re: Breadth First Search - Looking for Lesson Link, Sample Problem and Solution
              992949
              Just as my own breakdown of the problem:

              You get an initial config. That is your "master node" or something.

              Call a method for assessing possible moves.

              Each of those is another node.

              Check if that node is the goal.

              Move to the next possible node

              Check if that is the goal.

              Once all nodes are done.

              Go to first node.

              Call a method for assessing possible moves.

              Repeat.

              So the problem then becomes:

              How to define the node?

              Make a class that will return a node I guess.

              And its properties would be a configuration as well as a level. Keeping track of the level would be easy.

              Then the problem becomes how to define that unique configuration.

              I.e. lets say you have three coins: 3 2 1. Pretty simple, however, moving the 2 on the 3 makes:

              23, - , 0

              I see that they did something weird with base 5 there. I'm still trying to figure that out.