Résoudre des Cannibales/Missionnaires à l'aide de largeur tout d'abord de recherche (BFS) en Prolog?

Je suis en train de travailler sur la résolution de la classique Missionnaires(M) et les Cannibales(C) problème, l'état de départ est de 3 M et 3 C sur la rive gauche et le but de l'état est de 3M, 3C, sur la rive droite. J'ai terminer la fonction de base dans mon programme et j'ai besoin de implemet la recherche-stratégie, tels que la BFS et DFS.

Fondamentalement, mon code est d'apprendre à partir de l'Internet. Jusqu'à présent, je peux réussi à exécuter le programme avec DFS méthode, mais j'essaie de le lancer avec BFS il retourne toujours false. C'est mon tout premier SWI-Prolog programme, je ne trouve pas où est le problème de mon code.

Voici la partie de mon code, j'espère que vous pourrez m'aider à trouver le problème de il

solve2 :-
   bfs([[[3,3,left]]],[0,0,right],[[3,3,left]],Solution),
   printSolution(Solution).

bfs([[[A,B,C]]],[A,B,C],_,[]).
bfs([[[A,B,C]|Visisted]|RestPaths],[D,E,F],Visisted,Moves) :-
   findall([[I,J,K],[A,B,C]|Visited]),
     (
       move([A,B,C],[I,J,K],Description),
       safe([I,J,K]),
       not(member([I,J,K],Visited)
     ),
     NewPaths
   ),
   append(RestPaths,NewPaths,CurrentPaths),
   bfs(CurrentPaths,[D,E,F],[[I,J,K]|Visisted],MoreMoves),
   Moves = [ [[A,B,C],[I,J,K],Description] | MoreMoves ].


move([A,B,left],[A1,B,right],'One missionary cross river') :-
   A > 0, A1 is A - 1.  
   % Go this state if left M > 0. New left M is M-1
.
.
.
.
.
safe([A,B,_]) :-
   (B =< A ; A = 0),
   A1 is 3-A, B1 is 3-B,
   (B1 =< A1; A1 =0).

- Je utiliser findall de trouver tous les chemins possibles avant d'aller au prochain niveau. Seul celui qui passe du coffre-fort() sera considérer comme possible l'état suivant. L'état de ne pas utiliser si elle existe déjà. Depuis mon programme peut s'exécuter avec DFS donc je pense qu'il n'y a rien de mal à se déplacer() et() de prédicat. Mon BFS prédicat est en train de changer la base sur mon DFS code, mais sa fonctionne pas.

findall/3 a arité 3, mais vous n'utiliser qu'un seul argument dans votre code. Vous pouvez également utiliser des variables Visisted et Visited. Sont-ils censés être de la même? Essayez l'indentation de ton code pour le rendre plus lisible, et ajouter quelques commentaires. Sinon, il est difficile de comprendre ce que vous essayez d'atteindre avec le findall/3 appel et le bloc suivant.

OriginalL'auteur Shawn Lien | 2012-03-30

  1. 5

    Il y a un moyen très simple de transformer une profondeur d'abord de programme de recherche en largeur d'abord, la profondeur d'abord de recherche est directement mappée à Prologue de recherche. Cette technique est appelée l'approfondissement itératif.

    Simplement ajouter un argument supplémentaire pour s'assurer que la recherche ne va pas N étapes de profondeur.
    Ainsi, un dfs-version:

    dfs(State) :-
   final(State).
dfs(State1) :-
   state_transition(State1, State2),
   dfs(State2).

    Est transformé en un bfs par l'ajout d'un argument en faveur de la profondeur. E. g. à l'aide de successeur-arithmétique:

    bfs(State, _) :-
   final(State).
