Farmer, Wolf, Goat and Cabbage Breadth-first and Depth-first Search in Java

Question

So, I started this problem where I have to bring a cabbage, wolf, and goat across the river without leaving the cabbage with the goat or the wolf and goat by themselves on the same side.

I started and got sorely confused about how to approach this. Basically I was thinking of adding a bunch of vertexes that would lead to the correct outcome, and just have the program demonstrate breadth-first and depth-first searching without having a complex vertices generation process. Am I thinking about this correctly, or is there a better approach?

Here is my code for the main method so far.

package project3;

import java.util.*;
import java.io.*;


public class Project3 extends Network{

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    new Project3().run();
} //main method

public void run()
{
    String start ="fwgcR",
           finish = "Rfwgc";

    addVertex(start);
    addVertex("fwgRc");
    addVertex("fwcRg");
    addVertex(finish);


    //Breadth First iterator
    Iterator<String> itr = network.breadthFirstIterator (start);
        while (itr.hasNext())
            System.out.print (itr.next() + " ");

    //Depth First Iterator    
    itr = network.depthFirstIterator (start);
        while (itr.hasNext())
            System.out.print (itr.next() + " ");


    } // method run  
}

This really isn't a Java question, it's a question of figuring out an algorithm. I've added some tags. — ajb, Mar 11 '14 at 21:04

score 3 · Answer 1 · answered Mar 11 '14 at 21:07

The usual approach for problem-solving search is to develop a state space representation. You seem to want to explicitly represent all the states and transitions in a graph, but the more common approach is to design a state representation and then a process that will generate the successor states from a given state. The search process then relies on the successor state generator to expand a current state and carry out the search.

I strongly recommend using a state generating function rather than building a complete state graph from the start.

In your case, the state representation might be as simple as the current side of the river for each object (farmer, wolf, goat, and cabbage). The successor states for a given state are the farmer and possibly one of the objects currently on the same side as the farmer switching sides. You would probably want to filter out inadmissible states as part of the successor generation function. I don't recommend a string to represent the states, although it could work. An array of four booleans (each representing, say, "right side of the river") would be easier to work with.

score 1 · Answer 2 · edited Mar 24 '18 at 12:15

I don't know why you want to use both breadth-first and depth-first search, but yes, either of those can be used to find the correct order of steps to a solution.

Using strings to represent the nodes in your graph is a bad idea. It will be much more trouble than necessary to generate the outgoing vertices from each node, and to avoid adding redundant nodes.

The next thing you need to do is define a class to represent each node on the graph, and write a function to find adjacent nodes, filtering out any nodes with the goat and cabbage or goat and wolf on the same side of the river and alone.

Farmer, Wolf, Goat and Cabbage Breadth-first and Depth-first Search in Java

2 Answers2