人工智能(第三版)第二章 习题

讨论题:

  1. 搜索为什么是 AI 系统的重要组成部分?

   搜索可以获取目标信息、有效信息

  1. 状态空间图是什么?

   它是对问题的一种表示方法,它有很多条路径,某个具体问题的解将对应状态空间图中的一条路径

  1. 描述生成-测试范式。

   先给出所有可能的解,然后再筛选出所有符合条件的解 

  1. 生成器有什么属性?

   完备的、非冗余、知情的

  1. 回溯法如何对完全枚举法进行改进?

   完全枚举法会查看所有可能的情况,即使当前步骤不能得到解,它也会继续往后搜索;而回溯法在当前步骤无法不能得到解时,会回溯到前一步, 寻找能够摆放当前步骤的位置,若找不到,则撤销前一步,以此往复。

  1. 用一两句话描述贪心算法。

   贪心算法会将一个问题拆解成好几个步骤,然后找出当前步骤的最优解

  1. 陈述旅行商问题

   给定n个顶点的加权图(即每条边上带有开销值),求从某个顶点Vi出发经过加权图中的所有顶点(每个顶点只经过一次),然后返回到Vi的最短路径

  1. 简述 3 种盲目搜索算法。

   深度优先搜索(DFS): 从起始顶点开始,沿着一条路径一直向下访问直到末端,然后回溯并继续探索下一条路径。

   广度优先搜索(BFS):从起始顶点开始,首先访问起始顶点的所有相邻顶点,然后依次访问这些相邻顶点的相邻顶点,以此类推,直到所有顶点都被访问过。

   迭代加深的深度优先搜索(DFS-ID):它会先以较浅的深度进行深度优先搜索,在搜索过程中若未找到目标,则逐渐增加深度限制,并重复进行深度优先搜索,直至找到目标为止

  1. 在何种意义上,盲目搜索算法是盲目的?

   没有确定的目标,搜索方法是随机的抽取

  1. 按照完备性、最优性和时空复杂性,比较本章描述的 3 种盲目搜索算法。

完备性:

      ·深度优先搜索:在所有路径都不是很深的情况下,DFS是完备;在某几条路径很长的情况下,DFS不是完备的

      ·广度优先搜索:如果搜索空间的分支因子是有限的,那么 BFS 是完备的

      ·迭代加深的深度优先搜索:如果给定的搜索空间是有限的,并且DFS-ID算法能够遍历所有可能的输入样本,那么它具有完备性。但是,如果搜索空间无限大或算法无法遍历所有输入样本,那么DFS-ID可能无法解决所有情况,从而导致不完备性。

  1. 在什么情况下,DFS 比 BFS 好?

    树很深;分支因子不太大;并且解出现在树中的位置相对较深

  1. 在什么情况下,BFS 比 DFS 好?

    搜索树的分支因子不太大(一个适度的 b 值),当整棵树的分支因子实际上很大时, BFS 会因为有过多的路径需要探索而不堪重负;解出现在树中的位置在合理的深度(一个适度的 d 值);所有路径都不是特别深

  1. 在什么意义上,可以说 DFS-ID 是 BFS 和 DFS 的折中?

在时间复杂度上,DFS-ID比BFS稍好;在空间复杂度上,它与DFS相同

