私が目にするほとんどの実装では、再帰的なソリューションを使用しています。しかし、私はこれを望んでいません。幅優先や深さ優先などの検索アルゴリズムを使用してツリー内を検索したい。
ありがとうございました
質問する
5107 次
2 に答える
2
BFSはそのようなものかもしれません（SWI-Prologで動作します）
% to store the tree of the possibilities
:- dynamic lst_hanoi/1.
hanoi_BFS :-
init,
% BFS loop
repeat,
next,
finish(Hanoi),
% display the solution
reverse(Hanoi, Rev_Hanoi),
maplist(writeln, Rev_Hanoi).
init :-
% cleaning of the bdd
retractall(lst_hanoi(_)),
% store the initial list of configurations (only one)
assert(lst_hanoi([[hanoi([1,2,3,4], [], [])]])).
% we search the final configuration
% here the first two columns are empty
finish([hanoi([], [], A) | B]) :-
% get the list of configurations
lst_hanoi(Lst),
% test
member([hanoi([], [], A) | B], Lst).
next :-
% get the actual list of configurations
retract(lst_hanoi(Hanoi)),
% act on each configuration
maplist(move_next,Hanoi, Hanoi_Temp),
% concatenate the list of new onfigurations
append(Hanoi_Temp, Hanoi_1),
% some configurations are empty, remove them
% SWI-Prolog feature
exclude(=([]), Hanoi_1, Hanoi_2),
% store the new list
assert(lst_hanoi(Hanoi_2)).
% compute the next configurations got from one configuration
move_next([Hanoi | T1], R) :-
% Only the first element of the list is usefull
% compute possible moves
move(Hanoi, Next),
% create the new configuration
maplist(new_hanoi([Hanoi| T1]), Next, R).
% add the new position if it has not been already seen
new_hanoi(T, H, [H | T]) :-
\+member(H, T), !.
% else the configuration will be remove
new_hanoi(_T, _H, []).
% the list of all the possibilities of moves
move(hanoi([H | T], [], []), [hanoi(T, [H], []), hanoi(T, [], [H])]).
move(hanoi([], [H | T], []), [hanoi([H], T, []), hanoi([], T, [H])]).
move(hanoi([], [], [H | T]), [hanoi([H], [], T), hanoi([], [H], T)]).
move(hanoi([H1 | T1], [H2 | T2], []),
[hanoi(T1, [H2 | T2], [H1]), hanoi([H1 | T1], T2, [H2]), hanoi([H2, H1 | T1], T2, [])]) :-
H1 > H2, !.
move(hanoi([H1 | T1], [H2 | T2], []),
[hanoi(T1, [H2 | T2], [H1]), hanoi([H1 | T1], T2, [H2]), hanoi(T1, [H1, H2 | T2], [])]).
move(hanoi([H1 | T1], [], [H2 | T2]),
[hanoi(T1, [H1], [H2 | T2]), hanoi([H1 | T1], [H2], T2), hanoi([H2, H1 | T1], [], T2)]) :-
H1 > H2, !.
move(hanoi([H1 | T1], [], [H2 | T2]),
[hanoi(T1, [H1], [H2 | T2]), hanoi([H1 | T1], [H2], T2), hanoi(T1, [], [H1, H2 | T2])]).
move(hanoi([], [H1 | T1], [H2 | T2]),
[hanoi([H1], T1, [H2 | T2]), hanoi([H2], [H1 | T1], T2), hanoi([], [H2, H1 | T1], T2)]) :-
H1 > H2, !.
move(hanoi([], [H1 | T1], [H2 | T2]),
[hanoi([H1], T1, [H2 | T2]), hanoi([H2], [H1 | T1], T2), hanoi([], T1, [H1, H2 | T2])]).
move(hanoi([H1 | T1], [H2 | T2], [H3 | T3]),
[hanoi(T1, [H1, H2 | T2], [H3 | T3]),
hanoi(T1, [H2 | T2], [H1, H3 | T3]),
hanoi([H1 | T1] , T2, [H2, H3 | T3])]) :-
H1 < H2, H2 < H3, !.
move(hanoi([H1 | T1], [H2 | T2], [H3 | T3]),
[hanoi(T1, [H1, H2 | T2], [H3 | T3]),
hanoi(T1, [H2 | T2], [H1, H3 | T3]),
hanoi([H1 | T1] , [H3, H2 | T2 ], T3)]) :-
H1 < H3, H3 < H2, !.
move(hanoi([H1 | T1], [H2 | T2], [H3 | T3]),
[hanoi([H2, H1 | T1], T2, [H3 | T3]),
hanoi([H1 |T1], T2, [H2, H3 | T3]),
hanoi(T1 , [H2 | T2 ], [H1 , H3 | T3])]) :-
H2 < H1, H1 < H3, !.
move(hanoi([H1 | T1], [H2 | T2], [H3 | T3]),
[hanoi([H2, H1 | T1], T2, [H3 | T3]),
hanoi([H1 |T1], T2, [H2, H3 | T3]),
hanoi([H3, H1 | T1] , [H2 | T2 ], T3)]) :-
H2 < H3, H3 < H1, !.
move(hanoi([H1 | T1], [H2 | T2], [H3 | T3]),
[hanoi([H3, H1 | T1], [H2 | T2], T3),
hanoi([H1 |T1], [H3, H2 |T2], T3),
hanoi(T1 , [H1, H2 | T2 ], [H3 | T3])]) :-
H3 < H1, H1 < H2, !.
move(hanoi([H1 | T1], [H2 | T2], [H3 | T3]),
[hanoi([H3, H1 | T1], [H2 | T2], T3),
hanoi([H2, H1 |T1], T2, [H3 |T3]),
hanoi([H1 | T1] , [H3, H2 | T2 ], T3)]) :-
H3 < H2, H2 < H1, !.
このコードは改善される可能性があります。
于 2012-06-21T15:01:29.510 に答える
0
OK、これは本当に簡単なはずです。本当に、Prolog ではすべてが簡単なはずです。通常、質問を書き留めることが解決策そのものです。:)
それで、私たちは何を持っていますか？3つの塔、と言いt(X,Y,Z)ます。各タワーは、サイズが小さい順に並べられた一連のディスクです。小さいディスクのみが大きいディスクの上に配置でき、その逆はできません。
move1( t([A|B],[C|D],E), t(B,[A,C|D],E) ) :- A < C, writeln([move,A,on,C]).
move1( t([A|B],[],E), t(B,[A],E) ) :- writeln([move,A,on,empty]).
これらの 2 つのルールは、1 番目のタワーから 2 番目のタワーへの移動 (より大きなディスクの上または空のタワーへの移動) を示しています。したがって、これらは可能な唯一の移動であり、上部ディスクを最初の極から 2 番目の極に移動します。しかし、ディスクを 3 番目の極に移動することも、2 番目または 3 番目の極から移動することもできます。
move( t(A,B,C), t(X,Y,Z)):-
move1( t(A,B,C), t(X,Y,Z)) ; move1( t(A,C,B), t(X,Z,Y)) ;
move1( t(B,C,A), t(Y,Z,X)) ; move1( t(B,A,C), t(Y,X,Z)) ;
move1( t(C,A,B), t( ... )) ; move1( t(C,B,A), t( ... )).
ほら、質問についてすでに知っていることを書き留めるだけです。これmove/2で、指定された位置 (その 1 番目の引数) からの可能な動きを記述し、新しい位置 (2 番目の引数) を与える述語ができました。
これは、ここでの検索スペースを定義する述語です。各ポイントで、私たちは動き、解決策があるかどうかを確認します。これは深さ優先の検索です。なぜなら、それが私たちの目標につながることを期待して、私たちは動き、それをさらに深く掘り下げていくからです。
hanoi( Start, Finish):- move(Start,Finish), write('Done.'),nl.
hanoi( Start, Finish):- move(Start, P), hanoi(P,Finish).
たとえば、hanoi(t([1,2],[],[]), t([],[1,2],[])).今何が起こるか?で実行します。無限にループし、同じ動きを何度も試みます。しかし、新しいものを試して最終的に最終状態に達したとしても、どの動きがそこにつながったのかはわかりません。
したがって、移動をすぐに書き出す必要はありませんが、移動のリストを維持し、最終状態に達したときにのみ、そこに到達した成功した移動のリストを書き出す必要があります。すでに行った動きを繰り返さないように、この動きのリストを確認することもできます。
move1( t([A|B],[C|D],E), t(B,[A,C|D],E) ) :- A < C.
move1( t([A|B],[],E), ... ).
move( P, P2, M, [P2|M] ):- move(P,P2), \+memberchk(P2,M).
これは「これまでの動き」、つまりこれまでに訪れたすべての位置のリストMであり、4 番目の引数は位置の新しいリストです - 新しい位置が以前に訪問されていない場合 (または、私たちの最初のバージョンはそうでした）。
今、私たちはそれを次のように呼びます
hanoi(Start,Finish,N):- hanoi_dfs(Start,Finish,[Start],N).
hanoi_dfs( Start, Finish, M, N):- move(Start, Finish, M, M2),
length(M2,K), N is K-1,
reverse(M2,L), maplist(writeln,L), nl.
hanoi_dfs( Start, Finish, M, N):- move(Start, P, M, M2),
hanoi_dfs(P, Finish, M2, N).
そして、私たちは得る
?- hanoi(t([1,2],[],[]), t([],[1,2],[]), _).
t([1, 2], [], [])
t([2], [1], [])
t([], [1], [2])
t([], [], [1, 2])
t([1], [], [2])
t([1], [2], [])
t([], [1, 2], [])
ただし、この DFS は暗黙的です。Prolog に依存して動きを試します。明示的な検索は、各位置のすべての可能な動きを見つけ、これらの動きを操作バッファーに追加します。これには、位置とその位置につながる動きのリストのペアが含まれます。
現在、明示的な DFS は、そのリストから最初の要素を削除し、その位置で可能なすべての動きを見つけて、新しい位置のリストを取得し、それぞれが動きのリストとペアになっていることで機能し、このリストを操作の先頭にプレフィックスとして付けます。バッファ。
BFS は、この新しい位置のリストを操作バッファーの末尾に追加するという点で DFS とは異なります。
于 2012-06-24T20:47:16.650 に答える