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

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

Я не могу найти алгоритм для решения этой проблемы, используя 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 ответа

Решение

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

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

Источник

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

Источник
Другие вопросы по тегам