Kannibalen und Missionare mit IDDFS und GreedyBFS

Question

Drei Kannibalen und drei Missionare müssen einen Fluss überqueren. Ihr Boot kann nur zwei Personen halten. Wenn die Kannibalen den Missionaren auf beiden Seiten des Flusses zahlenmäßig überlegen sind, sind die Missionare in Schwierigkeiten (ich werde die Ergebnisse nicht beschreiben). Jeder Missionar und jeder Kannibale kann das Boot rudern. Wie können alle sechs über den Fluss kommen?

Ich kann keinen Algorithmus finden, um dieses Problem mit IDDFS (Iterative Vertiefung Tiefensuche zuerst) und GreedyBFS (gierige Best-First-Suche) zu lösen. Eine Idee, wie ich das lösen könnte, würde mich auch glücklich machen.

Edited:

ich einen Algorithmus für IDDFS auf dem Wiki gefunden:

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 
} 

Aber ich kann nicht herausfinden, was soll in DLS (Knoten) expand() zu erreichen, meine Problem. Das ist meine Klasse 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; 
    } 

} 

ich Hilfe schätzen würde.

Answer 1

Wie löst man es ohne Algorithmus? dein Modell ist klein und es kann ohne Programmierung gelöst werden, zuerst zwei Kannibalen gehen auf die andere Seite, dann einer von ihnen mit Boot zurück und nimmt einen anderen Kannibalen auf die andere Seite, jetzt gibt es 3 Kannibalen auf der anderen Seite einer von ihnen Rücken und zwei Missionare gehen auf die andere Seite (jetzt 2 c und 2 m sind auf der anderen Seite). in dieser Zeit kommt ein c mit einem m zurück (2 c und 2 m an erster Stelle), und nochmals 2 m zur anderen Seite (3m auf der anderen Seite mit einem c), wieder kommt nur das c auf der anderen Seite zurück und trägt zwei c auf der anderen Seite (2 c und 3 m auf der anderen Seite), wieder ein c kommt zurück und bewegt sich spät c auf die andere Seite.

Wie simuliert man es mit Algorithmen wie DFS? Erstellen Sie einen Digraph, es gibt 2^6 Positionen (alle möglichen Teilmengen von {1,2,3,4,5,6}), sie sind miteinander verwandt, wenn Sie mit verfügbaren Bewegungen von einer Position zur nächsten wechseln können . Einige Knoten sind tote Knoten (Knoten, die mehr Kannibalen auf einer Seite verursachen), Sie entfernen diese Knoten aus Ihrem Graph, dann ist es Ihre Aufgabe zu überprüfen, ob es eine Möglichkeit gibt, von Knoten 0 {} zu Knoten 63 {1,2 zu gelangen , 3,4,5,6}, die auf zu viele Arten wie BFS, DFS gelöst werden können.

Answer 2

Um die von Ihnen erwähnten Algorithmen zu verwenden, müssen Sie herausfinden, was der -Statusbereich des Problems ist. A Zustand ist eine vollständige Beschreibung einer Situation in dem Problem (sei es die Ausgangssituation, die endgültige Situation oder eine Zwischensituation). Der Trick besteht darin, gerade genug Informationen in einen Zustand einzubeziehen, um feststellen zu können, ob der Zustand eine Lösung des Problems ist, und wenn nicht, was als nächstes zu tun ist. In Ihrem Fall ist eine Möglichkeit, den Zustand darzustellen, die Verwendung von drei Variablen: die ganze Zahl m sagt aus, wie viele Missionare auf der Start Seite des Flusses sind, die ganze Zahl c sagt, wie viele Kannibalen auf der Startseite sind, und die boolesche b sagt, auf welcher Seite das Boot ist. Mit den gegebenen Werten für (m, c, b) können Sie bestimmen, welche möglichen Aktionen Sie ausführen können und in welche anderen Zustände Sie gelangen. Die Algorithmen, die Sie erwähnen, sind wirklich Algorithmen zum Durchsuchen einer solchen Menge verbundener Zustände.