标签: river-crossing-puzzle

三个食人族和三个传教士必须过河.他们的船只能容纳两个人.如果食人族的数量超过传教士,在河的两边,传教士都遇到麻烦(我不会描述结果).每个传教士和每个食人族都可以划船.六个人怎么能过河？

我找不到使用IDDFS(迭代深化深度优先搜索)和GreedyBFS(贪婪最佳优先搜索)来解决此问题的算法.如何解决这个问题的想法也会让我感到高兴.

编辑:

我在wiki上找到了IDDFS的算法:

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
}

但我无法弄清楚DLS()中的扩展(节点)应该在我的问题中完成.这是我的Node类:

public class Node{
    //x-no of missionaries
    //y-no of cannibals
    //z-position of boat
    int x,y;
    boolean z;
    Node(int …

我正在开发一款名为"狼山羊白菜"的益智游戏.编程语言是Prolog.

change(e,w).
change(w,e).
move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]) :- change(X,Y).
move([X,Wolf,X,Cabbage],goat,[Y,Wolf,Y,Cabbage]) :- change(X,Y).
move([X,Wolf,Goat,X],cabbage,[Y,Wolf,Goat,Y]) :- change(X,Y).
move([X,Wolf,Goat,Cabbage],nothing,[Y,Wolf,Goat,Cabbage]) :- change(X,Y).

oneeq(X,X,WW).
oneeq(X,WWW,X).

safe([Man,Wolf,Goat,Cabbage]) :-
        oneeq(Man,Goat,Wolf),
        oneeq(Man,Goat,Cabbage).

wgc([e,e,e,e],[]).

wgc(Config,[FirstMove|OtherMoves]) :-
        move(Config,FirstMove,NextConfig),
        safe(NextConfig),
        wgc(NextConfig,OtherMoves).

为了使它工作,我打电话 length(X,7),wgc([w,w,w,w],X).,它显示结果.问题是它显示了很多次第一个结果,然后是第二个结果:

X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ;
X = [goat, nothing, wolf, goat, cabbage, nothing, goat] ; …

因此，尽管老师只讲了基础知识，但实际上这是Prolog中唯一的项目，所以我被分配去尝试在Prolog中解决此问题。我觉得我想得太过分了，而且他只是对首次Prolog程序抱有太多期望。

问题在下面列出，我该如何解决呢？

编写一个Prolog程序来解决下面的单词问题。作为解决方案的一部分，它应打印所有交叉点，并首先列出桨手。

汤姆，杰克，比尔和吉姆必须使用只能容纳两个人的独木舟穿越河流。
在从河的左到右岸的三个交叉口中，每个独木舟都有两个人，在从右到左的两个交叉口中的每个交叉口中，独木舟都有一个人。当其他人和他一起划独木舟时，汤姆无法划桨。
除了比尔和他一起在独木舟上时，杰克无法划桨。每个人都划着至少一个渡口。

到目前为止，这就是我所拥有的，尽管它“有效”，但并不能确保每个人至少划桨一次。

state(tom(Side),jim(Side),jack(Side),bill(Side),c(Side)).
initial(state(tom(l),jim(l),jack(l),bill(l),c(l))).
final(state(tom(r),jim(r),jack(r),bill(r),c(r))).

canoe(P):-P=p.
canoe(P,C):-P=p,C=c.

bad(state(tom(W),jim(X),jack(Y),bill(Z),c(C))):-
    C=l,(W=c;X=c;Y=c;Z=c).

move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z),c(C1))):-
    ((canoe(W1),W=r,W=C,C1=m);(canoe(W),W1=l,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1),X=r,X=C,C1=m);(canoe(X),X1=l,X1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z),c(C1))):-
    ((canoe(Y1),Y=r,Y=C,C1=m);(canoe(Y),Y1=l,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1),Z=r,Z=C,C1=m);(canoe(Z),Z1=l,Z1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1,W1),W=l,W=X,W=C,C1=m);
    (canoe(X,W),W1=r,W1=X1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,W1),W=l,W=Z,W=C,C1=m);
    (canoe(Z,W),W1=r,W1=Z1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y1),bill(Z),c(C1))):-
    ((canoe(X1,Y1),Y=l,Y=X,Y=C,C1=m);
    (canoe(X,Y),Y1=r,Y1=X1,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,X1);canoe(X1,Z1)),
     Z=l,Z=X,Z=C,C1=m);
    ((canoe(Z,X);canoe(X,Z)),Z1=r,Z1=X1,Z1=C1).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z1),c(C1))):-
    ((canoe(Y1,Z1);canoe(Z1,Y1)),
     Y=l,Y=Z,Y=C,C1=m);
    ((canoe(Y,Z);canoe(Z,Y)),Y1=r,Y1=Z1,Y1=C1).

