1、人工智能问题求解编程 实验一 人工智能问题求解编程（深度优先搜索方法）实验内容：1.学习深度优先搜索方法（第一局部内容）；2.学习C语言编程风格； 3.自己将该程序调试一下，能正确计算出结论。 4.画出总体程序框图和各段程序的框图。第一局部：知识背景 人工智能(Artificial Intelligence，AI)由相互有差异但都令人感兴趣的几个方面组成，其中多数AJ应用的根底是问题求解(problem solving)。所有问题根本分为两类。第一类通过某种确保成功的决定过程(即计算过程)解决。解决第一类问题的方法常常易于转换成计算机能执行的算法。然而，没有几个现实问题是适合计算解决方案的。事
2、实上，许多问题(即第二类问题)是非计算性的。解决第二类问题的方法是搜索，即人工智能关心的问题求解方法。 人工智能追求的目标之一，是建立一个通用问题求解器。通用问题求解器(general problem solver)是一种程序，其中没有特定领域的专门知识，但又能够产生对各种问题的解。本章将指出这种目标既有吸引力又难于到达的原因。 早期AI研究的主要目的是研究优秀的搜索方法。其原因有二：需要和愿望。把AI技术应用到现实问题的最大障碍就是多数情况下的规模和复杂性，因此我们需要高效率的搜索技术。此外，研究人员一直认为搜索是问题求解的关键，而问题求解又是智能的关键成分。1.1 表示和术语 假设某人把自
3、己的车钥匙遗忘在住所中，希望找到这把钥匙。住所的平面布局如以下图所示。该人站在前门外(标X处)。开始搜索时，先查看起居室，然后穿过走廊到达第二间卧室，回到走廊去主卧室。由于未发现钥匙，返回起居室后再到厨房寻找，终于找到遗失的车钥匙。上述情景可以由一幅图方便地描述出来，如图25l所示。 搜索问题的事实用图(graph)表达出来是很重要的，因为图提供形象描述各种搜索原理的手段。同时，用图表示问题允许AI研究者利用图论(graph theory)的各种定理(这些定理超出本书的范围)。但我们应学会以下的定义： 节点(Node) 一个离散点，可能是搜索目标 目标(Goal) 搜索对象的节点 终端节点(T
4、erminal node) 终结一条路径的节点 搜索空间(Search space) 所有节点的集合 探试式(Heuristics) 关于特定节点比其他节点是否更优的信息 解路径(Solution path) 到达解节点路途上经过的节点构成的有向分图 在遗忘钥匙的例子里，住所的每间房屋是节点，整个住所是解空间，目标是厨房，解路径如图251所示。各卧室和浴室是终端节点，因为不能由此到达其他房间。求解中未用探试式，探试的应用在本章稍后内容中讨论。12 组合爆炸 至此，一切都显得十分简单：开始搜索，继续搜索，到达目标。在遗忘钥匙这类特别简单的问题中，情况确 实如此。然而，在计算机求解的多数问题中，情
5、况困难得多。总之，计算机求解的问题都有很大的搜索空间，由于空间中节点数目很大，到达目标的解路径也变得很多。问题的症结在于，增加一个节点后，解路径增加得更多。换言之，到达目标的道路数比节点数增长得快。 我们以排列3个对象A、B和C为例说明上述观点。6种可能的排列是： A B C A C B B C A B A C C B A C A B直观验证和排列组合数学(combinatorics)定理都指出，3个对象共有6种排列。根据排列组合数学定理，N个对象的排列总数等于N!(N的阶乘)。N阶乘指Nx(N-1)xx2x1，因此3个对象的排列种数是3!(排列组合数等于6)，4个对象是4!(24)，5个对象
6、是5!(120)，6个对象是6!(720)。依次类推，1000个对象的排列种数简直是一个天文数字。 图25-2中所示的曲线趋势形象地表示了人工智能研究者称为组合爆炸(combinatoric explosion)的现象。对象总数逼近数百时，很快就不可能再研究(甚至枚举)各种组合了。换言之，搜索空间中每增加一个节点，搜索路径增加的数目远大于一倍。因此，节点增到一定数目时，问题的规模就超出我们的能力了。因为可能解的数目随节点数增长太快，除特别简单的情况外，一般问题都不适于穷尽搜索(exhaustiv esearch)。穷尽搜索方法研究所有节点，是一种蛮力(brute force)技术。这种方法总是
7、正确的，但因为占用的计算时间和资源太多，般并不实用。出于这种考虑，人工智能研究人员开展了其他搜索技术。 1.3 搜索技术在寻找可能解的方法中，以下4种是最根本的： 深度优先搜索 宽度优先搜索 爬山搜索 最小代价搜索本章将分别研究上列各种方法。1.4评价搜索技术 对搜索技术性能的评价是相当复杂的，事实上它已在人工智能研究中占据一大局部工作。然而，本章把目标局限于以下两个重要方面： 寻找解的速度； 解的质量。 在假设干类问题中，只要找到任一解就可以了，因为这样做所花费的代价最低。对这类问题，寻找解的速度是最重要的。但在其他情况下，要求的是质量，即解必须优(good)，甚至应该最优(optimal)
8、。 搜索的速度由解路径的长度和遍历的节点数决定。因为从死节点上回朔(backtracking)本质上是浪费的，所以我们希望搜索中尽量少回朔。 求最优解和求优解是不同的：求最优解一般导致穷尽搜索，因为此外不能确保解是最优的；求优解指寻找满足一组约束的某一个解，并不在乎是否还有满足约束的更好的解。 读者将会看到，本章描述的搜索技术都在某种条件下互有短长，因此难说一种技术总是优于其他技术。然而，某些技术在平均情况下较好的概率可能会更大。此外，定义问题的方法有时也有助于恰中选择搜索方法。第二局部：求解问题背景 假设某旅游代理面对一个挑剔的客户，该客户要预订一张XYZ 航空公司自纽约到洛杉矶的飞机票。代
9、理商告诉客户，XYZ没有两地间的直飞航线。客人坚持，非要乘坐 XYZ公司的班机不可。XYZ航班如下表所示。 航 班 里 程 航 班 里 程 纽约到芝加哥 1000英里 多伦多到芝加哥 500英里 芝加哥到丹佛 1000英里 丹佛到欧巴纳 1000英里 纽约到多伦多 800英里 丹佛到休斯敦 1500英里 纽约到丹佛 1900英里 休斯敦到洛杉矶 1500英里 多伦多到卡尔加里 1500英里 丹佛到洛杉矶 1000英里 多伦多到洛杉矶 1800英里 通过接续航班，旅游代理很快为客人办理了从纽约到洛杉矶的机票。 本实验任务是学习编写好的C语言程序，读懂完成搜索任务的程序。 25 .5 用图表示问题
10、 XYZ公司航班表中的信息可以变换成如图25-3中所示的有向图。有向图(directed graph)中的节点用有向线连接，有向线的箭头指出移动方向，不允许逆向穿过。 为便于理解，图25-3重画成图25-4，仅抽出有用的拓扑信息。本章讨论将以图25-4为基准。图25-4中，目标洛杉矶用环线标注；为简化结构，有的城市屡次出现。至此，我们可以开始构造搜索程序了。第三局部：问题求解算法 （具体实验编程内容）学习目的：分析C语言程序写作方法，读懂完成搜索任务的程序； 学习构造搜索程序。 要求：根据本节C语言程序，在实验报告纸上画出深度优先搜索算法的总体程序框图和其中各段程序的程序框图。 25.6 深度
11、优先搜索 深度优先搜索按ABDBEBACF序列遍历该树，就是对树的中序(inorder)遍历。搜索路径向左下推进，直至找到目标或到达终端节点。如到达终端节点，路径退回一级(回朔)，然后向右下推进一级，再向左下深入，直到发现目标或到达终端节点。重复该过程，直至发现目标节点或检查完解空间的最后节点。 显然，深度优先方法肯定能够找到目标，因为最劣情况下，搜索退化成穷尽搜索。本例中，如果G为目标而F不是目标，搜索将成为穷尽方式。编制搜索纽约至洛杉矶航行路程的C程序时，需要一个放XYZ航班信息的数据库。其中每个记录必须含起止城市、二者间的距离和一个帮助回朔的标志。以下结构用于放数据记录。 #define
12、 MAX 100 x structure of the flight databasex struct FL charfrom20； char to20； int distance； char skip；xused in backtracking x； struct FL flightMAX；xarray of db structuresx int f_Pos0； xnumber of entries in flight db x int find_Pos0； xindex for searching flight dbx 函数assert_flight()把每个记录放人数据库中，setup(
13、)对航班信息初始化。全局变量f_pos放数据库末记录的下标。这些例程如下所示： Void Setup(void) assert_r_flight(NewYork，Chicago，1000)； ssert_flight(Chicago，Denver，1000)； assert_flight(NewYork，Toronto,800)； assert_flight(NewYork，Denver，1900)； assert_flight(Toronto，Calgary，1500)； assert_flight(Toronto，IdsAngeles，1800)； assert_flight(Toront
14、o，Chicago，1800)；assert_flight(Denver，Urbana，1000)； assert_flight(Denver，Houston，1500)； assert_flight(Houston，LosAngeles，1500)； assert_flight(Denver，10sAngeles，lOOO)； xPutfacts into the databasex void assert_flight(charxfrom，charxto，int dist) if(f_posMAX) strcpy(flightf_posfrom，from)； strcpy(flightf_posto，to)； flightf_posdistancedist； flightf_posskip=0； f_pos+； else printf(Flight databasefulln)； 为了与人工智能的精神一致，我们把数据库看做事实(facts)的集合，即要开发的程序将通过其中的事实求解问题。人工智能研究者称这种数据库为知识库(knowledge base)，本书交替使用这两个术语于。结束。祝同学们学习愉快！ 主讲教师：汤军7