Solved

DFS ALGORITHM

Posted on 2007-03-26
4
2,341 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
4 Comments
 
LVL 30

Expert Comment

by:Mayank S
ID: 18797135
0
 

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

3 Use Cases for Connected Systems

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, testing some more, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Powershell Script need assistance to make some changes 4 82
servlet example issue 6 40
hibernate example using maven 12 42
Tomcat: Unable to run tomcat service. 2 20
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Navigation is an important part of web design from a usability perspective. But it is often a pain when it comes to a developer’s perspective. By navigation, it often means menuing. This is less theory and more practical of how to get a specific gro…
The viewer will learn how to implement Singleton Design Pattern in Java.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

831 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