Cannibali e missionari che usano IDDFS e GreedyBFS

Question

Tre cannibali e tre missionari devono attraversare un fiume. La loro barca può contenere solo due persone. Se i cannibali sono più numerosi dei missionari, ai lati del fiume, i missionari sono nei guai (non descriverò i risultati). Ogni missionario e ogni cannibale possono remare sulla barca. Come possono attraversare il fiume tutti e sei?

Non riesco a trovare un algoritmo per risolvere questo problema utilizzando IDDFS (Iterative deepening depth-first search) e GreedyBFS (greedy best-first search). Un'idea su come risolvere questo mi renderebbe felice.

Modificato:

ho trovato un algoritmo per IDDFS sul wiki:

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 
} 

Ma io non riesco a capire cosa espandere (nodo) nel DLS() dovrebbe realizzare nel mio problema. Questa è la mia classe 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; 
    } 

} 

Gradirei qualsiasi aiuto.

Answer 1

Come risolverlo senza algoritmo? il tuo modello è piccolo e può essere risolto senza alcuna programmazione, i primi due cannibali vanno dall'altra parte, poi uno di loro torna con la barca e prende un altro cannibale dall'altro lato, ora ci sono 3 cannibali sull'altro lato uno di loro dorsi e due missionari che vanno dall'altra parte (ora 2 e 2 m sono nell'altro lato). in questo momento uno c torna con uno m (2c e 2m al primo posto), e di nuovo 2 m andando dall'altro lato (3m nell'altro lato con uno c), di nuovo l'unica c nell'altro lato ritorna e porta due c sull'altro lato (2 e 3 m nell'altro lato), ancora una volta c torna e sposta l'ultima c verso l'altro lato.

Come simularlo con algoritmi come DFS? Crea un digraph, ci sono 2^6 posizioni (tutti i possibili sottoinsiemi di {1,2,3,4,5,6}), sono correlati tra loro se puoi passare da una posizione all'altra usando le mosse disponibili . alcuni nodi sono nodi morti (nodi che causano più cannibali su un lato), rimuoverai questi nodi dal tuo grafico, quindi il tuo compito è controllare c'è un modo per passare dal nodo 0 {} al nodo 63 {1,2 , 3,4,5,6}, che può essere risolta in troppi modi come BFS, DFS.

Answer 2

Per utilizzare gli algoritmi citati, è necessario capire quale sia lo spazio dello spazio del problema. A stato è una descrizione completa di una situazione nel problema (che si tratti della situazione di partenza, della situazione finale o di una situazione intermedia). Il trucco è includere solo le informazioni sufficienti in uno stato per essere in grado di determinare se lo stato è una soluzione del problema e, in caso contrario, cosa fare dopo. Nel tuo caso, un possibile modo di rappresentare lo stato consiste nell'utilizzare tre variabili: il numero intero m indica quanti missionari sono sul lato iniziale del fiume, il numero intero c indica quanti cannoni sono sul lato di partenza, e la booleana b indica da che parte si trova la barca. Dati i valori per (m, c, b), è possibile determinare quali azioni è possibile intraprendere e quali altri stati vi porteranno. Gli algoritmi che menzioni sono in realtà algoritmi per la ricerca attraverso un insieme di stati collegati.