Solved

DFS ALGORITHM

Posted on 2007-03-26
4
2,351 Views
Last Modified: 2013-11-23
Hi experts
I am writing a program to do forward planning and solve a puzzle, I need some help on how to apply a code for DFS search with cycle checking!
I dont know who to travesre the graph, and in which order save my frontier!
0
Comment
Question by:eternity5219
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
4 Comments
 

Author Comment

by:eternity5219
ID: 18797147
I am looking for the recursive definition of DFS without a graph. all I am given is start node, goal node, and available action and I need to build my paths and in case I am not in the right path , bach track to where I was!
0
 
LVL 10

Accepted Solution

by:
ADSLMark earned 500 total points
ID: 18798722
Ok, a very basic solution I would say looks like this:

- Keep a stack with the current path.
- Add node to the stack (push)
- Check for cycles by looking at the current path (only path cycles are checked!!)
- If the current node (top node) equals the goal node, return true
- Otherwise, recursive call all possible actions
- If one returns true, return true as well (solution has been found, just propagating)
- If not, remove node from stack (pop) and return false.

In code it looks something like below. In this problem it starts with 0 and tries to get to 23 by three different operations: +5, -3 and *2. It will restrict the possible actions when above 23 it will only allow the substraction and if below only the addition and multiplication. Notice, this does not find the *optimal* solution, only the first. It has a max_depth argument (set pretty low) that was because I made a small mistake and got a *huge* error message, so that limit can be lifted. I'm not sure if the cycle detection works correctly.

Mark

//-- DFS.java --//
package dfs;

import java.util.Stack;

public class DFS
{
    private Stack<DFSState> path;
    private DFSState start;
    private DFSState goal;

    //Construct a problem situation
    public DFS()
    {
        this.start = new DFSState(0);
        this.goal = new DFSState(23);

        this.path = new Stack<DFSState>();
    }

    //Solve problem instance
    public void solve()
    {
        if(this.dfs(this.start, 0))
        {
            System.out.println("Solved!");
            for(DFSState pstate : this.path)
                System.out.println(pstate);
        }
        else
        {
            System.out.println("Could not solve problem.");
        }
    }

    //Perform depth first search
    public boolean dfs(DFSState state, int maxDepth)
    {
        if(maxDepth == 10) return false;

        //Check for cycle
        for(DFSState pstate : this.path)
        {
            if(pstate.equals(state))
                return false;
        }

        //Add state to path
        this.path.push(state);

        //Is the current state the goal state?
        if(state.equals(goal))
            return true;

        //Recursive calling possible actions
        if(state.getValue() > goal.getValue())
        {
            if(this.dfs(new DFSState(state.getValue()-3), maxDepth+1))
                return true;
        }
        else
        {
            if(this.dfs(new DFSState(state.getValue()+5), maxDepth+1))
                return true;

            if(this.dfs(new DFSState(state.getValue()*2), maxDepth+1))
                return true;
        }

        //No solution found in this call
        this.path.pop();
        return false;
    }

    //Program entry
    public static void main(String[] args)
    {
        new DFS().solve();
    }
}

//-- DFState.java --//
package dfs;

class DFSState
{
    private int value;

    //Constructor
    public DFSState(int value)
    {
        this.value = value;
    }

    //Return value of this state
    public int getValue()
    {
        return this.value;
    }

    //Compare this state with another
    public boolean equals(DFSState state)
    {
        return this.getValue() == state.getValue();
    }

    //Return string representation of this state
    public String toString()
    {
        return "v="+this.value;
    }
}
0

Featured Post

[Webinar] How Hackers Steal Your Credentials

Do You Know How Hackers Steal Your Credentials? Join us and Skyport Systems to learn how hackers steal your credentials and why Active Directory must be secure to stop them. Thursday, July 13, 2017 10:00 A.M. PDT

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will show, step by step, how to integrate R code into a R Sweave document
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
This video teaches viewers about errors in exception handling.

630 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question