Suchalgorithmus in Python verwenden, um die 3 Wölfe und 3 Lämmer zu lösen

Question

Ich habe lange über diese Frage nachgedacht und konnte nicht herausfinden, wie ich sie lösen kann.

Das Problem ist, wie folgend:

Wir haben 3 Lämmer und drei Wölfe in einer Seite und wir müssen sie den Fluss auf die andere Seite passieren lassen. Am Anfang sah es einfach, bis ich mit diesen schwierigen Umständen gestoppt:

• Die Wölfe nicht mehr als die Lämmer sein können, die die Lämmer bedeuten mehr sein können als oder gleich die Wölfe.
• Das Boot, das die Tiere auf die andere Seite trägt, kann nicht mehr als 2
• Das Boot muss immer mit Tieren, was bedeutet, dass Sie ein leeres Boot nicht bewegen können.

Die Frage muss vom Suchalgorithmus gelöst werden, wie A * oder BFS usw.

Wir alle wissen, dass diese Algorithmen nicht funktionieren, bis Sie ein Diagramm als eine Eingabe zur Verfügung stellen, und hier ist das Problem.

Wie können wir eine Grafik von 3 Lämmern und 3 Wölfen erstellen?

Ich habe viele Male darüber nachgedacht, und der einzige Weg kam mir durch all die Möglichkeiten. Klingt gut für mich, aber macht mir immer noch keine Fortschritte, weil das Problem immer noch das gleiche ist, wie man es implementiert oder es als Python-Code schreibt, um dieses Diagramm an den Algorithmus zu übergeben, damit der Algorithmus es lösen kann?

Answer 1

Angenommen, jeder Knoten hat einen Status, der angibt, wie viele Lämmer und Wölfe sich auf der linken Bank befinden und ob sich das Boot auf dieser Bank befindet ('0' für links, '1' für rechts).

Der erste Knoten ist:

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

von dort aus zu einem beliebigen Knoten fahren kann, die den Anforderungen entsprechen. Also muss der neue Knoten {boat:1} haben (er ging auf die andere Seite) und er muss 1 oder 2 Lämmer und ein oder zwei Wölfe damit aufnehmen.

Die nächsten möglichen Knoten sind:

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 

Und so weiter. Sie können diese dynamisch generieren, während Sie die Baumstruktur möglicher Bewegungen erkunden. Und wie Erick in den Kommentaren hervorhebt, sind einige davon laut den Regeln nicht legal und hätten nicht in der Grafik sein sollen. Das überlasse ich dir, um es herauszufinden.

Der Endknoten ist:

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

Der Schlüssel zum Mitnehmen ist, dass Sie eine Grafik zwischen möglichen Zuständen kein Graph zwischen den Seiten des Flusses oder die Tiere brauchen. Und jeder Staat muss alles im "Welt" -Modell erfassen.

In pseudo C# Code:

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); 
      ... 
     } 
    } 
}