optimization - 在 prolog 中找到最高可能的评估

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 1.

:- use_module (library(clpfd))。

:- set_prolog_flag (toplevel_print_anon，假)。

length_Booleans_weight_(长度， bool 值，重量，[重量| bool 值]):-
length ( bool 值，长度)，
bool 值 ins 0..1,
sum ( bool 值，#=，权重)。

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

?- member (长度，[10,20,30,40,50,60,70,80,90,100])，
call_time ( once ((length_Booleans_weight_(Length,Booleans,Weight,_Zs),
labeling ([最大(重量)],_Zs))),
T_ms )。
Len = Weight, Weight = 10 , T_ms = 4, bool 值 = [1,1,1,1,1,1,1,1,1,1]
; Len = 重量，重量 = 20，T_ms = 32， bool 值 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1]
; Len = 重量，重量 = 30，T_ms = 58， bool 值 = [1,1,1,1,1,1,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 = 重量，重量 = 40，T_ms = 124， bool 值 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,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 = 重量，重量 = 50，T_ms = 234， bool 值 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,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 = 重量，重量 = 60，T_ms = 376， bool 值 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,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 = 重量，重量 = 70，T_ms = 580， bool 值 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,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 = 重量，重量 = 80，T_ms = 845， bool 值 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,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 = 重量，重量 = 90，T_ms = 1178， bool 值 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,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 = 重量，重量 = 100，T_ms = 1619， bool 值 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ,1,1,1,1,1,1,1,1,1,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 = Length, maplist(=(1), Booleans) .
脚注 2:使用 SWI-Prolog 7.3.14(64 位)。