留言版

简易的留言版一枚,(在我容忍的限度内)言论自由。想扔臭鸡蛋的,想送鲜花的,欢迎在此留言~

32 thoughts on “留言版

  1. “MATLAB 程序的变量命名问题” 一文,
    第一段代码:“M 酱告诉我,她要用 0.061435 秒才能干完这件事。”
    第二段代码:“M酱跑过来说,她这次用了 5.069864 就干完了这件事。”

    好像有点疑问,0.061435 比 5.069864 还大么?

  2. 我需要用iclingo求解器求解一个约束问题,但是碰到点问题,我的问题是这样的:1 2 -9 3 4 8这样的的数据代表节点1和节点2的约束关系为X1-X2<=-9,节点3和节点4的约束关系为X3-X4<=8,我需要将节点在(-10,10)之间取任意一个整数,满足上述两个任意一个不等式,这两个不等式是析取关系,问题有很多这样的析取式(1 2 -9 3 4 8),析取式之间是合取关系,就是每个析取式都要成立,但是每个析取式中的两个不等式仅成立一个即满足条件,我想用iclingo来求解这样的问题,但是规则文件我不知道该怎么写,您能给我一点意见么,不胜感激

    • 嗯,首先,iclingo 是 increasemental clingo 的缩写, 一般来说适用于需要分多个步骤解决的问题。你的问题似乎不会用到多个步骤,所以用 clingo 应该就可以了。

      那么大概给一个思路,首先你需要表示你有几个节点,我们就假设有10个吧:

      node(1..10).
      

      然后是节点的取值范围:

      value(-10..10).
      

      之后,第一个约束条件自然而然就成了每个节点只能赋一个值:

      1{assign(N,V):value(V)}1 :- node(N).
      

      下面,就是定义约束了,我们可以把每一个约束起一个名字,比如 constraint1-1,constraint1-2(不太确定这么起名字合不合法,你可以试试)之后你提供的两个约束就可以这样定义:

      constraint1-1 :- assign(1, V1), assign(2, V2), V1-V2<=-9.
      constraint1-2 :- assign(3, V1), assign(4, V2), V1-V2<=8.
      

      最后的问题就是如何表示这两个限制只用满足一个就可以了,根据这个文档(http://www.cs.utexas.edu/~vl/teaching/388L/clingo_guide.pdf)中 3.1.10 Aggregates 里,我们可以用这样的规则表示:

      1 #min [constraint1-1, constraint1-2].
      

      希望这个对你有所帮助。

  3. 我看了您给的意见,非常感谢您能帮我解答,但是有一个地方仍存在问题:第一,我举得例子是约束个数为1的情况,即每个约束有两个X1-X2<=-9这样的不等式,这两个不等式任意成立一个就好(即合取关系),但是问题可能存在10个或者20个这样的约束,但这些约束之间都要成立才可以说问题有解,这样同时成立的关系该如何表示呢,举例:1 2 -9 3 4 8 2 1 -3 4 2 6,这代表其中一个约束X1-X2<=-9和X3-X4<=8中的两个不等式任意成立一个即可,另一个约束X2-X1<=-3和X4-X2<=6中的两个不等式任意成立一个即可,但是这两个约束需要同时成立,这个合取关系怎么表示呢?而且当数据比较大的时候,任然需要把所有条件都列上么,有没有什么简便的方式,类似函数的功能

    • 每个规则之间都是与的关系,所以如果有两个规则

      1 #min [constraint11, constraint12].
      1 #min [constraint21, constraint22].
      

      那么这两个规则在这么写的情况下就需要同时成立。至于规则比较多的情况,约束是无论如何都要直接写出来的,不过约束的名字可以用点变量,比如说假设有 n 组约束

      constraint(1,1) :- xxxxxxx.
      constraint(1,2) :- xxxxxxx.
      .
      .
      .
      constraint(n,1) :- xxxxxxx.
      constraint(n,2) :- xxxxxxx.
      

      那么在指明约束对个数后,最后的限制条件可以写成

      constraintPair(1..n).
      pair(1..2).
      1{constraint(N,P):pair(P)}2 :- constraintPair(N).
      

      另外,我试了一下,那篇 PDF 里 Aggregates 那章内容里的语法有些老了,如果你用的是 clingo4.x 的话你可能需要看看新的语法是怎么写的(https://www.mat.unical.it/aspcomp2013/ASPStandardization)这部分我也不是很清楚了。

  4. 您给的代码给了我非常大的帮助,十分感激,下面是我编写的代码,出了点小问题:

    node(1..2).
    domain(-4..4).
    1{assign(N,D):domain(D)}1 :- node(N).
    constraint(1,1) :- assign(1, V1), assign(2, V2), V1-V2<=-9.
    constraint(1,2) :- assign(1, V1), assign(2, V2), V1-V2<=-9.
    constraint(2,1) :- assign(1, V1), assign(2, V2), V1-V2<=8.
    constraint(2,2) :- assign(1, V1), assign(2, V2), V1-V2<=8.
    pair(1..2).
    1{constraint(1,P)}2 :- pair(P).
    1{constraint(2,P)}2 :-pair(P).

    我需要constraint(1,1)和constraint(1,2) (这两者是或的关系)这两个任意成立一个,constraint(2,1) constraint(2,1) 任意成立一个即可,但是问题有解的条件是constraint(1,N) 和constraint(2,N) 都成立(这两者是与的关系),所以我把它们写成了两条并列的规则,可以发现我举得例子是无法满足的,但是当我运行后,得到的结果是有解的,这是为什么呢,是不能重复赋值么,就是constraint(1,N)这一类约束已经给结点1和结点2赋值了,但是constraint(2,N)就不能再给结点1和结点2赋值了么,运行结果是

    assign(2,-4) assign(1,-4)
    constraint(1,2) constraint(1,1)

    这是给结点1和结点2赋值为-4,并且满足constraint(1,2) 和constraint(1,1)这两个约束,但是算了一下并不满足呀,这是怎么回事呢

    • 额,抱歉,之前有点想歪了,最后那种 Aggregates 这么写的话是可以无视前面的约束推出 constraint(X,X) 的。那么就只有这么写了,因为至少满足一个约束等于不能同时不满足两个约束,所以,

      constraint11 :- xxxxxxx.
      constraint12 :- xxxxxxx.
      .
      .
      .
      constraintn1 :- xxxxxxx.
      constraintn2 :- xxxxxxx.
      
      :- not constraint11, not constraint12.
      .
      .
      .
      :- not constraintn1, not constraintn2.
      

      不过这样写就没得简化了,也许你可以先用其他程序写一个自动生成这种规则的脚本,然后再来求解。

      最后提示一下,即使那种 Aggregates 是可用的,你的这种写法

      1{constraint(1,P)}2 :- pair(P).
      

      也是不正确的,这代表着对于每一个 P,constraint(1,P) 都至少要有一个成立,这实际上就默认了任意 constraint(1,P) 都要成立。如果你想要表示 constraint(1,1), constraint(1,2) 至少一个成立,需要用

      1{constraint(1,P):pair(P)}2.
      

      不过这么写的话其实无视了之前对于 constraint(1,1), constraint(1,2) 的限制,而表示无论如何这两个之间至少要有一个成立,所以在你的问题里是行不通的。最后,你可以通过使用 clingo --text 来看你的程序展开后的样子,这样比较容易发现错误。

  5. 非常感谢您的耐心解答,我按着您上面提示的已经改正了,并写了一个脚本自动生成这个规则文件,我会认真看一下语法规则的,出了上面的问题也是语法没有掌握好,还有clingo --text这个也很好用,我会慢慢在研究的,再次谢谢您的帮助,真的帮了我很大的忙

    • 我又趴地上想了想,果然给 constraint 弄点简化还是有可能的,不过各类约束就得这么写了

      constraintPair(1..n).
      pair(1..2).
      1{constraint(N,P):pair(P)}2 :- constraintPair(N).
      
      :- assign(1, V1), assign(2, V2), V1-V2>-9, constraint(1,1).
      :- assign(3, V1), assign(4, V2), V1-V2>8, constraint(1,2).
      .
      .
      .
      

      这样应该可行。不过要注意的是,同一含义的规则不同的方法写出来计算速度差异可能很大,这个我上次听 Torsten 演讲的时候他在 Slides 里给了例子,我对于这块不是很清楚,你可以去 Potassco 的主页上看看,应该有相关的资料。

发表评论

电子邮件地址不会被公开。 必填项已用*标注