Smullyan型数控机床的求解
在这里，我建议找到一个解决Smullyan的数值机器作为在此定义。
问题陈述
它们是以数字列表作为输入的机器，并根据输入模式将其转换为另一个数字列表，遵循某些规则。下面是在上面的链接中给出的机器的规则，表达得稍微正式一些。假设M是机器，M( X )是X的转换，我们定义了如下几条规则：
M(2X) = X
M(3X) = M(X)2M(X)
M(4X) = reverse(M(X)) // reverse the order of the list.
M(5X) = M(X)M(X)任何不符合任何规则的东西都会被拒绝。以下是几个例子：
- M(245) = 45
- M(3245) = M(245)2M(245) = 45245
- M(43245) =反向(M(3245))=反向(45245)= 54254
- M(543245) = M(43245)M(43245) = 5425454254
问题是，找到X，这样：
- M(X) =2
- M(X) =X
- M(X) = X2X
- M(X) =反向(X)
- M(X) =反向(X2X)反向(X2X)
下面的第二个例子更复杂一些，包括详尽的搜索(特别是如果我想要前10或100种解决方案的话)。
M(1X2) = X
M(3X) = M(X)M(X)
M(4X) = reverse(M(X))
M(5X) = truncate(M(X)) // remove the first element of the list truncate(1234) = 234. Only valid if M(X) has at least 2 elements.
M(6X) = 1M(X)
M(7X) = 2M(X)问题：
- M(X) = XX
- M(X) =X
- M(X) =反向(X)
(非)解
用Prolog编写一个求解器非常简单。但这只是一种彻底的探索(也就是一种野蛮的力量)，可能需要一些时间来制定一些规则。
我试着用CLP(FD)用逻辑约束来表达这个问题，所以我尝试用列表上的约束(特别是append约束)来表达这个问题，但是无论我如何表达它，它总是归结为一个彻底的搜索。
问题
请问我可以采取甚麽方法，在合理的时间内解决这类问题呢？理想情况下，我希望能够生成比某个界限更短的所有解。
回答 4
Stack Overflow用户
发布于 2014-07-01 15:17:11
以下是@Celelibi的改进版本(cele_n)的另一个改进。粗略地说，它通过限制第一个参数的长度得到一个因子2，而通过预先测试两个版本得到另一个因子2。
cele_n SICStus 2.630s
cele_n SWI 12.258s 39,546,768 inferences
cele_2 SICStus 0.490s
cele_2 SWI 2.665s 9,074,970 inferencesappendh([], [], Xs, Xs).
appendh([_, _ | Ws], [X | Xs], Ys, [X | Zs]) :-
appendh(Ws, Xs, Ys, Zs).
m([H|A], X) :-
A = [_|_], % New
m(H, X, A).
m(1, X, A) :-
append(X, [2], A).
m(3, X, A) :-
appendh(X, B, B, X),
m(A, B).
m(4, X, A) :-
reverse(X, B),
m(A, B).
m(5, X, A) :-
X = [_| _],
m(A, [_|X]).
m(H1, [H2 | B], A) :-
\+ \+ ( H2 = 1 ; H2 = 2 ), % New
m(A, B),
( H1 = 6, H2 = 1
; H1 = 7, H2 = 2
).
answer3(X) :-
between(1, 13, N),
length(X, N),
reverse(X, A),
m(X, A).
run :-
time(findall(X, (answer3(X), write(X), nl), _)).Stack Overflow用户
发布于 2014-06-20 11:56:26
让我们来看看你的“更复杂”的问题。详尽的搜索工作非常出色！
下面是与Серге́й的解决方案的比较，通过考虑共同的目标，可以显着地改进该解决方案：
m([1|A], X) :-
A = [_|_],
append(X, [2], A).
m([E | X], Z) :-
m(X, Y),
( E = 3,
append(Y, Y, Z)
; E = 4,
reverse(Y, Z)
; E = 5,
Y = [_ | Z]
; E = 6,
Z = [1 | Y]
; E = 7,
Z = [2 | Y]
).对于查询time(findall(_, (question3(X), write(X), nl), _)).，我使用B8.1，SICStus 4.3b8：
Серге́й B tabled 104.542s
Серге́й B 678.394s
false B 16.013s
false B tabled 53.007s
Серге́й SICStus 439.210s
false SICStus 7.990s
Серге́й SWI 1383.678s, 5,363,110,835 inferences
false SWI 44.743s, 185,136,302 inferences这些额外的问题没有那么难回答。只有SICStus以上的m/2和call_nth/2
| ?- time(call_nth( (
length(Xs0,N),append(Xs0,Xs0,Ys),m(Xs0,Ys),
writeq(Ys),nl ), 10)).
[4,3,7,4,3,1,4,3,7,4,3,1,2,4,3,7,4,3,1,4,3,7,4,3,1,2]
[3,4,7,4,3,1,3,4,7,4,3,1,2,3,4,7,4,3,1,3,4,7,4,3,1,2]
[4,3,7,3,4,1,4,3,7,3,4,1,2,4,3,7,3,4,1,4,3,7,3,4,1,2]
[3,4,7,3,4,1,3,4,7,3,4,1,2,3,4,7,3,4,1,3,4,7,3,4,1,2]
[3,5,4,5,3,1,2,2,1,3,5,4,5,3,1,2,3,5,4,5,3,1,2,2,1,3,5,4,5,3,1,2]
[3,5,5,3,4,1,2,1,4,3,5,5,3,4,1,2,3,5,5,3,4,1,2,1,4,3,5,5,3,4,1,2]
[5,4,7,4,3,3,1,2,5,4,7,4,3,3,1,2,5,4,7,4,3,3,1,2,5,4,7,4,3,3,1,2]
[4,7,4,5,3,3,1,2,4,7,4,5,3,3,1,2,4,7,4,5,3,3,1,2,4,7,4,5,3,3,1,2]
[5,4,7,3,4,3,1,2,5,4,7,3,4,3,1,2,5,4,7,3,4,3,1,2,5,4,7,3,4,3,1,2]
[3,5,4,7,4,3,1,_2735,3,5,4,7,4,3,1,2,3,5,4,7,4,3,1,_2735,3,5,4,7,4,3,1,2]
196660ms
| ?- time(call_nth( (
length(Xs0,N),m(Xs0,Xs0),
writeq(Xs0),nl ), 10)).
[4,7,4,3,1,4,7,4,3,1,2]
[4,7,3,4,1,4,7,3,4,1,2]
[5,4,7,4,3,1,_2371,5,4,7,4,3,1,2]
[4,7,4,5,3,1,_2371,4,7,4,5,3,1,2]
[5,4,7,3,4,1,_2371,5,4,7,3,4,1,2]
[3,5,4,7,4,1,2,3,5,4,7,4,1,2]
[4,3,7,4,5,1,2,4,3,7,4,5,1,2]
[3,4,7,4,5,1,2,3,4,7,4,5,1,2]
[4,7,5,3,6,4,1,4,7,5,3,6,4,2]
[5,4,7,4,3,6,1,5,4,7,4,3,6,2]
6550ms
| ?- time(call_nth( (
length(Xs0,N),reverse(Xs0,Ys),m(Xs0,Ys),
writeq(Ys),nl ), 10)).
[2,1,3,4,7,1,3,4,7]
[2,1,4,3,7,1,4,3,7]
[2,1,3,5,4,7,_2633,1,3,5,4,7]
[2,1,5,4,7,3,2,1,5,4,7,3]
[2,4,6,3,5,7,1,4,6,3,5,7]
[2,6,3,5,4,7,1,6,3,5,4,7]
[2,_2633,1,5,3,4,7,_2633,1,5,3,4,7]
[2,_2633,1,5,4,3,7,_2633,1,5,4,3,7]
[2,1,3,4,4,4,7,1,3,4,4,4,7]
[2,1,3,4,5,6,7,1,3,4,5,6,7]
1500msStack Overflow用户
发布于 2014-06-21 03:43:35
我在这里提出另一种解决办法，基本上是详尽的探索。对于这些问题，如果m/2的第一个参数的长度是已知的，那么第二个参数的长度也是已知的。如果第二个参数的长度总是已知的，则可以通过将一些约束传播到递归调用来减少前面的搜索。但是，这与false提出的优化不兼容。
appendh([], [], Xs, Xs).
appendh([_, _ | Ws], [X | Xs], Ys, [X | Zs]) :-
appendh(Ws, Xs, Ys, Zs).
m([1 | A], X) :-
append(X, [2], A).
m([3 | A], X) :-
appendh(X, B, B, X),
m(A, B).
m([4 | A], X) :-
reverse(X, B),
m(A, B).
m([5 | A], X) :-
B = [_, _ | _],
B = [_ | X],
m(A, B).
m([H1 | A], [H2 | B]) :-
m(A, B),
( H1 = 6, H2 = 1
; H1 = 7, H2 = 2
).
answer3(X) :-
between(1, 13, N),
length(X, N),
reverse(X, A),
m(X, A).下面是分别花的时间:这段代码，这段代码在用每一种情况的约束交换递归调用时(类似于Sergey的解)，以及包含递归调用的false的解决方案。测试在SWI上运行，并搜索长度小于或等于13的所有解。
% 36,380,535 inferences, 12.281 CPU in 12.315 seconds (100% CPU, 2962336 Lips)
% 2,359,464,826 inferences, 984.253 CPU in 991.474 seconds (99% CPU, 2397214 Lips)
% 155,403,076 inferences, 47.799 CPU in 48.231 seconds (99% CPU, 3251186 Lips)所有措施都是通过呼叫执行的：
?- time(findall(X, (answer3(X), writeln(X)), _)).https://stackoverflow.com/questions/24313936
复制相似问题
腾讯云开发者
