Фермер, волк, коза и капуста Поиск в ширину и в глубину в Java

Итак, я начал эту задачу, где я должен перевезти капусту, волка и козу через реку, не оставляя капусту с козой или волка и козу поодиночке на одной стороне.

Я начал и сильно запутался в том, как подойти к этому. По сути, я думал добавить кучу вершин, которые приведут к правильному результату, и просто заставить программу демонстрировать поиск в ширину и в глубину без сложного процесса генерации вершин. Правильно ли я думаю об этом, или есть лучший подход?

Вот мой код для основного метода.

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  
}

java algorithm breadth-first-search depth-first-search river-crossing-puzzle
person iamgod    schedule 11.03.2014    source источник
comment
Это действительно не вопрос Java, это вопрос выяснения алгоритма. Я добавил несколько тегов.   -  person ajb    schedule 12.03.2014
comment
Извините за это, спасибо!   -  person iamgod    schedule 12.03.2014

Ответы (2)


arrow_upward
3
arrow_downward

Обычный подход к поиску решения проблем заключается в разработке представления в пространстве состояний. Кажется, вы хотите явно представить все состояния и переходы в графе, но более распространенный подход заключается в разработке представления состояния, а затем процесса, который будет генерировать последующие состояния из заданного состояния. Затем процесс поиска полагается на генератор состояний-преемников для расширения текущего состояния и выполнения поиска.

Я настоятельно рекомендую использовать функцию генерации состояний, а не строить полный граф состояний с самого начала.

В вашем случае представление состояния может быть таким же простым, как текущая сторона реки для каждого объекта (фермер, волк, коза и капуста). Состояния-преемники для данного состояния — это фермер и, возможно, один из объектов, находящихся в настоящее время на той же стороне, что и фермер, переходящий на другую сторону. Вы, вероятно, захотите отфильтровать недопустимые состояния как часть функции генерации преемника. Я не рекомендую строку для представления состояний, хотя это может сработать. С массивом из четырех логических значений (каждое из которых представляет, скажем, «правый берег реки») было бы легче работать.

person Ted Hopp    schedule 11.03.2014

arrow_upward
1
arrow_downward

Я не знаю, почему вы хотите использовать как поиск в ширину , так и поиск в глубину, но да, любой из них можно использовать для поиска правильного порядка шагов к решению.

Использование строк для представления узлов на вашем графике — плохая идея. Будет гораздо больше проблем, чем необходимо, чтобы сгенерировать исходящие вершины из каждого узла и избежать добавления избыточных узлов.

Следующее, что вам нужно сделать, это определить класс для представления каждого узла на графе и написать функцию для поиска соседних узлов, отфильтровывая любые узлы с козой и капустой или козой и волком на на той же стороне реки и в одиночестве.

person Alex D    schedule 11.03.2014