练习题:

  1. 在只允许称重 3 次的情况下,求解 12 枚硬币的假币问题。回忆一下,天平可以返回以下3种结果之一:相等、左侧轻或左侧重。
  2. 在只称重两次的情况下,求解微型假币问题或证明这是不可能的。

   只称重两次只有在特定情况下能够求解

   当第一组和第二组的重量相同时,说明假币在第三组中,拿出第一组中的一枚硬币与第三组中的其中一枚比较,若重量相等则另一枚是假币,若重量不相等则这枚是假币 

  1. 非确定性搜索(nondeterministic search)是本章未讨论的一种盲目搜索方法。在这种搜索中,刚刚扩展的子节点以随机顺序放在开放表中。请判断非确定性搜索是否完备以及是否最优。

   不是完备的。将扩展的子节点以随机顺序放在开放表中,无法保证在有限的步骤中找到解。

   不是最优的。由于节点扩展顺序是随机的,无法保证在最少的步骤中找到解。

  1. n皇后问题的另一个生成器如下:第一个皇后放在第一行,第二个皇后不放在受第一个 皇后攻击的任何方格中。在状态 i,将第 i 列的皇后放在未受前面(i−1)个皇后攻击的方格中, 如图 2.34 所示。 (a)使用这个生成器求解 4 皇后问题。 (b)证明这个生成器比文中使用的两个生成器拥有更多的信息。 (c)画出搜索第一个解时在搜索树中展开的部分。
  1. :解是[1,3,0,2]和[2,0,3,1]
  2. :原本的生成器会将所有的情况都遍历一遍,而这个生成器会将明显会导致冲突的情况排除掉,缩小范围,降低运行成本
  1. 思考下列 4 皇后问题的生成器:从 i=1 到 i=4,随机地分配皇后 i 到某一行。这个生成器完备吗?非冗余吗?解释你的答案。

   不完备也不是非冗余的。首先,这个生成器是随机地分配皇后的位置,这无法保证皇后遍历过每一个位置,造成不完备 ;其次,这个随机分配有可能分配到同一个地方,产生同一个解,造成冗余

  1. 如果一个数等于其因数(不包括这个数本身)的和,则称这个数是完美数。例如,6 是 完美数,因为 6 = 1 + 2 + 3,其中整数 1、2 和 3 都是 6 的因数。给出你所能想到的拥有最多信息的生成器,使用这个生成器,可以找到 1 和 100 之间(包括 1 和 100 在内)的所有完美数。

def factor_sum(n):

    return sum(f for f in range(1, n) if n % f == 0)

perfect_numbers = [num for num in range(1, 101) if factor_sum(num) == num]

print(perfect_numbers)

  1. 使用 Dijkstra 算法找到从源顶点 V0到所有其他顶点的最短路径,如图 2.35 所示。 图 2.34 4 皇后问题的生成器 图 2.35 使用 Dijkstra 算法的标记图

节点

离出发点的距离

前面点

0

0

1

4

0

2

7

1

3

6

1

4

7

3

  1. 创建拼图(如15拼图)的表示以适合检查重复状态。

   建立一个二维数组,在相应的位置标上号,若对应的是空位置,则标上0   

  1. 使用广度优先搜索求解传教士与野人问题。  
  2. 在河的西岸,一个农夫带着一匹狼、一只山羊和一篮子卷心菜(参见图 2.0)。河上有一艘船,可以装下农夫以及狼、山羊、卷心菜三者中的一个。如果留下狼与羊单独在一起,那么狼会吃掉羊。如果留下羊与卷心菜单独在一起,那么羊会吃掉卷心菜。现在的目标是将它们都安全地转移到河的对岸。请分别使用以下搜索算法解决上述问题:(a)深度优先搜索;(b)广度优先搜索
  3. 深度优先搜索:先把羊送过去,以这个为起点,然后继续搜索下去
  4. 广度优先搜索:将把狼、山羊、卷心菜这三个东西都送过去的情况都遍历,这一层只有运送山羊的情况成功,接下来就如DFS一样遍历下去
  1. 首先使用 BFS,然后使用 DFS,从图 2.36(a)和图 2.36(b)的起始节点 S 开始,最终到达目标节点 G。其中每一步都按照字母表顺序浏览节点。
  2. 标记图 2.37 所示的迷宫。
  3. 对于图 2.37 所示的迷宫,先使用 BFS,再使用 DFS,从起点处开始走到目标处。 图 2.36 使用 BFS 和 DFS 到达目标节点 图 2.37 迷宫
  4. 我们已经确定,12枚硬币的假币问题需要对3组硬币进行称重才能确定假币。那么在 15 枚硬币中,需要称重多少次才可以确定假币?20 枚硬币时又会怎么样?请开发出一种算法来 证明自己的结论。 提示:可以先考虑 2~5 枚硬币所需的基本称量次数,从而开发出事实知识库,自底向上得 到这个问题的解。

15枚:4次

20枚:4次

先将所有的硬币等分成相同的个数,进行比较,然后再等分,直到找到假币为止     

  1. 我们讨论了传教士与野人问题。假定“移动”或“转移”是强行(受迫)的,找出这个问题的一个解。确定问题解决状态的“子目标状态”,我们必须获得这个状态,才能解决这个问题    

版权声明:本文为博主作者:aaa114514__原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/aaa114514__/article/details/135862334

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
社会演员多的头像社会演员多普通用户
上一篇 2024年2月19日
下一篇 2024年2月19日

相关推荐

此站出售,如需请站内私信或者邮箱!