人工智能实验指导书.doc

贵州大学计算机科学与技术学院计算机科学与技术科系本科生人工智能实验指导书/实验教学大纲 王以松 2012年目 录实验一 人工智能冲浪3实验二 SAT求解描述性问题4实验三 Prolog基本编程环境5实验四 ASP描述性问题求解8参考资料：10实验一人工智能冲浪1、 实验目的了解人工智能的定义/讨论，研究内容，研究进展以及相关的重要人物和有影响的事件。2、 实验原理通过网络搜索引擎，例如google，baidu，yahoo等，以关键词在网络上搜索相关内容。3、 实验内容搜索如下内容：1） 人工智能的定义与讨论，特别是wiki百科在这方面的讨论.2） 人工智能研究方向/领域，以及本领域中有重大影响力的论文1-2篇，例如在citeseer上的被引用次数最多.3） Turing奖获得者中，人工智能领域的专家，例如McCarthy, Pearl, Newell, Simon, Feigenbaum等，他们的获奖理由/在人工智能方面的突出贡献.4） IBM Deep Blue， Watson；Checker；Big Dog（Boston Dynamics） 4、 实验描述及要求选择其中一个实验内容，整理形成一个AI的主题介绍。5、 实验步骤无要求.6、 参考程序 无.实验二SAT求解描述性问题 1、 实验目的通过学习并使用一个SAT求解器，例如MiniSat，了解Satisfiability描述性问题求解方法。了解SAT求解器的研发现状。2、 实验原理把给定的问题表达成逻辑公式CNF形式， 使得其模型对应问题的解。经过翻译后，输入给SAT求解器，并将其输出结果解释后输出，从而读出问题的一个解。3、 实验内容1） 选用一个SAT求解器，例如MiniSat等。2） 搜索公开的SAT的benchmark/测试用例，就图着色等问题生成CNF公式， 或随机生成CNF公式。3） 调用SAT求解器，例如MiniSat，计算其模型。4） 输出对应问题的解。4、 实验描述及要求将上述实验内容和结果书写成实验报告。5、 实验步骤无要求。6、 参考程序sat的输入格式可采用DIMACS字句的如下形式:c 表示注释c file name: fc start with commentsccp cnf 5 3 c （5个原子，3个字句 开始的第一行）1 -5 4 0 c 字句结束 是0，-5表示第5个原子的经典否定-1 5 3 4 0-3 -4 0上面字句集为：x1, x5, x4, x1, x5, x3, x4 x3, x4调用minisat f将得到输出表示该字句集是可满足的，使之满足的赋值是把全部原子赋值为false（如果是赋值为true，则会输出该原子的编号）。实验三Prolog基本编程环境1、 实验目的通过Prolog环境下的编程，了解基于逻辑的问题求解理论。并熟悉一个具体的Prolog语言，特别是各种数据结构，及其开发环境和开发方法。通过具体的编程实践，掌握基本的prolog解决问题的方法。2、 实验原理Prolog（Programming in Logic的缩写）是一种逻辑编程语言。它建立在逻辑学的理论基础之上， 最初被运用于自然语言等研究领域。现在它已广泛的应用在人工智能的研究中，它可以用来建造专家系统、自然语言理解、智能知识库等。 3、 实验内容1） 快速排序：给定一个整数链表，按照给定顺序重排并输出。2） 图着色：给定一个图（可以有各种表示），和一些颜色，输出对图的一种着色方案。3） 图的给定两点的最短距离：给定一个距离图（节点之间有距离），和其中的两个点，输出一个该两点之间的最短路径及其距离。4） N-皇后问题：给定一个N，输出在N个皇后在NN棋盘上的一种可行布局(见参考程序)。4、 实验描述及要求选择上述实验内容中的任何一个，完成实验并书写实验报告。5、 实验步骤1） 熟悉Prolog语言的基本规范；2） 熟悉Prolog的基本数据结构3） 熟悉Prolog解决问题的思路（链表和递归）。6、 参考程序/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - N Queens problem FileName: nqueen.pl To run at command line like, swipl -quiet -c nqueen.pl To compile it into an exe file, run like swipl -goal=goal -o nqueen.exe -c nqueen.pl revised by Yisong Wang (ys_) from /wiki/N-queens_problem#Prolog via adding some comments. -*/nqueens(N,Queens) :-range(1,N,Qs), % Qs=1,2,.,Npermutation(Qs, Queens),safe(Queens).range(N,N,N).range(M,N,M|Ns):- M N, M1 is M+1, range(M1,N,Ns).safe().% The Queen does not attack the others, and% the others are safesafe(Queen|Others) :-noattack(Queen,Others,1),safe(Others).noattack(_,_).% Y does not attack any qeeen in Y1|Ylistnoattack(Y,Y1|Ylist,Xdist) :-Y1-Y=Xdist,Y-Y1=Xdist,Dist1 is Xdist + 1,noattack(Y,Ylist,Dist1).goal :-read(N),nqueens(N,Qs),writeln(Qs),statistics,halt.:- goal.*以下两个参考程序来自wiki百科。更多的问题参考Bartak的主页关于Prolog的介绍。1）快速排序范例（对list作排序）：/* quicksort2.pl 原始來源：/wiki/Prolog */* quicksort()中的第二個引數帶有排序好的結果*/* 僅為示範，若為gprolog使用者則用內建sort等較佳 */* 在gprolog下之編譯例：gplc -min-size quicksort2.pl*/* 執行 quicksort2 後會出現排序結果 2,9,18,18,25,33,66,77 */ q:- L=33,18,2,77,66,18,9,25, last(P,_), (quicksort(L,P,_), write(P), nl). /* 加入last/2會在印P時沒複合項 */ partition(, _, , ). /* 此行表空集亦視為分割（分割成空集與空集）*/partition(X|Xs, Pivot, Smalls, Bigs) :- /* 原list分成Smalls與Bigs; 此rule保證Smalls集=Pivot */ ( X Smalls = X|Rest, partition(Xs, Pivot, Rest, Bigs) ; Bigs = X|Rest, partition(Xs, Pivot, Smalls, Rest) ). quicksort() - . /* 表empty list視為排序好的list */quicksort(X|Xs) - /* 此行相當於quicksort(X|Xs,Start,End) :- 此rule讓Start為sorted list */ partition(Xs, X, Smaller, Bigger) , /* 由上行最左端元素為 Pivot */ quicksort(Smaller), X, quicksort(Bigger). /* 此行相當於 quicksort(Smaller,Start,A), A=X|B, 注意首字母大寫者皆視為變數(list) quicksort(Bigger,B,End). */:- initialization(q). /* 啟動q處goals */2）下面简洁的排序范例可以体会到为什么AI领域喜用Prolog：/* sortcsj.pl 原始參考：Computer Science J. Glenn Brookshear */* sortcsj()中的第二個引數帶有排序好的結果*/* 僅為示範，若為gprolog使用者則用內建sort等較佳 */* 在gprolog下之編譯例：gplc -min-size sortcsj.pl*/* 執行 sortcsj 後會出現排序結果 2,9,18,18,25,33,66,77 */ q:- L=33,18,2,77,18,66,9,25, (sortcsj(L,P), write(P), nl). sortcsj(L,S) :- permutation(L,S), ordered(S). /* L為原list, S為排序好的list, 此為permutation關係(built-in) */ ordered(). /* 表empty list視為排序好的list */ordered(_|). /* 只有一元素之list視為排序好的list */ordered(A|B|T) :- A = B, ordered(B|T). /* 此rule約束所謂的排序好是指前項元素小於或等於後一項元素 */ :- initialization(q). /* 啟動q處goals */实验四ASP描述性问题求解1、 实验目的通过学习Answer Set Programming（ASP）的基本概念，了解ASP的描述性问题求解基本方法；通过具体的ASP编程实验，体验基于逻辑的描述性问题求解的基本思想。2、 实验原理回答集编程是语法上类似传统逻辑编程而语义上密切于非单调逻辑的一种声明式编程。在传统逻辑编程和回答集编程之间的主要区别是如何表示否定为失败。在传统逻辑编程中，否定为失败指示推导失败；在回答集编程中，它指示一个文字的一致性。 回答集编程由规则的集合构成，每个规则由一个头部和一个后部构成:规则的头部和后部二者都是文字的集合，每个文字都是可能被否定的原子。与传统逻辑程序相反，原子都是命题而不是一阶的，并且可以使用两种形式的否定去否定它们: 经典否定(指示为 )和否定为失败(指示为 )。文字要么是原子要么是(使用经典否定)否定的原子。与 Prolog 相反，回答集程序的语义不依赖于规则的求值和原子在每个规则中的特定次序。 检查一个程序的回答集的存在性的复杂性，和检查一个程序是否蕴涵一个文字复杂性，范围是从 P 到多项式层次的第二级，依赖于一个程序可以满足也可以不满足的一组条件(就是说分层、头部中的析取)。3、 实验内容1） 图的着色：问题与Prolog情形一致。2） N皇后问题：问题与Prolog情形一致。3） 汉密尔顿回路问题：给定一图，输出该图的一条汉密尔顿回路（如果有的话）。4） 学校课表排课：给定学校课表安排的约束（教室、教师、课程），输出一种排课方案（参考The thirdInternational Timetabling Competition 2011以及张青伟,赵岭忠.回答集程序设计在TTP求解中的应用）。4、 实验描述及要求选择上述实验内容中的任何一个，编写ASP程序并用clasp计算其回答集，输出试验结果；书写实验报告。5、 实验步骤1) 了解ASP的基本语法语义2) 了解ASP语言lparse/gringo3) 熟悉ASP规则的问题求解方法4) 编写ASP程序并运行验证。6、 参考程序*更多的测试用例参考Answer Set Programming Competition 2011% To run like this, lparse color.lp p10 | clasp%-% file name: color.lpc(g;r;b).1 clr(X,I) : c(I) 1 :- v(X).:- clr(X,I), clr(Y,I), e(X,Y), c(I).#hide.#show clr(X,Y).% -% Petersen graph % file name: p10e(X,Y) :- e(Y,X), v(X;Y). v(1.10). e(1,2).e(1,5).e(1,6).e(2,7).e(2,3).e(3,8).e(3,4).e(4,9).e(4,5).e(5,10).e(6,8).e(6,9).e(7,9).e(7,10).e(8,10).参考文献：、 Artificial Intelligence: A New Synthesis, by Nils J. Nilsson. San Francisco, CA: Morgan Kaufmann Publishers, Inc. 1998.、 Russell and Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, 1995. 、 人工智能郑扣根庄越挺译机械工业出版社、 Sat Live. /、 The Satisfiability Library. http:/www.cs.ubc.ca/hoos/SATLIB/index-ub