Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

DFS ALGORITHM

Posted on 2007-03-26
4
Medium Priority
?
2,352 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 1500 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

New benefit for Premium Members - Upgrade now!

Ready to get started with anonymous questions today? It's easy! Learn more.

Question has a verified solution.

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

Windows Script Host (WSH) has been part of Windows since Windows NT4. Windows Script Host provides architecture for building dynamic scripts that consist of a core object model, scripting hosts, and scripting engines. The key components of Window…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
The viewer will learn how to implement Singleton Design Pattern in Java.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
Suggested Courses

715 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