Использование алгоритма поиска в Python для решения головоломки 3 волков и 3 ягнят

Question

Я долго думал об этом вопросе и не мог понять, как его решить.

Проблема заключается в следующем:

У нас есть 3 ягнят и 3 волков в стороне, и мы должны позволить им пройти через реку на другую сторону. В начале это выглядело легко, пока я не остановился с этими трудными условиями:

• Волков не могут быть больше, чем у ягнят, что означает ягнята могут быть больше или равно волки.
• Лодка, несущая животных на другую сторону, не может нести более 2
• Лодка ДОЛЖНА всегда носить животных, а это значит, что вы не можете переместить пустую лодку.

вопрос должен быть решен по алгоритму поиска, как A * или BFS и т.д.

Мы все знаем, что эти алгоритмы не работают, пока вы не предоставите график в качестве входных данных, и здесь это проблема.

Как мы можем создать график из 3 ягнят и 3 волков?

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

Answer 1

Предположим, что у каждого узла есть состояние, представляющее, сколько ягнят и волков находится на левом берегу и находится ли лодка на этом берегу ('0' слева, '1' справа).

Исходный узел:

Node 0 : { lambs:3, wolves:3, boat:0 } 

Отсюда вы можете поехать в любой узел, который отвечает требованиям. Таким образом, новый узел должен иметь {boat:1} (он перешел на другую сторону), и он должен взять с собой 1 или 2 ягнят и 1 или двух волков.

Следующие возможные узлы:

Node 1 : { lambs:2, wolves:3, boat:1 } // boat took one lamb 
Node 2 : { lambs:1, wolves:3, boat:1 } // boat took two lambs 
Node 3 : { lambs:2, wolves:2, boat:1 } // boat took one lamb and one wolf 
Node 4 : { lambs:3, wolves:1, boat:1 } // boat took two wolves 
Node 5 : { lambs:3, wolves:2, boat:1 } // boat took one wolf 

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

Конечный узел:

Node N : { lambs:0, wolves:0, boat:1 } 

Ключ вынос в том, что вам нужен график между возможными состояниями не графа между сторонами реки или животных. И каждое государство должно захватывать все в «мировой» модели.

В псевдо C# код:

public class Node 
{ 
    public int LambsOnLeft {get; set;} 
    public int WolvesOnLeft {get; set;} 
    public int Boat {get; set;} 

    public IEnumerable<Node> NextStates() 
    { 
     if (Boat == 0) // on left 
     { 
       // boat takes one lamb from left to right 
      if (LamsOnLeft > 0 && LambsOnLeft-1 >= WolvesOnLeft)  
       yield return new Node(LambsOnLeft-1, WolvesOnLeft, 1); 
      } 
      if (LambsOnLeft > 1 && LambsOnLeft-2 >= WolvesOnLeft) 
       yield return new Node(LambsOnLeft-2, WolvesOnLeft, 1); 
      } 
      // take one wolf 
      if (WolvesOnLeft > 0) 
       yield return new Node(LambsOnLeft, WolvesOnLeft-1, 1); 
      // take two wolves 
      if (WolvesOnLeft > 1) 
       yield return new Node(LambsOnLeft, WolvesOnLeft-1, 1); 
      ... 
     } 
    } 
}