用 CLP 求解欧拉 4
Solving Euler 4 with CLP
我对 Project Euler 4 有这个非常慢的解决方案,
:- use_module(library(clpfd)).
euler_004(P) :-
A in 1..9,
B in 0..9,
C in 0..9,
P #= A * 100001 + B * 10010 + C * 1100,
D in 100..999,
E in 100..999,
E #>= D,
P #= D * E,
labeling([max(P)], [P]).
有没有办法加快速度?
您的原始模型在我使用 SWI-Prolog 的机器上需要 32.8 秒。这个版本,使用ff,bisect
作为搜索策略,耗时3.1s:
euler4c(P) :-
A in 1..9,
B in 0..9,
C in 0..9,
D in 100..999,
E in 100..999,
E #>= D,
P #= D * E,
P #= A * 100001 + B * 10010 + C * 1100,
labeling([max(P),ff,bisect], [P]). % 3.1s
此外,SWI Prolog 的 CLP 求解器通常不是最快的 CLP 求解器,因此其他 Prolog 的可能更快。
此外,请参阅我的非 CLP SWI Prolog 解决此问题的方法:http://hakank.org/swi_prolog/euler4.pl(在大约 0.2 秒内解决问题)。
这是另一种搜索策略,可以极大地缩短时间。
...
labeling([max(P),down], [A,B,C]).
理由是:
- 在
A
、B
和 C
上搜索而不是 P
可能会减少搜索 space 的大小,顺序为 10^6
到只有 10^3
.
- 为了最大化
P
,有趣的是首先尝试A
、B
和C
的较大值(尤其是A
) ,这是通过使用搜索选项 down
. 实现的
在 SWISH 中,这将时间从约 63 秒减少到大约 0.2 秒。
我对 Project Euler 4 有这个非常慢的解决方案,
:- use_module(library(clpfd)).
euler_004(P) :-
A in 1..9,
B in 0..9,
C in 0..9,
P #= A * 100001 + B * 10010 + C * 1100,
D in 100..999,
E in 100..999,
E #>= D,
P #= D * E,
labeling([max(P)], [P]).
有没有办法加快速度?
您的原始模型在我使用 SWI-Prolog 的机器上需要 32.8 秒。这个版本,使用ff,bisect
作为搜索策略,耗时3.1s:
euler4c(P) :-
A in 1..9,
B in 0..9,
C in 0..9,
D in 100..999,
E in 100..999,
E #>= D,
P #= D * E,
P #= A * 100001 + B * 10010 + C * 1100,
labeling([max(P),ff,bisect], [P]). % 3.1s
此外,SWI Prolog 的 CLP 求解器通常不是最快的 CLP 求解器,因此其他 Prolog 的可能更快。
此外,请参阅我的非 CLP SWI Prolog 解决此问题的方法:http://hakank.org/swi_prolog/euler4.pl(在大约 0.2 秒内解决问题)。
这是另一种搜索策略,可以极大地缩短时间。
...
labeling([max(P),down], [A,B,C]).
理由是:
- 在
A
、B
和C
上搜索而不是P
可能会减少搜索 space 的大小,顺序为10^6
到只有10^3
. - 为了最大化
P
,有趣的是首先尝试A
、B
和C
的较大值(尤其是A
) ,这是通过使用搜索选项down
. 实现的
在 SWISH 中,这将时间从约 63 秒减少到大约 0.2 秒。