find(Path):-initial(S),rez(S,Path).
bkt(State,Path,[Path|State]):-final(State).
bkt(State,Path,Sol):-move(State,Next),not(bad(Next)),
    not(member(Next,Path)),bkt(Next,[Path|Next],Sol).
rez(State,Sol):-bkt(State,[State],Sol).
start:-find(D),writef('%w\n',D).

我的工作解决了经典传教士(M)和食人族(C)的问题,一开始状态是3 M和左岸3 C和目标状态是3M,右岸3C.我已完成程序中的基本功能,我需要实现搜索策略,如BFS和DFS.

基本上我的代码是从互联网上学习的.到目前为止,我可以使用DFS方法成功运行程序,但我尝试使用BFS运行它总是返回false.这是我的第一个SWI-Prolog程序,我找不到我的代码问题在哪里.

这是我的代码的一部分,希望你能帮助我找到它的问题

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 …

我试图用clpfd解决'逃离Zurg'的问题.https://web.engr.oregonstate.edu/~erwig/papers/Zurg_JFP04.pdf 玩具从左侧开始向右侧移动.这就是我所拥有的:

:-use_module(library(clpfd)).

toy(buzz,5).
toy(woody,10).
toy(res,20).
toy(hamm,25).

%two toys cross, the time is the max of the two.
cross([A,B],Time):-
  toy(A,T1),
  toy(B,T2),
  dif(A,B),
  Time#=max(T1,T2).
%one toy crosses
cross(A,T):-
  toy(A,T).

%Two toys travel left to right
solve_L(Left,Right,[l_r(A,B,T)|Moves]):-
  select(A,Left,L1),
  select(B,L1,Left2),
  cross([A,B],T),
  solve_R(Left2,[A,B|Right],Moves).

%One toy has to return with the flash light
solve_R([],_,[]).
solve_R(Left,Right,[r_l(A,empty,T)|Moves]):-
  select(A,Right,Right1),
  cross(A,T),
  solve_L([A|Left],Right1,Moves).

solve(Moves,Time):-
   findall(Toy,toy(Toy,_),Toys),
   solve_L(Toys,_,Moves),
   all_times(Moves,Times),
   sum(Times,#=,Time).

all_times([],[]).
all_times(Moves,[Time|Times]):-
  Moves=[H|Tail],
  H=..[_,_,_,Time],
  all_times(Tail,Times).

查询?-solve(M,T)或?-solve(Moves,T), labeling([min(T)],[T]).我得到一个解决方案但不是一个= <60.(我也看不到一个..)我怎么用clpfd做这个？或者最好在链接中使用该方法？

仅供参考:我也找到了这个http://www.metalevel.at/zurg/zurg.html 哪个有DCG解决方案.在其中内置约束Time = <60,它没有找到最低时间.

首先,我很抱歉提出这个问题.但是"逃离Zurg"文章给了我很多帮助,我可以为Wolf Goat Cabbage问题编写自己的解决方案.我在下面提出我的代码.我要你告诉我

1. 如果我的代码是以真正的F#和函数式编程精神编写的

2. 这是解决问题的最佳方案

   open System
   
   (* 
     The type direction determines which direction the human is present.
     Left means that Human is present on the left side of the bank.
     Right means human is present on the right side of the bank.
   *)
   type Direction =
     | Left
     | Right
   
   (*
     Master list of animals
   *)
   let Animals = ["Wolf"; "Goat"; "Cabbage"]
   
   let DeadlyCombinations = [["Wolf"; "Goat"];["Goat"; "Cabbage"];]
   
   let isMoveDeadly list1 list2 =
     List.exists (fun n -> …

   Run Code Online (Sandbox Code Playgroud)