Solved

DFS ALGORITHM

Posted on 2007-03-26
4
2,336 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
groupNoAdj 7 87
Non-recursive backtracking, using a stack 1 103
Capture logon name 13 48
servlet filter example 37 46
This article will show, step by step, how to integrate R code into a R Sweave document
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

864 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

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now