optimization - 在序言中找到可能的最高评价

Question

我正在解决一个必须评估博弈树结果的问题。问题是我想比较树的结果。为此，我有这样的东西:

bestOption(SomeVariables, Result) :-
   generateOption(SomeVariables, Result),
   evaluate(Result). % dark magic ensures that Result is the highest possible value

但是，我现在想找到最佳的结果。最好有一些巧妙的缓存。有什么想法吗？

这是目标编程语言的序言。

知道如何做到这一点吗？

Answer 1

在此答案中，我们正在搜索 Boolean长度列表N最大Hamming weight ¹。

:- use_module(library(clpfd)).

:- set_prolog_flag(toplevel_print_anon, false).

length_Booleans_weight_(Length, Booleans, Weight, [Weight|Booleans]) :-
   length(Booleans, Length),
   Booleans ins 0..1,
   sum(Booleans, #=, Weight).

让我们使用 call_time/2 对于不同问题实例大小的运行时测量²:

?- member(Length, [10,20,30,40,50,60,70,80,90,100]),
   call_time(once((length_Booleans_weight_(Length,Booleans,Weight,_Zs),
                   labeling([max(Weight)],_Zs))),
             T_ms).
   Len = Weight, Weight =  10, T_ms =    4, Booleans = [1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  20, T_ms =   32, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  30, T_ms =   58, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  40, T_ms =  124, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  50, T_ms =  234, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  60, T_ms =  376, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  70, T_ms =  580, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  80, T_ms =  845, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  90, T_ms = 1178, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight = 100, T_ms = 1619, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1].

---

^{脚注1:当然，我们知道所有最大值都满足目标Weight<a href="http://www.swi-prolog.org/pldoc/doc_for?object=%28%3D%29/2" rel="noreferrer noopener nofollow"> = </a>Length, <a href="https://stackoverflow.com/questions/6682987/prolog-map-procedure-that-applies-predicate-to-list-elements/6683502#6683502" rel="noreferrer noopener nofollow">maplist</a>(<a href="http://www.swi-prolog.org/pldoc/doc_for?object=%28%3D%29/2" rel="noreferrer noopener nofollow">=</a>(1), Booleans) .
脚注 2:使用 SWI-Prolog 7.3.14(64 位)。}