Prolog 手动或自定义标签 [英] Prolog manual or custom labeling

问题描述

我目前正在为 Prolog 中的平面规划问题编写求解器，但标签部分存在一些问题.

当前的问题是我发布了限制条件，但是当我启动标签时，需要很长时间才能找到解决方案.我想引入一些启发式方法.

我的问题是，如何手动标记我的变量?恐怕在定义了这样的 clpfd 变量之后:

Xinf..Xsup 中的 X

并限制它，如果我做类似的事情:

 fd_sup(X, Xmax),X = Xmax，...

在我的自定义标签中，我不会使用 Prolog 的回溯功能来测试 X 域的其他值.我错了吗 ?

此外，有没有比编写自定义标签程序更聪明的方法来标记我的变量?我的启发式思想包括尝试可变域的极值(例如 max(X)、min(X)、max(X-1)、min(X-1) 等...)

希望你能帮助我:)

解决方案

首先，始终尝试内置启发式方法.ff 通常是一个很好的策略.

对于自定义标签策略，通常最简单的方法是首先将域转换为列表，然后重新排序列表，然后简单地使用 member/2 使用 new 分配域的值订购.

一个好的构建黑色是 dom_integers/2，将有限 CLP(FD) 域与整数列表相关联:

:- use_module(library(clpfd)).dom_integers(D, Is) :- 短语(dom_integers_(D), Is).dom_integers_(I) -->{整数(I)}，[I].dom_integers_(L..U) -->{ numlist(L, U, Is) }, Is.dom_integers_(D1\/D2) -->dom_integers_(D1), dom_integers_(D2).

您的具体策略很容易用这样的有序整数列表表达，将这些整数与第二个列表相关联，其中值按照您描述的顺序出现:

outside_in([]) -->[].external_in([I]) -->[一世].external_in([First|Rest0]) -->[第一，最后]，{ append(Rest, [Last], Rest0) },外面_输入(休息).

示例查询和结果:

<预>?- 短语(outside_in([1,2,3,4]), 是).是 = [1, 4, 2, 3] ;错误的.

将其与 fd_dom/2 和 dom_integers/2 结合，我们得到(省略了除 X 之外的变量的绑定):

?- X in 10..20,fd_dom(X, Dom),dom_integers(Dom, Is0),短语(outside_in(Is0)，是)，成员(X，是).X = 10 ;X = 20 ;X = 11 ;X = 19 ;X = 12 ;X = 18 ;等等.

member/2 保留了不确定性.

I am currently writing a solver for a floor planning problem in Prolog and have some issues with the labeling part.

The current problem is my constraints are posted but when I launch the labeling, it takes forever to find a solution. I would like to bring in some heuristics.

My question is, how do I manually label my variables ? I am afraid that after defining a clpfd variable like this :

X in Xinf..Xsup

and constraining it, If I do something like :

    fd_sup(X, Xmax),
    X = Xmax,
...

in my custom label, I won't be using the backtrack ability of Prolog to test the other values of X's domain. Am I wrong ?

Also, is there a smarter way to label my variables than writing custom labeling procedures ? My idea of heuristics would consist in trying extrema of a variable domain alternatively (like max(X), min(X), max(X-1), min(X-1) etc...)

Hope you can help me :)

解决方案

First, always try built-in heuristics. ff is often a good strategy.

For custom labeling strategies, it is often easiest to first convert the domain to a list, then reorder the list, and then simply use member/2 to assign the values of the domain using the new order.

A good building black is dom_integers/2, relating a finite CLP(FD) domain to a list of integers:

:- use_module(library(clpfd)).

dom_integers(D, Is) :- phrase(dom_integers_(D), Is).

dom_integers_(I)      --> { integer(I) }, [I].
dom_integers_(L..U)   --> { numlist(L, U, Is) }, Is.
dom_integers_(D1\/D2) --> dom_integers_(D1), dom_integers_(D2).

Your specific strategy is easily expressed on a list of such ordered integers, relating these integers to a second list where the values occur in the order you describe:

outside_in([]) --> [].
outside_in([I]) --> [I].
outside_in([First|Rest0]) --> [First,Last],
        { append(Rest, [Last], Rest0) },
        outside_in(Rest).

Sample query and result:

?- phrase(outside_in([1,2,3,4]), Is).
Is = [1, 4, 2, 3] ;
false.

Combining this with fd_dom/2 and dom_integers/2, we get (bindings for variables other than X omitted):

?- X in 10..20,
   fd_dom(X, Dom),
   dom_integers(Dom, Is0),
   phrase(outside_in(Is0), Is),
   member(X, Is).
X = 10 ;
X = 20 ;
X = 11 ;
X = 19 ;
X = 12 ;
X = 18 ;
etc.

Nondeterminism is preserved by member/2.

这篇关于Prolog 手动或自定义标签的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！