Solved

DFS ALGORITHM

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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
difference of if loops 23 60
javap not working 8 58
web application structure 18 96
collection output issue 9 36
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…
This article will show, step by step, how to integrate R code into a R Sweave document
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

808 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