[_], ... .?- length(X,N), path( state(on(c,on(b,on(a,void))), void, void), state(void, void, on(c,on(a,on(b,void)))), X), phrase((...,[E],...,[E],...), X). X = ... N = 6, E = state(void,on(c,void),on(a,on(b,void))); ...

问题描述 投票：0回答：1
Oh yes, there are! Now it does make sense to rule out such paths. Here is a clean way:

alldifferent([]).alldifferent([X

move(state(on(X, NewX), OldY, Z), state(NewX, on(X, OldY), Z)).
move(state(on(X, NewX), Y, OldZ), state(NewX, Y, on(X, OldZ))).

move(state(OldX, on(Y, NewY), Z), state(on(Y, OldX), NewY, Z)).
move(state(X, on(Y, NewY), OldZ), state(X, NewY, on(Y, OldZ))).

move(state(OldX, Y, on(Z, NewZ)), state(on(Z, OldX), Y, NewZ)).
move(state(X, OldY, on(Z, NewZ)), state(X, on(Z, OldY), NewZ)).

path(X,X,[]).
path(X,Y,[Z|ZS]) :- 
    move(X,Z),
    path(Z,Y,ZS).

move我有以下代码。path其中

给我们提供可能的动作，你可以使用，并。path 应该给出你从X到Y的路径。path(state(on(c,on(b,on(a,void))), void, void), state(void, void, on(c,on(a,on(b,void)))), X).问题是，谓词 

X=[state(void, void, on(c,on(a,on(b,void)))),
state(void, on(c,void), on(void(a,on(b,void))),
state(on(a,void), on(c,void), on(b,void)),
state(on(b,on(a,void)), on(c,void), void),
state(on(c,on(b,on(a,void))), void, void)].

不能如我所愿，也就是说，如果我输入了

我得到了ERROR。Out of local stack,but I want that that X would be
prolog
1个回答
3
投票

我的代码如下： move(state(on(X，NewX)，OldY，Z)，state(NewX，on(X，OldY)，Z)).move(state(on(X，NewX)，Y，OldZ)，state(NewX，Y，on(X，OldZ))).move(state(OldX，on(Y，NewY)，Z)，state(on(......))。对于第一次测试，没有必要重写你的代码。自1972年夏天以来，没有

1

. 相反，你可以节约地重新表述你的查询。与其要求一个具体的答案，这需要你的Prolog系统相当多的聪明才智，不如让我们把你的答案表述为一个查询！我试了一下，发现你在其中有一些讨厌的语法错误，之后，查询失败了。我试了一下，发现你有一些讨厌的语法错误，之后，查询失败了。但还有一个更便宜的方法! 让我们限制一下列表的长度，然后... 剩下的就让Prolog来完成吧. 这份名单有多长？我们不知道（也就是说，我不知道）。好吧，让我们试试 

?- length(X,N),  % new
   path(  state(on(c,on(b,on(a,void))), void, void),
          state(void, void, on(c,on(a,on(b,void)))),
          X).
   X = [ state(on(b,on(a,void)),on(c,void),void),
         state(on(a,void),on(c,void),on(b,void)),
         state(void,on(c,void),on(a,on(b,void))),
         state(void,void,on(c,on(a,on(b,void)))) ],
   N = 4
;  ...

任何长度length(X, N)! 同时这也是Prolog喜欢的东西。它就像..:看我做了什么? 我只添加了 在前面。而突然间普罗格回答了一声

较短

 答案比你预期的还要好!

现在，这真的是最好的问法吗？毕竟，很多答案可能都是简单的循环，把一个积木放到一个地方再放回去...... 真的有循环吗？我们先来问问这个问题。

... --> [] conceiveddelivered.

哦......一个积木世界的问题!

这只是因为你做了两件事。X先在状态空间中进行深度搜索未能测试是否已经访问过某个状态。(另外，你给出的解决方案不是一个可到达的状态，第二行有一个 length/2 在一个错误的位置上，加上路径是反向的）。)

事实上，你通过状态路径来构建路径 path/4只回

在这里的第三个论点。

. 你
2
投票

来检查每次状态扩展时是否有新的状态已经在路径上。否则，程序可能会永远循环下去（这取决于它是如何打到

移动生成谓词......其实是一个不错的练习选择一个

  • 概率地......也许以后会）。) 在下面的代码中，检查是通过以下方式完成的
  • .

此外，根据上述的深度优先搜索。void会

找到解决途径，但很可能 不 是一条捷径，而不是寻求的解决方案。path(X,Y,[Z|ZS])你真的需要广度优先搜索（或者说。

迭代深化). 由于Prolog不允许更换搜索算法(为什么不允许?已经40多年了)，你必须自己推出一个。观察一下。move/2最后我们得到的结果是：move/2一条长度为23的路径成功地到达了最终状态 但根据所寻求的解决方案，它 "太长了" 即使用启发式的 "不要移动一个块两次 "来表示 fail_if_visited/2.

补遗。概率搜索使用 随机算法 是惊人的收获。撕开...

谓词，并将其替换为:显然，这不是高效的Prolog模式，但谁在乎呢？只用了7次就找到了长度为5的解！

% ===
% Transform a state into a string
% ===

express(state(A,B,C),S) :- 
   express_pos(A,SA),
   express_pos(B,SB),
   express_pos(C,SC),
   atomic_list_concat(["[",SA,",",SB,",",SC,"]"],S).

express_pos(on(Top,Rest),S) :- 
   express_pos(Rest,S2), 
   atomic_list_concat([Top,S2],S).

express_pos(void,""). 

% ===
% Transform a path into a string
% (The path is given in the reverse order; no matter)
% ===

express_path(Path,PathStr) :-
   express_path_states(Path,StateStrs),
   atomic_list_concat(StateStrs,"<-",PathStr).

express_path_states([S|Ss],[StateStr|SubStateStrs]) :-   
   express_path_states(Ss,SubStateStrs),
   express(S,StateStr).

express_path_states([],[]).

% ===
% For debugging
% ===

debug_proposed(Current,Next,Moved,Path) :-
   express(Current,CurrentStr),
   express(Next,NextStr),
   length(Path,L),
   debug(pather,"...Proposed at path length ~d: ~w -> ~w (~q)",[L,CurrentStr,NextStr,Moved]).

debug_accepted(State) :-
   express(State,StateStr),
   debug(pather,"...Accepted: ~w",[StateStr]).

debug_visited(State) :-
   express(State,StateStr),
   debug(pather,"...Visited: ~w",[StateStr]).

debug_moved(X) :-
   debug(pather,"...Already moved: ~w",[X]).

debug_final(State) :-
   express(State,StateStr),
   debug(pather,"Final state reached: ~w",[StateStr]).

debug_current(State,Path) :-
   express(State,StateStr),
   express_path(Path,PathStr),
   length(Path,L),
   debug(pather,"Now at: ~w with path length ~d and path ~w",[StateStr,L,PathStr]).

debug_path(Path) :-
   express_path(Path,PathStr),
   debug(pather,"Path: ~w",[PathStr]).

% ===
% Moving blocks between three stacks, also recording the move
% ===

move(state(on(X, A), B, C), 
     state(A, on(X, B), C),
     moved(X,"A->B")).

move(state(on(X, A), B, C), 
     state(A, B, on(X, C)),
     moved(X,"A->C")).

move(state(A, on(X, B), C), 
     state(on(X, A), B, C),
     moved(X,"B->A")).

move(state(A, on(X, B), C), 
     state(A, B, on(X, C)),
     moved(X,"B->C")).

move(state(A, B, on(X, C)), 
     state(on(X, A), B, C),
     moved(X,"C->A")).

move(state(A, B, on(X, C)), 
     state(A, on(X, B), C),
     moved(X,"C->B")).

move(_,_,_,_) :- debug(pather,"No more moves",[]).

% ===
% Finding a path from an Initial State I to a Final State F.
% You have to remember the path taken so far to avoid cycles,
% instead of trying to reach the final state while the path-so-far
% is sitting inaccessible on the stack, from whence it can only be
% be reconstructed on return-fro-recursion.
% ===

fail_if_visited(State,Path) :- 
   (memberchk(State,Path) 
   -> (debug_visited(State),fail)
   ; true).

fail_if_moved(moved(X,_),LastMoved) :-
   (LastMoved = moved(X,_)
   -> (debug_moved(X),fail)
   ; true).

path2(F,F,Path,Path,_) :- 
    debug_final(F).

path2(I,F,PathToI,FullPath,LastMoved) :-
    dif(I,F),                          % I,F are sure different (program will block if it can't be sure)
    debug_current(I,PathToI),
    move(I,Next,Moved),                % backtrackably pattern-match yourself an acceptable next state based on I
    ground(Next),                      % fully ground, btw
    debug_proposed(I,Next,Moved,PathToI),
    fail_if_moved(Moved,LastMoved),    % don't want to move the same thing again
    fail_if_visited(Next,PathToI),     % maybe already visited?
    debug_accepted(Next),              % if we are here, not visited
    PathToNext = [Next|PathToI],
    path2(Next,F,PathToNext,FullPath,Moved). % recurse with path-so-far (in reverse) 

% ---
% Top call
% ---

path(I,F,Path) :- 
   PathToI = [I],
   path2(I,F,PathToI,FullPath,[]),     % FullPath will "fish" the full path out of the depth of the stack
   reverse(FullPath,Path),             % don't care about efficiency of reverse/2 at all
   debug_path(Path).

% ===
% Test 
% ===

:- begin_tests(pather).

test(one, true(Path = [state(void, void, on(c,on(a,on(b,void)))),
                       state(void, on(c,void), on(void(a,on(b,void)))),
                       state(on(a,void), on(c,void), on(b,void)),
                       state(on(b,on(a,void)), on(c,void), void),
                       state(on(c,on(b,on(a,void))), void, void)]))

     :- I = state(on(c,on(b,on(a,void))), void, void),
        F = state(void, void, on(c,on(a,on(b,void)))),
        path(I,F,Path).

:- end_tests(pather).

rt :- debug(pather),run_tests(pather).


% ...Accepted: [c,,ab]
% Now at: [c,,ab] with path length 24 and path [c,,ab]<-[,c,ab]<-[,ac,b]<-[b,ac,]<-[ab,c,]<-[ab,,c]<-[b,a,c]<-[,a,bc]<-[a,,bc]<-[a,b,c]<-[,ab,c]<-[c,ab,]<-[ac,b,]<-[ac,,b]<-[c,a,b]<-[,ca,b]<-[b,ca,]<-[cb,a,]<-[cb,,a]<-[b,c,a]<-[,bc,a]<-[a,bc,]<-[ba,c,]<-[cba,,]
% ...Proposed at path length 24: [c,,ab] -> [,c,ab] (moved(c,"A->B"))
% ...Already moved: c
% ...Proposed at path length 24: [c,,ab] -> [,,cab] (moved(c,"A->C"))
% ...Already moved: c
% ...Proposed at path length 24: [c,,ab] -> [ac,,b] (moved(a,"C->A"))
% ...Visited: [ac,,b]
% ...Proposed at path length 24: [c,,ab] -> [c,a,b] (moved(a,"C->B"))
% ...Visited: [c,a,b]
% ...Proposed at path length 23: [,c,ab] -> [,,cab] (moved(c,"B->C"))
% ...Accepted: [,,cab]
% Final state reached: [,,cab]
% Path: [cba,,]<-[ba,c,]<-[a,bc,]<-[,bc,a]<-[b,c,a]<-[cb,,a]<-[cb,a,]<-[b,ca,]<-[,ca,b]<-[c,a,b]<-[ac,,b]<-[ac,b,]<-[c,ab,]<-[,ab,c]<-[a,b,c]<-[a,,bc]<-[,a,bc]<-[b,a,c]<-[ab,,c]<-[ab,c,]<-[b,ac,]<-[,ac,b]<-[,c,ab]<-[,,cab]
ERROR: /home/homexercises/pather.pl:146:
        test one: wrong answer (compared using =)
ERROR:     Expected: [state(void,void,on(c,on(a,on(b,void)))),state(void,on(c,void),on(void(a,on(b,void)))),state(on(a,void),on(c,void),on(b,void)),state(on(b,on(a,void)),on(c,void),void),state(on(c,on(b,on(a,void))),void,void)]
ERROR:     Got:      [state(on(c,on(b,on(a,void))),void,void),state(on(b,on(a,void)),on(c,void),void),state(on(a,void),on(b,on(c,void)),void),state(void,on(b,on(c,void)),on(a,void)),state(on(b,void),on(c,void),on(a,void)),state(on(c,on(b,void)),void,on(a,void)),state(on(c,on(b,void)),on(a,void),void),state(on(b,void),on(c,on(a,void)),void),state(void,on(c,on(a,void)),on(b,void)),state(on(c,void),on(a,void),on(b,void)),state(on(a,on(c,void)),void,on(b,void)),state(on(a,on(c,void)),on(b,void),void),state(on(c,void),on(a,on(b,void)),void),state(void,on(a,on(b,void)),on(c,void)),state(on(a,void),on(b,void),on(c,void)),state(on(a,void),void,on(b,on(c,void))),state(void,on(a,void),on(b,on(c,void))),state(on(b,void),on(a,void),on(c,void)),state(on(a,on(b,void)),void,on(c,void)),state(on(a,on(b,void)),on(c,void),void),state(on(b,void),on(a,on(c,void)),void),state(void,on(a,on(c,void)),on(b,void)),state(void,on(c,void),on(a,on(b,void))),state(void,void,on(c,on(a,on(b,void))))]
 done
% 1 test failed
% 0 tests passed
false.

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.