2

Sicstus 4.3.0 有一个优雅的新特性来枚举优化问题中的所有解决方案， minimize(:Goal,?X,+Options).

在测试新的启发式搜索时，由于搜索空间大，通常无法证明全局最优，这意味着搜索需要很长时间。

但通常（尤其是对于工业问题）找到一个“足够好”的解决方案就足够了。

那么问题来了：

我有一个问题，我很快就找到了一个“足够好”的解决方案，但我无法证明全局最优。所以现在我想使用最大化来查看我的搜索启发式在搜索过程中的表现，而不是等待全局最优。

使用新的 4.3.0 版本，我可以这样做：

findall(L,     
(
   minimize(labeling([],VarsList), Es, [all]),
   L = Es
),
Ls)

然后，我将得到一个列表Ls，其中包含在跟踪上找到的所有解决方案，以实现全局最优。

但我不想等待全局最优，所以我添加了time_out这样的：

findall(L,
(
  minimize(labeling([time_out(MaxLabelingTime,LabelingResult)],VarsList), Es, [all]),
  L = [Es,LabelingResult]
),
Ls),

这应该找到所有解决方案，但不会MaxLabelingTime在每个回溯之间花费更多时间。但是，如果time_out从那时起的启动将未被实例化，Es则这种方式将失败：

Instantiation error in argument 2 of user:minimize/2
! goal:  minimize(user:labeling([time_out(500,_201)],[_203,_207....]),_179)

我的解决方案/解决方法如下：

findall(L,
(
   minimize(my_labeling(MaxLabelingTime,LabelingResult,VarsList,Es), Es, [all]),
   L = [Es,LabelingResult]
),
Ls)

my_labeling(MaxLabelingTime, LabelingResult, VarsList,Es):-
   labeling([time_out(MaxLabelingTime,LabelingResult)], VarsList),
   (  LabelingResult=time_out
   -> Es=0
   ;  true
   ).

这个接缝可以按预期工作，但我不确定这是否是一个好方法？

4

0 回答 0