用 CLP 求解欧拉 4

Question

我对 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]).

有没有办法加快速度？

Answer 1

您的原始模型在我使用 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 秒内解决问题）。

Answer 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 秒。

用 CLP 求解欧拉 4

Solving Euler 4 with CLP

prolog

clpfd