dram.me

Swift模板工具GYP

GYPSwift内部使用的一个简单的模板工具,在阅读Swift代码时,了解GYP是必要的。

GYP的文档可以运行gyp.py -h查看。

答案集编程语义

答案集编程并不是通用的编程语言,它主要适用于解决一些组合(combinatorial)问题,例如基于知识表示的事实推理过程。

求解过程

答案集编程包括两个过程,grounding和solving。以以下代码为例:

num(1..2).

queen(X, Y) :- not free(X, Y), num(X), num(Y).
free(X, Y) :- not queen(X, Y), num(X), num(Y).

grounding的结果(执行clingo --text example.lp)是:

num(1).
num(2).
queen(1,1):-not free(1,1).
queen(2,1):-not free(2,1).
queen(1,2):-not free(1,2).
queen(2,2):-not free(2,2).
free(1,1):-not queen(1,1).
free(2,1):-not queen(2,1).
free(1,2):-not queen(1,2).
free(2,2):-not queen(2,2).

grounding去处了所有的变量,体现在Prolog中的choice point在这里已经在grounding阶段处理,所有的choice point都包含在grounding的结果中。

如果grounding结果中不包含negation,那么求解结果只有一个stable模型,如果包含negation,那么就会出现多个stable模型。

人工智能资料汇集

补遗

  1. 一些人工智能相关的国际性比赛:ICAPS CompetitionsSAT Competitions。—— 2017-05-09

以下是人工智能资料的汇集:

事务和创新

对于事务性的重复的事,常有着本能的排斥,一部分原因是因为在处理事情的过程中,预期是学习不到新的知识的。

而转变的关键,就在于改变观念,在事务中发现成长。而另一角度来说,创新也正在于此,在重复的事务中发现可以改变的点。

如果从这个角度思考的话,处理事情动力的来源,不在于意义和事情本身的价值,而在于自我以及周围环境经由不断创新的成长。

正如《SRE:Google运维解密》第5章减少琐事中所说的:

如果我们都致力于每一周通过工程工作消除一点琐事,就可以持续性地整顿服务……让我们多创新,少干琐事吧!

答案集编程练习(第一期)

补遗

  1. 该练习参考了Luger《人工智能》第二部分前言中的例子。—— 2017-04-28

当前针对答案集编程的资料不多,多数有较高的门槛,在学习的过程中存在一定阻力。

现在想通过实践的方式辅助理解,这里将题目与参考的程序加以整理。以下是第一期的题目及题解,完整的程序可以在这里查看。

题目

abcd四个块,列举将他们叠加摆放在桌面的所有方法。其中abc为正方形,d为三角形。

解题

解题基本按四个步骤进行。

描述事实

block(a).
block(b).
block(c).
block(d).

cube(a).
cube(b).
cube(c).
pyramid(d).

枚举答案

所有块必须摆放在桌面或者其他块之上,基于此可以列举备选的所有可能答案集。

on_table(X) ; on(X, Y) : block(Y) :- block(X).

添加约束

在上一步骤获得的答案集中,有些答案集是无效的,需要加以筛选。

只允许将其中一个块放置在桌面上:

:- on_table(X), on_table(Y), X != Y.

块上之后放置一个块:

:- on(X, Z), on(Y, Z), X != Y.

不能将块放置在三角形之上:

:- on(_, X), pyramid(X).

不能循环堆叠:

above(X, Y) :- on(X, Y).
above(X, Y) :- on(X, Z), above(Z, Y).
:- above(X, X).

显示结果

#show on/2.
#show on_table/1.

结果

以下是在Clingo 5.2中运行的结果:

clingo version 5.2.0
Reading from blocks.lp
Solving...
Answer: 1
on_table(b) on(d,a) on(c,b) on(a,c)
Answer: 2
on_table(b) on(c,a) on(a,b) on(d,c)
Answer: 3
on_table(c) on(b,a) on(d,b) on(a,c)
Answer: 4
on_table(a) on(b,a) on(c,b) on(d,c)
Answer: 5
on_table(c) on(d,a) on(a,b) on(b,c)
Answer: 6
on_table(a) on(c,a) on(d,b) on(b,c)
SATISFIABLE

Models       : 6
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.001s

← older posts newer posts →