DLS – Depth-Limited Search

	private StackWithFastContains < Node > path;
	private int limit;

	public DLDFS(int limit) {
	    this.limit = limit;
	}

	public Node search(Node start, Predicate < Node > endPredicate) {
	    //Initial the stackWithFastContains
	    path = new StackWithFastContains < > ();
	    return searchForNode(start, endPredicate, limit);
	}

	private Node searchForNode(Node currentNode, Predicate < Node > toSearchFor, int depth) {
	    path.push(currentNode);

	    if (depth >= 0) {
	        //As long as we are depth > or equal zero, we are allowed to check for its predicate
	        //Return if the node equals the goal.
	        if (toSearchFor.test(currentNode))
	            return currentNode;

	        for (Node currentChildNode: currentNode.adjacent()) {
	            if (path.contains(currentChildNode))
	                continue; //If the current child is already in the stack path, continue.

	            //Recursively search for the result node.
	            Node result = searchForNode(currentChildNode, toSearchFor, depth - 1);
	            if (result != null)
	                return result;
	        }
	    }

	    //Limit reached, remove it from the stack.
	    path.pop();

	    //We found nothing, return nothing.
	    return null;
	}

Hinterlasse einen Kommentar

Please Login to comment
  Subscribe  
Notify of