hw1.typ

== HW 1
Due: 2024.03.17

#let ans(it) = [
  #pad(1em)[
    #text(fill: blue)[
      #it
    ]
  ]
]

=== Question 3.7

3.7 给出下列问题的初始状态、目标测试、后继函数和耗散函数. 选择精确得足以实现的形式化.

+ 只用四种颜色对平面地图染色, 要求每两个相邻的地区不能染成相同的颜色.
+ 一间屋子里有一只 3 英尺高的猴子, 屋子的房顶上挂着一串香蕉, 离地面 8 英尺. 屋子里有两个可叠放起来、可移动、可攀登的 3 英尺高的箱子. 猴子很想得到香蕉.
+ 有一个程序, 当送入一个特定文件的输入记录时会输出“不合法的输入记录”. 已知每个记录的处理独立于其它记录. 要求找出哪个记录不合法.
+ 有三个水壶, 容量分别为 12 加仑、8 加仑和 3 加仑, 还有一个水龙头. 可以把壶装满或者倒空, 从一个壶倒进另一个壶或者倒在地上. 要求量出刚好 1 加仑水.

#ans[
  +
    - Initial State: 所有区域未染色
    - Goal Test: 所有区域都染色
    - Successor Function: 选择一个未染色的区域, 为其染上一种颜色
    - Cost Function: 涂色的次数
  +
    - Initial State: 猴子在屋子的地面, 箱子在屋子的地面, 香蕉距离地面 8 英尺
    - Goal Test: 猴子站在箱子上, 可以够到香蕉
    - Successor Function: 猴子搬动、放下箱子、爬上箱子、爬下箱子、拿起香蕉
    - Cost Function: 猴子总用时
  +
    - Initial State: 一个输入记录
    - Goal Test: 输入记录合法
    - Successor Function: 修改输入记录的某一部分
    - Cost Function: 修改的次数
  +
    - Initial State: 三个水壶都是空的
    - Goal Test: 一个水壶里有 1 加仑水
    - Successor Function: 装满水壶、倒空水壶、从一个壶倒进另一个壶
    - Cost Function: 倒水的次数

]

=== Question 3.9

3.9 传教士和野人问题通常描述如下：三个传教士和三个野人在河的一边, 还有一条能载一个人或者两个人的船. 找到一个办法让所有的人都渡到河的另一岸, 要求在任何地方野人数都不能多于传教士的人数 (可以只有野人没有传教士). 这个问题在 AI 领域中很著名, 因为它是第一篇从分析的观点探讨问题形式化的论文的主题（Amarel, 1968）

+ 精确地形式化该问题, 只描述确保该问题有解所必需的特性. 画出该问题的完全状态空间图.
+ 用一个合适的搜索算法实现和最优地求解该问题. 检查重复状态是个好主意吗？
+ 这个问题的状态空间如此简单, 你认为为什么人们求解它却很困难？

#ans[
  +
    - 状态：$(a,b,c)$, $a$:传教士在此岸的人数, $b$:野人在此岸的人数, $c$:船是否在此岸 (0/1)
    - Initial State: $(3,3,1)$
    - Goal Test: $(0,0,0)$
    - Successor Function:
      $
        (x,y,1) -> cases((x-1,y,0), (x,y-1,0), (x-1,y-1,0), (x-2,y,0), (x,y-2,0))
        \
        (x,y,0) -> cases((x+1,y,1), (x,y+1,1), (x+1,y+1,1), (x+2,y,1), (x,y+2,1))
      $
      同时所有$(x,y,c),(x',y',z')$满足$0<=x<=3, 0<=y<=3$, 并且：
      $
        (x=0 or x>=y) and (x=3 or x<=y)
      $
    - Cost Function: 操作次数
  + 使用 BFS 对状态进行搜索, 维护一个 $3 times 1$ 的数组记录已经访问过的状态：

    $
      (3,3,1) -> (3,1,0) -> (3,2,1) -> (3,0,0) -> (3,1,1) -> (1,1,0)\ -> (2,2,1) -> (0,2,0) -> (0,3,1) -> (0,1,0) -> (
        1,1,1
      ) -> (0,0,0)
    $

    问题中限制很多, 可以不考虑重复状态 (全部枚举即可). 如果问题中 $3 -> 100$, 检查重复状态是个好主意.
  + 虽然每一步的限制都足够多而且空间足够简单, 但图的深度很大, 每一步所需要做的判断过于复杂.

]