用CLP求解Euler 4

Question

我得到了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]).

有办法加快速度吗？

Answer 1

您的原始型号使用SWI在我的机器上使用32.8s。该版本使用ff,bisect作为搜索策略，采用3.1：

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方法来解决这个问题：http://hakank.org/swi_prolog/euler4.pl (在0.2s内解决这个问题)。

Answer 2

这里有一种替代搜索策略，可以极大地缩短搜索时间。

...
labeling([max(P),down], [A,B,C]).

理由是：

在10^3.

• In、B和C上搜索

1. ，而不是P，可能会将搜索空间的大小从10^6顺序减少到仅用P顺序来最大化P，使用搜索选项down.

来尝试更大的A值( B和C (特别是A) )是很有趣的。

在SWISH中，这将时间从~63秒缩短到大约0.2秒。