Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Page 1 of 2 12 LastLast
Results 1 to 25 of 27

Thread: Depth-Limited Search using Recursive Backtracking...please help!

  1. #1
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Depth-Limited Search using Recursive Backtracking...please help!

    Writing a Depth-Limited Search Java Class in an Artificial Intelligence course. I have included the code for my class below and attached a flow diagram I came up with. This project is based on the "Vacuum World" problem in 'Artificial Intelligence: A Modern Approach'.

    The class compiles and runs correctly with all the other classes and packages. Those files are instructor provided and work with a Breadth-First Search Class he included. The program successfully finds the goal state and returns the goal state to the user if the program starts in the goal state. Additionally, the program successfully transverses through the search space using DLS and finds a goal state. I used the println in the recursive method to show that it finds a goal state.

    What I am having problem with is the recursion. When I use the recursion backtracking to find a "goal state", the program finds the goal state, however, it keeps searching the searchspace. What I need help with is when it finds a "goal state", I need the program and all previously threaded recursion calls to stop and return the first found "goal state".

    If needed I can upload all of the files when I get off of work. But I hope it's an easy answer.

    package ai.searches;
     
    import ai.Problem;
    import ai.Solution;
    import ai.Successor;
    import dataStructures.Iterator;
    import dataStructures.List;
     
    public class DepthLimitedSearch extends AbstractSearch
    {
        int depthLimit;
     
        public DepthLimitedSearch(Problem p, int maxDepth)
        {
            super(p);
            this.depthLimit = maxDepth;
        }
     
        public Solution search()
        {
            // stores the solution to return
            Solution solution = null;
            Successor solutionNode = null;
     
            solutionNode = recursiveExpandNode( (Successor)problem.getInitialState() );
     
            if( solutionNode != null ) solution = new Solution( solutionNode, solutionNode.getDepth() );
     
            return solution;
        }
     
        private Successor recursiveExpandNode( Successor node )
        {
            Successor output = null;
     
            // check for goal state
            if( problem.isGoalState( node.getState() ) ) {
                System.out.println( "Yes");
                return node;
            }
     
            // check for depth
            if( node.getDepth() > ( this.depthLimit - 1 ) ) return null;
     
            List successorsList = problem.getSuccessorFunction().getSuccessors(node);
     
            if( !successorsList.isEmpty() )
            {
                for( Iterator itr = successorsList.iterator(); itr.hasNext(); itr.next() )
                {
                    // get current Successor
                    Successor current = (Successor)itr.getCurrent();
     
                    // set parent
                    current.setParent( node );
     
                    // set depth
                    current.setDepth(node.getDepth() + 1);
     
                    System.out.println( current.toString() );
     
                    // recursively expands search space
                    output = recursiveExpandNode( current );
                    if( problem.isGoalState( current.getState() ) ) break;
                }
            }
            return output;
        }
    }
    Attached Images Attached Images


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    What I need help with is when it finds a "goal state", I need the program and all previously threaded recursion calls to stop and return the first found "goal state".
    Can you use what the method returns to tell the caller that the goal has been found and to stop further searching and to return that results to its caller?

  3. #3
    Member
    Join Date
    Jun 2011
    Posts
    56
    Thanks
    2
    Thanked 7 Times in 6 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    I think your termination criteria is wrong. You should unwind the recursion when a goal is found anywhere in the tree (not just when the current node is a goal). A simple solution is to have a Boolean member variable that signals a goal is found somewhere, and then return from every node when that is set. For more complex goals with a range of values, you may need to keep track of the best values at each internal node.

  4. #4
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Yep, I am not terminating properly. If someone would please provide some code to try that would be awesome.

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Can you provide a small program that compiles and executes to demonstrate your problem?
    Your posted code is incomplete and uses 3rd party classes.

  6. #6
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Quote Originally Posted by Norm View Post
    Can you provide a small program that compiles and executes to demonstrate your problem?
    Your posted code is incomplete and uses 3rd party classes.
    Attached is the source code for the entire program. The class I am working on is in src > ai > searches > DepthLimitedSearch.java and the main class is src > VacuumWorld > VacuumWorldDriver.java

    DLS.zip

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    There are 76 source files in that zip. What do you expect anyone to do with all that code?

  8. #8
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Executable code was requested. I am only struggleing with one method in one class. As mentioned above I am having problems terminating all recursive branches when a goal state is found. The method is called recursiveExpandNode(), see details in my initial post above.

  9. #9
    Member
    Join Date
    Jun 2011
    Posts
    56
    Thanks
    2
    Thanked 7 Times in 6 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Quote Originally Posted by Zaxx81 View Post
    Executable code was requested. I am only struggleing with one method in one class. As mentioned above I am having problems terminating all recursive branches when a goal state is found. The method is called recursiveExpandNode(), see details in my initial post above.
    Did you try my suggestion ? It is pretty straight forward and I can not see why it will not work.
    Declare a member variable goalFound.
    Boolean goalFound;
    Set it to false initially (in constructor)
    goalFound = false;
    Then wherever you test for termination (isGoalState(node)) , do the following instead
    if(goalFound || problem.isGoalState( node.getState() ) ) {
         System.out.println( "Yes");
         goalFound = true;
         return node;
    }

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    I don't see many printlns for debugging in that code. How are you debugging it?

  11. #11
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Gonna try the boolean idea after lunch. Attached is a flow diagram for just that method. The problem is when a recursive node is terminated, the previous recursive branch is still in the "for loop", so it goes to the next successor in the List.

    There is a println inside the recursiveExpandNode. The print shows that it finds and recognizes the goal state but then it keeps going through the search space.

    // check for goal state
    if( problem.isGoalState( node.getState() ) ) {
       System.out.println( "Yes");
       return node;
    }
    recursiveExpandNode diagram.jpg

  12. #12
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Quote Originally Posted by dabdi View Post
    Did you try my suggestion ? It is pretty straight forward and I can not see why it will not work.
    Declare a member variable goalFound.
    Boolean goalFound;
    Set it to false initially (in constructor)
    goalFound = false;
    Then wherever you test for termination (isGoalState(node)) , do the following instead
    if(goalFound || problem.isGoalState( node.getState() ) ) {
         System.out.println( "Yes");
         goalFound = true;
         return node;
    }
    How do I stop the for loop? Because even with goalFound, the other Successor nodes in the this will return themselves or null...

  13. #13
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Returning something from a successful search method invocation seems like a good way of terminating your search. Can you continue / break your loop depending on the return value of the search method? Here's a little example that uses depth-limited recursion (hard-coded at 5) and a return value to determine when to give up searching:
    package com.javaprogrammingforums.domyhomework;
     
    import java.util.Scanner;
     
    public class DepthLimitedSearch
    {
      private static final int DEPTH_LIMIT = 5;
      private static final char[] CHARS = "abcdefghijklmnopqrstuvwxyz".toCharArray();
      public static void main(String[] args)
      {
        System.out.println("Enter a word to search for:");
        String word = new Scanner(System.in).nextLine();
        int effort = searchFor(word, 0);
        if (effort < 0)
          System.out.println("Couldn't find '" + word + "' after " + (-effort) + " attempts");
        else
          System.out.println("Found! After " + effort + " attempts");
      }
      private static int searchFor(String word, int index)
      {
        if (index > DEPTH_LIMIT)
          return -1; // not found
        int tries = 0;
        for (char c : CHARS) // 'search' for matching character at this depth
        {
          tries++;
          if (word.charAt(index) == c)
          {
            if (++index < word.length())
            {
              int moreTries = searchFor(word, index);
              if (moreTries < 0)
                return moreTries - tries;
              return tries + moreTries;
            }
            else // found it
              return tries;
          }
        }
        return -tries;
      }
    }
    What principle of your problem makes the solution you seek more difficult than this?

    edit: This isn't substantially different from dabdi's suggestion of a redundant flag with the right scope.
    Last edited by Sean4u; October 1st, 2011 at 01:54 PM. Reason: edit: same same

  14. #14
    Member
    Join Date
    Jun 2011
    Posts
    56
    Thanks
    2
    Thanked 7 Times in 6 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    How do I stop the for loop? Because even with goalFound, the other Successor nodes in the this will return themselves or null...
    You have isGoalState inside the for loop as well so make the same change.
    // recursively expands search space
       output = recursiveExpandNode( current );
       if( problem.isGoalState( current.getState() ) ) break;
    change the above to
     output = recursiveExpandNode( current );
     if(goalFound || problem.isGoalState( current.getState() ) ) {
          goalFound = true;
          break;
     }
    This simple method is used even in threaded applications where many threads participate in finding one goal.

  15. #15
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    even in threaded applications
    That's your solution's natural ground, where it's behaving not only as a success flag but also as a communications channel. If the task in hand is 'can a matching item be found?', then a Boolean / boolean flag makes sense. If it's 'find the one-and-only matching item', then a reference (or AtomicReference) may make more sense. If it's possible that more than one solution exists, then threads can check a shared result list to see if it's not empty.

    For the single threaded case, it ought to be possible to propagate 'success' back through the invocation chain, terminating each level as it goes, without the need for a shared variable.

  16. #16
    Member
    Join Date
    Jun 2011
    Posts
    56
    Thanks
    2
    Thanked 7 Times in 6 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Quote Originally Posted by Sean4u View Post
    That's your solution's natural ground, where it's behaving not only as a success flag but also as a communications channel. If the task in hand is 'can a matching item be found?', then a Boolean / boolean flag makes sense. If it's 'find the one-and-only matching item', then a reference (or AtomicReference) may make more sense. If it's possible that more than one solution exists, then threads can check a shared result list to see if it's not empty.

    For the single threaded case, it ought to be possible to propagate 'success' back through the invocation chain, terminating each level as it goes, without the need for a shared variable.
    Yes proper back propagation is required for more complex goals. The OP's problem is very simple as to not require advanced solutions. He can even use a longjump once he encounters a goal at a leaf node but that is a very bad design. When the goal is not as clear cut, for example if it is finding shortest path, best action (i.e move in a zero-sum game etc), one would have to do proper back-propagation of updating the internal nodes. I am sure he will learn about those later. I still use volatile variables with atomic operations in my c++ projects for synchronization, to quit program on user interrupt, or when one of the worker threads find out work at the current node need to be stopped etc...

  17. #17
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Finally got it to work, with everyone's help. I ended up creating a class variable "Boolean goalFound" and "Successor goalNode". So once I find a goal node, I set goalFound to true and store it in goalNode. This ensured I only returned the first goal node. I still had the problem of the program continuing through the for loops of every recusive branch. So I added a check at the beggining of the for loop to see if goalFound was true, which instead of returning null like I thought, I used break on the for statement so it doesn't iterate any more for that branch.

    The sad thing is this is 1 of my last two assignments for my Masters in Computer Science. What sucks is that I did Computer Engineering for my undergrad, so we didn't have any programming focused classes beyond data structures, just classes that we programmed in. Never had to do anything more complex with recursion than fibonnacci number.

    Below is the final code for that class. Thanks again!

    public class DepthLimitedSearch extends AbstractSearch
    {
        int depthLimit;
        Boolean goalFound;
        Successor goalNode;
     
       public DepthLimitedSearch(Problem p, int maxDepth)
        {
            super(p);
            this.depthLimit = maxDepth;
            this.goalFound = false;
            this.goalNode = null;
        }
        public Solution search()
        {
            // stores the solution to return
            Solution solution = null;
            Successor solutionNode = null;
     
            solutionNode = recursiveExpandNode( (Successor)problem.getInitialState() );
     
            if( this.goalNode != null ) solution = new Solution( this.goalNode, this.goalNode.getDepth() );
            return solution;
        }
     
        private Successor recursiveExpandNode( Successor node )
        {
            Successor output = null;
     
            // check for goal state
            if( !this.goalFound && problem.isGoalState( node.getState() ) ) {
                System.out.println( "Yes");
                this.goalFound = true;
                this.goalNode = node;
                return node;
            }
     
            // check for depth
            if( node.getDepth() > ( this.depthLimit - 1 ) ) return null;
     
            List successorsList = problem.getSuccessorFunction().getSuccessors(node);
     
            if( !successorsList.isEmpty() )
            {
                for( Iterator itr = successorsList.iterator(); itr.hasNext(); itr.next() )
                {
                   if( this.goalFound ) break;
     
                    // get current Successor
                    Successor current = (Successor)itr.getCurrent();
     
                    // set parent
                    current.setParent( node );
     
                    // set depth
                    current.setDepth(node.getDepth() + 1);
     
                    System.out.println( current.toString() );
     
                    // recursively expands search space
                    output = recursiveExpandNode( current );
                    if( problem.isGoalState( current.getState() ) ) break;
                }
            }
            return output;
        }
    }

  18. #18
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    New code puzzle. The first time I run the program the menu of test cases print in the wrong order. When it loops back to give the user a chance to enter another case the menu order is correct. Can anyone see anything wrong in the attached code? Also attached a screenshot.



    package VacuumWorld.testing;
     
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
     
    import VacuumWorld.Environment;
    import VacuumWorld.Location;
    import VacuumWorld.VacuumSearchAgent;
     
    import dataStructures.HashMap;
    import dataStructures.Iterator;
     
     
    /**
     *	Class VacuumWorldDLSTester.
     *	<p>
     *	This class runs test cases for testing a depth-limited search for the
     *	VacuumWorld problem.
     *	<p>
     *	Written by:	Roger West
     *				University of Illinois at Springfield
     *				01/2006
     */
    public class VacuumWorldDLSTester
    {
     
    	/************
    	 *	constants
    	 ***********/
     
    	/** indicates all available tests should be run in batch mode */
    	private final static String RUN_ALL_TESTS = "ALL";
     
     
    	/*************
    	 *	attributes
    	 ************/
     
    	/** the collection of TestCase objects available for testing */
    	private HashMap testCases;
     
     
    	/***************
    	 *	constructors
    	 **************/
     
    	/**
    	 *	Create a new VacuumWorldDLSTester with an empty collection of test cases.
    	 */
    	public VacuumWorldDLSTester()
    	{
    		// create HashMap for storing test cases
    		testCases = new HashMap();
     
     
    	}
     
     
    	/**********
    	 *	methods
    	 *********/
     
    	/**
    	 *	Query user for depth limit to use for testing.
    	 */
    	private int queryDepth()
    	{
    		int depth = 0;
     
    		try
    		{
    			BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
     
    			System.out.print("\nEnter depth limit for DepthLimitedSearch: ");
     
    			String input = bfr.readLine();
     
    			depth = Integer.parseInt(input);
    		}
    		catch (Exception e)
    		{
    			depth = 0;
    		}
     
    		return depth;
    	}
     
     
    	/**
    	 *	Populate collection of test cases.  Currently all test cases are hard-
    	 *	coded inside this method.
    	 *
    	 *	@param	depth	depth limit for testing the depth-limited search
    	 */
    	private void populateVacuumWorldDLSTestCases(int depth)
    	{
    		// test case object
    		VacuumWorldDLSTestCase tc;
     
    		// test case id
    		String id;
     
    		// test case description
    		String description;
     
    		// the test case
    		Environment test;
     
    		// test case expected result
    		String expectedResult;
     
    		//	Test Case #1:
    		id = "1";
    		description = "D-" + depth + " LEFT (dirty) (vacuum agent present) | RIGHT (dirty)";
    		expectedResult = "Optimal solution: Suck --> Move Right --> Suck";
    		test = new Environment();
    		test.addLocation(Location.LEFT, new Location(Location.LEFT, true));
    		test.addLocation(Location.RIGHT, new Location(Location.RIGHT, true));
    		test.setVacuumAgentLocation(Location.LEFT);
    		tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult);
    		testCases.add(id, tc);
     
    		//	Test Case #2:
    		id = "2";
    		description = "D-" + depth + " LEFT (dirty) | RIGHT (dirty) (vacuum agent present)";
    		expectedResult = "Optimal solution: Suck --> Move Left --> Suck";
    		test = new Environment();
    		test.addLocation(Location.LEFT, new Location(Location.LEFT, true));
    		test.addLocation(Location.RIGHT, new Location(Location.RIGHT, true));
    		test.setVacuumAgentLocation(Location.RIGHT);
    		tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult);
    		testCases.add(id, tc);
     
    		//	Test Case #3:
    		id = "3";
    		description = "D-" + depth + " LEFT (clean) (vacuum agent present) | RIGHT (clean)";
    		expectedResult = "Optimal solution: Do nothing";
    		test = new Environment();
    		test.addLocation(Location.LEFT, new Location(Location.LEFT, false));
    		test.addLocation(Location.RIGHT, new Location(Location.RIGHT, false));
    		test.setVacuumAgentLocation(Location.LEFT);
    		tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult);
    		testCases.add(id, tc);
     
    		//	Test Case #4:
    		id = "4";
    		description = "D-" + depth + " LEFT (clean) | RIGHT (clean) (vacuum agent present)";
    		expectedResult = "Optimal solution: Do nothing";
    		test = new Environment();
    		test.addLocation(Location.LEFT, new Location(Location.LEFT, false));
    		test.addLocation(Location.RIGHT, new Location(Location.RIGHT, false));
    		test.setVacuumAgentLocation(Location.RIGHT);
    		tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult);
    		testCases.add(id, tc);
     
    		//	Test Case #5:
    		id = "5";
    		description = "D-" + depth + " LEFT (clean) (vacuum agent present) | RIGHT (dirty)";
    		expectedResult = "Optimal solution: Move Right --> Suck";
    		test = new Environment();
    		test.addLocation(Location.LEFT, new Location(Location.LEFT, false));
    		test.addLocation(Location.RIGHT, new Location(Location.RIGHT, true));
    		test.setVacuumAgentLocation(Location.LEFT);
    		tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult);
    		testCases.add(id, tc);
     
    		//	Test Case #6:
    		id = "6";
    		description = "D-" + depth + " LEFT (clean) | RIGHT (dirty) (vacuum agent present)";
    		expectedResult = "Optimal solution: Suck";
    		test = new Environment();
    		test.addLocation(Location.LEFT, new Location(Location.LEFT, false));
    		test.addLocation(Location.RIGHT, new Location(Location.RIGHT, true));
    		test.setVacuumAgentLocation(Location.RIGHT);
    		tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult);
    		testCases.add(id, tc);
     
    		//	Test Case #7:
    		id = "7";
    		description = "D-" + depth + " LEFT (dirty) (vacuum agent present) | RIGHT (clean)";
    		expectedResult = "Optimal solution: Suck";
    		test = new Environment();
    		test.addLocation(Location.LEFT, new Location(Location.LEFT, true));
    		test.addLocation(Location.RIGHT, new Location(Location.RIGHT, false));
    		test.setVacuumAgentLocation(Location.LEFT);
    		tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult);
    		testCases.add(id, tc);
     
    		//	Test Case #8:
    		id = "8";
    		description = "D-" + depth + " LEFT (dirty) | RIGHT (clean) (vacuum agent present)";
    		expectedResult = "Optimal solution: Move Left --> Suck";
    		test = new Environment();
    		test.addLocation(Location.LEFT, new Location(Location.LEFT, true));
    		test.addLocation(Location.RIGHT, new Location(Location.RIGHT, false));
    		test.setVacuumAgentLocation(Location.RIGHT);
    		tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult);
    		testCases.add(id, tc);
     
    	}
     
     
    	/**
    	 *	Display menu of available test cases and allow user to choose test case
    	 *	to run.
    	 */
    	public void test()
    	{
    		int maxDepth = queryDepth();
     
    		populateVacuumWorldDLSTestCases(maxDepth);
     
    		System.out.println("\nChoose a test case:");
    		for (Iterator itr = testCases.iterator(); itr.hasNext(); itr.next())
    		{
    			VacuumWorldDLSTestCase tc = (VacuumWorldDLSTestCase)itr.getCurrent();
     
    			System.out.println(	"    " + tc.getID() + ": "
    								+ tc.getDescription());
    		}
    		System.out.println();
     
    		try
    		{
    			BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
     
    			String testID = bfr.readLine();
     
    			testID.trim();
     
    			runTest(testID);
     
    			test();
    		}
    		catch (Exception e)
    		{
    			e.printStackTrace();
    		}
     
    	}
     
     
    	/**
    	 *	Execute the test case corresponding to the specified ID.
    	 *
    	 *	@param	id	the unique identifier of the test case to run
    	 */
    	private void runTest(String id)
    	{
    		VacuumWorldDLSTestCase tc = (VacuumWorldDLSTestCase)testCases.get(id);
     
    		if (tc != null)
    		{
    			VacuumSearchAgent agent = tc.getAgent();
     
    			agent.solveProblem();
    		}
    		else
    		{
    			System.out.println("Error - chosen ID does not match any existing test cases!");
    		}
    	}
     
     
    	/**
    	 *	Execute all test cases in batch mode.
    	 *
    	 *	Currently not implemented.
    	 */
    	private void runAllTests()
    	{
     
    	}
    }

  19. #19
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    D'oh! duplicate post...
    Last edited by Sean4u; October 1st, 2011 at 04:09 PM. Reason: dup of next post

  20. #20
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Uh? HashMap isn't in any way sorted, so the out-of-order is to be expected. Changing order is as weird as in-order. TreeMap would give you sorting, LinkedHashMap reliable ordering. Do you remove / put the values, perhaps with a change of data that would effect their hashCode()?

  21. #21
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Quote Originally Posted by Sean4u View Post
    Uh? HashMap isn't in any way sorted, so the out-of-order is to be expected. Changing order is as weird as in-order. TreeMap would give you sorting, LinkedHashMap reliable ordering. Do you remove / put the values, perhaps with a change of data that would effect their hashCode()?
    That was instructor provided and it is in the correct order every time it loops back. I can live with it for a HW assignment, but it just kind of bugs me.

  22. #22
    Member
    Join Date
    Jun 2011
    Posts
    56
    Thanks
    2
    Thanked 7 Times in 6 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Quote Originally Posted by Zaxx81 View Post
    New code puzzle. The first time I run the program the menu of test cases print in the wrong order. When it loops back to give the user a chance to enter another case the menu order is correct. Can anyone see anything wrong in the attached code? Also attached a screenshot.
    As sean4u pointed out hashmap uses hash tables i.e (key,value) pair, so it is not sorted in any way. Interestingly it seems it is non-deterministic as well (you get different sequence every time you run the program). This is bad for debugging. I suspect it is because different set of hash keys (random numbers) are generated every time. May be there is a way to set the random number seed to a constant value.
    More here is the Java HashMap keySet() iteration order consistent? - Stack Overflow

  23. #23
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    You should use LinkedHashMap or TreeMap if you care about the order of your iterators. I'm agog at the order *changing* though - I'd be interested to see an SSCCE that demonstrated that behaviour. I can't help thinking the 'ordered' result is pure luck or perhaps a bad hashCode() implementation.

  24. #24
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    Waidaminnit! Since when did HashMap have an iterator() method?
    import dataStructures.HashMap
    That was instructor provided
    :facepalm:

  25. #25
    Junior Member
    Join Date
    Sep 2011
    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Depth-Limited Search using Recursive Backtracking...please help!

    The order is always the same the first time: 4, 5, 6, 7, 8, 1, 2, 3 and everytime after that it is 1, 2, 3, 4, 5, 6, 7, 8.

Page 1 of 2 12 LastLast

Similar Threads

  1. Replies: 2
    Last Post: July 24th, 2011, 05:29 PM
  2. Replies: 1
    Last Post: January 27th, 2011, 08:13 AM
  3. Q:BackTracking Algorithm
    By Cross`17 in forum Algorithms & Recursion
    Replies: 0
    Last Post: April 17th, 2010, 11:33 PM
  4. recursive search of all local disks
    By ttsdinesh in forum Java Theory & Questions
    Replies: 4
    Last Post: September 27th, 2009, 08:23 AM
  5. How can i create fake IP addresses to extract information for the DB?
    By neomancer in forum Java Theory & Questions
    Replies: 4
    Last Post: May 8th, 2009, 04:54 AM