bfs(State1, s(X)) :-
   state_transition(State1, State2),
   bfs(State2, X).

    Un objectif bfs(State,s(s(s(0)))) trouverez tous les calculs nécessitant 3 ou moins d'étapes. Vous pouvez toujours effectuer dfs! Utilisez simplement bfs(State,X).

    Pour trouver toutes les dérivations de l'utilisation natural_number(X), bfs(State,X).

    Il est souvent utile d'utiliser une liste au lieu de s(X)-nombre. Cette liste peut contenir tous les états intermédiaires ou aux transitions effectuées.

    Vous pourriez hésitez pas à utiliser cette technique, car il semble recalculer beaucoup d'états intermédiaires ("agrandis états"). Après tout, d'abord, il effectue des recherches sur tous les chemins d'accès avec une seule étape, puis, à plus de deux étapes, puis, au plus trois étapes... Cependant, si votre problème est un problème de recherche, le facteur de branchement ici caché à l'intérieur de state_transition/2 permettra d'atténuer les coûts indirects. Pour voir cela, considérons un facteur de branchement de 2: Nous allons avoir une surcharge d'un facteur de deux! Souvent, il ya des moyens faciles pour retrouver ce facteur de deux: E. g., en accélérant state_transition/2 ou final/1.

    Mais le plus grand avantage est qu'il ne consomme pas beaucoup d'espace - contrairement aux naïfs dfs.

    OriginalL'auteur false

  2. 2

    La Logtalk de distribution comprend un exemple, "recherche", qui met en œuvre un cadre pour l'espace d'état de la recherche:

    https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/searching

    Le "classique" les problèmes sont inclus (agriculteur, les missionnaires et les cannibales, puzzle 8, pont, une carafe d'eau, etc). Certains des algorithmes de recherche sont adaptés (avec permission) d'Ivan Bratko du livre "Prologue de la programmation de l'intelligence artificielle". L'exemple comprend également un moniteur de performance qui peut vous donner quelques notions de statistiques sur les performances d'une méthode de recherche (par exemple, la ramification des facteurs et le nombre de transitions de l'état). Le cadre est facile à étendre, à la fois pour les nouveaux problèmes et de nouvelles méthodes de recherche.

    Le lien est cassé.
    Merci. Le lien est maintenant résolu.

    OriginalL'auteur Paulo Moura

  3. 1

    Veuillez consulter ce résumé de voir une solution possible, peut-être utile à votre problème.

    Gist: résoudre les Missionnaires et les cannibales en Prolog

    OriginalL'auteur Juanito Fatas

  4. 1

    J'ai résolu avec la profondeur d'abord et ensuite avec en largeur d'abord, tenter de séparer clairement la partie réutilisable à partir de l'état de l'algorithme de recherche:

    miss_cann_dfs :-
    initial(I),
    solve_dfs(I, [I], Path),
    maplist(writeln, Path), nl.

solve_dfs(S, RPath, Path) :-
    final(S),
    reverse(RPath, Path).
solve_dfs(S, SoFar, Path) :-
    move(S, T),
    \+ memberchk(T, SoFar),
    solve_dfs(T, [T|SoFar], Path).

miss_cann_bfs :-
    initial(I),
    solve_bfs([[I]], Path),
    maplist(writeln, Path), nl.

solve_bfs(Paths, Path) :-
    extend(Paths, Extended),
    (   member(RPath, Extended),
        RPath = [H|_],
        final(H),
        reverse(RPath, Path)
    ;   solve_bfs(Extended, Path)
    ).

extend(Paths, Extended) :-
    findall([Q,H|R],
        (   member([H|R], Paths),
            move(H, Q),
            \+ member(Q, R)
        ), Extended),
    Extended \= [].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% problem representation
% independent from search method
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

initial((3,3, >, 0,0)).
final((0,0, <, 3,3)).

% apply a *valid* move
move((M1i,C1i, Bi, M2i,C2i), (M1f,C1f, Bf, M2f,C2f)) :-
    direction(Bi, F1, F2, Bf),
    who_move(MM, CM),
    M1f is M1i + MM * F1, M1f >= 0,
    C1f is C1i + CM * F1, C1f >= 0,
    ( M1f >= C1f ; M1f == 0 ),
    M2f is M2i + MM * F2, M2f >= 0,
    C2f is C2i + CM * F2, C2f >= 0,
    ( M2f >= C2f ; M2f == 0 ).

direction(>, -1, +1, <).
direction(<, +1, -1, >).

% valid placements on boat
who_move(M, C) :-
    M = 2, C = 0 ;
    M = 1, C = 0 ;
    M = 1, C = 1 ;
    M = 0, C = 2 ;
    M = 0, C = 1 .

    Je vous suggère de structurer votre code de manière similaire, avec un prédicat similaire à étendre/2, qui précise l'arrêt de la recherche.

    Un cadre pour l'espace d'état à la recherche, comme par exemple mis en œuvre dans le Logtalk "recherche" exemple que je cite ci-dessus, vous permet d'utiliser n'importe quelle combinaison de l'espace d'état et de la méthode de recherche.
    Moura: ce cadre, il est assez complexe système, comment pourrait aider Shawn Privilège? Je vois que breadth_first1 contient un complexe développer/expandall, mutuellement récursives (à première vue), et je ne suis pas en mesure de déterminer, simplement pour dire, si elle met en œuvre la résiliation. Qui me font penser à mon selfmade solve_bfs, si simple, et apparemment en général, peut-être erroné. Je viens de tester en comparant avec dfs...
    Certains des algorithmes de recherche, y compris la largeur de la première, sont adapté, avec permission, de la Ivan Bratko du livre "Prologue de la Programmation de l'Intelligence Artificielle". Le livre explique les algorithmes en détail. Notez que vous pouvez facilement votre propre version de l'ampleur premier algorithme pour le cadre et test avec les exemples fournis.

    OriginalL'auteur CapelliC

  5. 0

    Si votre système Prolog a un avant programme de chaînage vous pouvez également résoudre
    le problème de la modélisation par chaînage avant les règles. Ici
    est un exemple de la façon de résoudre une cruche d'eau problème dans Jekejeke Minlog.
    L'état est représenté par un prédicat d'état/2.

    Vous donner d'abord une règle qui filtre les doublons comme suit. L'
    la règle dit que l'arrivée d'un état/2 devrait être supprimé,
    si elle est déjà à l'avant de la boutique:

    % avoid duplicate state
unit &:- &- state(X,Y) && state(X,Y), !.

    Puis vous donner des règles que l'état de la recherche ne doivent pas être poursuivi
    lorsque l'état final est atteint. Dans le présent exemple, nous vérifions
    que l'un des navires contient 1 litre d'eau:

    % halt for final states
unit &:- state(_,1), !.
unit &:- state(1,_), !.

    Dans une prochaine étape, l'un des modèles les transitions d'état comme le chaînage avant
    des règles. C'est simple. Nous le modèle de la vidange, le remplissage et le coulage
    des navires:

    % emptying a vessel
state(0,X) &:- state(_,X).
state(X,0) &:- state(X,_).

% filling a vessel
state(5,X) &:- state(_,X).
state(X,7) &:- state(X,_).

% pouring water from one vessel to the other vessel
state(Z,T) &:- state(X,Y), Z is min(5,X+Y), T is max(0,X+Y-5).
state(T,Z) &:- state(X,Y), Z is min(7,X+Y), T is max(0,X+Y-7).

    Nous pouvons maintenant utiliser le chaînage avant moteur pour faire le travail pour nous. Il
    ne itérative deeping et il ne sera également pas faire de largeur.
    Il vient de faire l'unité de la résolution par une stratégie qui est avide pour la
    fait et le processus ne se termine, depuis l'espace d'état
    est finie. Voici le résultat:

    ?- post(state(0,0)), posted.
state(0, 0).
state(5, 0).
state(5, 7).
state(0, 7).
Etc..

    L'approche vous permet de savoir si il existe une solution, mais pas à expliquer
    la solution. Une approche pour rendre explicable est d'utiliser un fait
    etat/4 au lieu d'un état de fait/2. Les deux derniers arguments sont utilisés pour
    une liste des actions et de la longueur de la liste.

    La règle qui évite les doublons est ensuite changée pour une règle qui choisit
    la plus petite solution. Il se lit comme suit:

    % choose shorter path
unit &:- &- state(X,Y,_,N) && state(X,Y,_,M), M<N, !.
unit &:- state(X,Y,_,N) && &- state(X,Y,_,M), N<M.

    On obtient alors:

    ?- post(state(0,0,[],0)), posted.
state(0, 0, [], 0).
state(5, 0, [fl], 1).
state(5, 7, [fr,fl], 2).
state(0, 5, [plr,fl], 2).
Etc..

    Avec une petite aide de prédicat, nous pouvons forcer une explication de
    les actions qui mènent à un chemin:

    ?- post(state(0,0,[],0)), state(1,7,L,_), explain(L).
0-0
fill left vessel
5-0
pour left vessel into right vessel
0-5
fill left vessel
5-5
pour left vessel into right vessel
3-7
empty right vessel
3-0
pour left vessel into right vessel
0-3
fill left vessel
5-3
pour left vessel into right vessel
1-7

    Bye

    Code Source: Pot À Eau En État

    http://www.xlog.ch/jekejeke/forward/jugs3.p

    Code Source: pot à Eau en État et le Chemin d'accès

    http://www.xlog.ch/jekejeke/forward/jugs3path.p

    OriginalL'auteur j4n bur53