java - Java 中的农夫、狼、山羊和卷心菜广度优先和深度优先搜索

Question

所以，我开始了这个问题，我必须带着白菜、狼和山羊过河，不能让白菜和山羊在一起，也不能让狼和山羊单独在同一边。

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

这是我目前主要方法的代码。

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

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

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

在您的情况下，状态表示可能与每个对象(农夫、狼、山羊和卷心菜)的当前河边一样简单。给定状态的后继状态是农场主，并且可能是当前与农场主切换方位于同一侧的对象之一。作为后继生成函数的一部分，您可能希望过滤掉不允许的状态。我不推荐使用字符串来表示状态，尽管它可以工作。四个 boolean 值组成的数组(每个都代表“河流的右侧”)会更容易处理。