3

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

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

到目前为止，这是我的主要方法的代码。

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  
}
4

2 回答 2

3

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

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

在您的情况下，状态表示可能与每个对象（农夫、狼、山羊和卷心菜）的当前河流一侧一样简单。给定状态的后继状态是农夫，并且可能是当前与农夫切换边在同一侧的对象之一。作为后继生成功能的一部分，您可能希望过滤掉不可接受的状态。我不推荐使用字符串来表示状态，尽管它可以工作。一个由四个布尔值组成的数组（每个布尔值代表，比如说，“河流的右侧”）会更容易使用。

于 2014-03-11T21:07:04.623 回答
1

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

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

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

于 2014-03-11T21:07:10.047 回答