Каннибалы и миссионеры, использующие IDDFS и GreedyBFS - PullRequest
Новая
       35

Каннибалы и миссионеры, использующие IDDFS и GreedyBFS

5 голосов
/ 24 марта 2012

Три каннибала и три миссионера должны пересечь реку.Их лодка может вместить только двух человек.Если людоеды численно превосходят миссионеров по обе стороны реки, у миссионеров проблемы (я не буду описывать результаты).Каждый миссионер и каждый каннибал могут грести на лодке.Как все шесть могут пересечь реку?

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

Отредактировано:

Я нашел алгоритм для IDDFS на вики: 

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}


DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth > 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return no-solution
}

Но я не могу понять, что такое расширение (узел) в DLS () должно решить в моей проблеме.Это мой класс Node: 

public class Node{
    //x-no of missionaries
    //y-no of cannibals
    //z-position of boat
    int x,y;
    boolean z;
    Node(int x,int y,boolean z){
        this.x=x;
        this.y=y;
        this.z=z;
    }
    public int getM(){
        return this.x;
    }
    public int getC(){
        return this.y;
    }
    public boolean getB(){
        return this.z;
    }
    public void setM(int x){
        this.x=x;
    }
    public void setC(int y){
        this.y=y;
    }
    public void setB(boolean z){
        this.z=z;
    }

}

Буду признателен за любую помощь.

Ответы [ 2 ]

4 голосов
/ 24 марта 2012

Чтобы использовать упомянутые вами алгоритмы, вам необходимо выяснить, в чем состоит пространство состояний проблемы.Состояние - это полное описание ситуации в проблеме (будь то начальная ситуация, конечная ситуация или промежуточная ситуация).Хитрость заключается в том, чтобы включить в состояние достаточно информации, чтобы определить, является ли состояние решением проблемы, и, если нет, что делать дальше.В вашем случае одним из возможных способов представления состояния является использование трех переменных: целое число m указывает, сколько миссионеров находится на начальной стороне реки, целое число c говорит о том, какмногие каннибалы находятся на стартовой стороне, а логическое значение b указывает, на какой стороне находится лодка.Учитывая значения для (m, c, b) , вы можете определить, какие возможные действия вы можете предпринять, и в каких других состояниях это вас приведет.Алгоритмы, которые вы упоминаете, на самом деле являются алгоритмами для поиска в таком наборе связанных состояний.

4 голосов
/ 24 марта 2012

Как решить это без алгоритма? Ваша модель маленькая, и ее можно решить без какого-либо программирования: сначала два людоеда переходят на другую сторону, затем один из них возвращается на лодке и доставляет другого людоеда к с другой стороны, теперь есть 3 людоеда на другой стороне, один из которых отступает, и два миссионера идут на другую сторону (теперь 2 с и два м находятся на другой стороне). в это время возвращается один c с одним m (2 с и 2 м на первом месте), и снова 2 м с другой стороны (3 м с другой стороны с одним с), снова единственный с в другая сторона возвращается и несет два c на другой стороне (2 c и 3 м на другой стороне), снова один c возвращается и перемещает последний c на другую сторону.

Как смоделировать это с помощью алгоритмов, таких как DFS? Создать орграф, есть 2 ^ 6 позиций (все возможные подмножества {1,2,3,4,5,6}), они связаны друг с другом, если вы можете перейти из одной позиции в другую, используя доступные ходы. некоторые узлы - это мертвые узлы (узлы, которые вызывают больше людоедства на одной стороне), вы удалите эти узлы из своего графа, а затем ваша задача проверить, есть ли способ перейти от узла 0 {} к узлу 63 {1,2 , 3,4,5,6}, что может быть решено слишком многими способами, такими как BFS, DFS.

...