农民，狼，山羊和卷心菜在Java中的广度优先和深度优先搜索

Question

所以，我开始了这个问题，我必须带着卷心菜，狼和山羊过河，而不是把卷心菜和山羊放在一起，或者狼和山羊在同一侧。

我开始并对如何处理这个问题感到非常困惑。基本上，我在考虑添加一堆会导致正确结果的顶点，并让程序演示宽度优先和深度优先搜索，而不需要复杂的顶点生成过程。我的想法是正确的吗，还是有更好的方法?

这是目前为止main方法的代码。

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  
}

Answer 1

通常的解决问题的搜索方法是开发一个状态空间表示。您似乎想要显式地在图中表示所有状态和转换，但更常见的方法是设计一个状态表示，然后设计一个从给定状态生成后续状态的过程。然后，搜索过程依靠后继状态生成器展开当前状态并执行搜索。

我强烈建议使用状态生成函数而不是从一开始就构建一个完整的状态图。

在您的例子中，状态表示可能与每个对象(农民、狼、山羊和卷心菜)的当前河岸一样简单。给定状态的继承状态是农民，也可能是当前与农民处于同一侧的对象之一。您可能希望过滤掉不可接受的状态，作为后继生成函数的一部分。我不推荐用字符串来表示状态，尽管它可以工作。一个包含四个布尔值的数组(每个表示，例如，"河的右边")会更容易处理。

Answer 2

我不知道你为什么要同时使用宽度优先和深度优先搜索，但是，是的，它们中的任何一个都可以用来找到解决方案的正确步骤顺序。

使用字符串来表示图中的节点是一个坏主意。从每个节点生成外向顶点，并避免添加冗余节点，这将比必要的麻烦得多。

接下来需要做的是定义一个类来表示图上的每个节点，并编写一个函数来查找相邻节点，过滤掉在河的同一侧且单独存在的山羊和卷心菜或山羊和狼的任何节点。