在我看到的大多数实现中，使用递归解决方案。但是，我不想要这个。我想用搜索算法在树中搜索，比如广度优先或深度优先。
谢谢你
问问题
5107 次
2 回答
2
BFS may be something like that (works with 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, !.
This code may be improved !
于 2012-06-21T15:01:29.510 回答
0
好的，所以这应该很容易。真的，在 Prolog 中一切都应该很容易——写下问题通常就是解决方案本身。:)
那么，我们有什么？三塔，说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]).
这两个规则描述了从第一个塔到第二个的移动，或者在一个更大的圆盘上，或者到一个空塔上。所以这些是唯一可能的移动，将顶部圆盘从第一极移动到第二极。但是我们也可以将磁盘移动到第三极，或者从第二极或第三极：
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，它描述了从给定位置（它的第一个参数）的任何可能的移动，给了我们新的位置（它的第二个参数）。
这是在这里为我们定义搜索空间的谓词。在每一点上，我们都会采取行动，看看我们是否有解决方案。这是一个深度优先的搜索，因为我们采取行动并深入研究它，希望它能够引导我们实现目标。
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是“到目前为止的移动”，即到目前为止访问过的所有位置的列表，第四个参数是新的位置列表 - 如果我们之前没有访问过我们的新位置（否则我们会绕圈子，比如我们的第一个版本做到了）。
现在我们称它为
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 回答