hw3.typ

== HW3
Due 2024.03.31

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

=== Question 6.5

6.5 分别用带有前向检验、MRV 和最少约束值启发式的回溯算法手工求解图 6.2 中的密码算术问题.

#ans[
  首先考虑 1-相容：

  #align(center)[
    #table(
      stroke: blue,
      columns: (auto, auto, auto, auto, auto, auto, auto, auto, auto),
      align: center,
      [$C_1$], [$C_2$], [$C_3$], [$F$], [$T$], [$U$], [$W$], [$R$], [$O$],
      [$0, 1$], [$0, 1$], [$0, 1$], [$1-9$], [$1-9$], [$0-9$], [$0-9$], [$0-9$], [$0-9$],
    )
  ]

  所有约束：

  $
    2O &= R + 10 dot C_3 \
    2W + C_3 &= U + 10 dot C_2 \
    2T + C_2 &= O + 10 dot C_1 \
    C_1 &= F \
    "ALLDIFF" & {F, T, U, W, R, O}
  $

  按照 $X_i$ 进行整理：

  $
    C_1&: <C_1, F>, <C_1, C_2, T, O> \
    C_2&: <C_2, C_3, U, W>, <C_1, C_2, T, O> \
    C_3&: <C_3, R, O>, <C_2, C_3, U, W> \
    F&: <C_1, F> \
    T&: <C_1, C_2, T, O> \
    U&: <C_2, C_3, U, W> \
    W&: <C_2, C_3, U, W> \
    R&: <C_3, R, O> \
    O&: <C_3, R, O>, <C_1, C_2, T, O> \
  $

  #align(center)[
    #table(
      stroke: blue,
      columns: (auto, auto, auto, auto, auto, auto, auto, auto, auto, auto),
      align: center,
      [], [$C_1$], [$C_2$], [$C_3$], [$F$], [$T$], [$U$], [$W$], [$R$], [$O$],
      [$<C_1, F>$], [$1$], [$0, 1$], [$0, 1$], [$1$], [$1-9$], [$0-9$], [$0-9$], [$0-9$], [$0-9$],
      [$<C_3, R, O> and "ALLDIFF"$], [$1$], [$0, 1$], [$0, 1$], [$1$], [$1-9$], [$0-9$], [$0-9$], [$0-9$], [$1-9$],
      [$"ALLDIFF"$], [$1$], [$0, 1$], [$0, 1$], [$1$], [$2-9$], [$0, 2-9$], [$0, 2-9$], [$0, 2-9$], [$2-9$],
      [$<C_3, R, O>$], [$1$], [$0, 1$], [$0, 1$], [$1$], [$2-9$], [$0, 2-9$], [$0, 2-9$], [$0, 2, 4, 6, 8$], [$2-9$],
      [$<C_1, C_2, T, O>$],
      [$1$],
      [$0, 1$],
      [$0, 1$],
      [$1$],
      [$5-9$],
      [$0, 2-9$],
      [$0, 2-9$],
      [$0, 2, 4, 6, 8$],
      [$2-9$],

      [$"SET:" C_2 = 0$], [$1$], [$0$], [$0, 1$], [$1$], [$5-9$], [$0, 2-9$], [$0, 2-9$], [$0, 2, 4, 6, 8$], [$2-9$],
      [$<C_2, C_3, U, W>$],
      [$1$],
      [$0$],
      [$0, 1$],
      [$1$],
      [$5-9$],
      [$0, 2-9$],
      [$0, 2, 3, 4$],
      [$0, 2, 4, 6, 8$],
      [$2-9$],

      [$<C_1, C_2, T, O>$],
      [$1$],
      [$0$],
      [$0, 1$],
      [$1$],
      [$5-9$],
      [$0, 2-9$],
      [$0, 2, 3, 4$],
      [$0, 2, 4, 6, 8$],
      [$2, 4, 6, 8$],

      [$"SET:" C_3 = 0$],
      [$1$],
      [$0$],
      [$0$],
      [$1$],
      [$5-9$],
      [$0, 2-9$],
      [$0, 2, 3, 4$],
      [$0, 2, 4, 6, 8$],
      [$2, 4, 6, 8$],

      [$<C_3, R, O>$], [$1$], [$0$], [$0$], [$1$], [$5-9$], [$0, 2-9$], [$0, 2, 3, 4$], [$0, 4, 8$], [$2, 4$],
      [$<C_1, C_2, T, O>$], [$1$], [$0$], [$0$], [$1$], [$5, 6, 7$], [$0, 2-9$], [$0, 2, 3, 4$], [$0, 4, 8$], [$2, 4$],
      [$<C_2, C_3, U, W>$],
      [$1$],
      [$0$],
      [$0$],
      [$1$],
      [$5, 6, 7$],
      [$0, 4, 6, 8$],
      [$0, 2, 3, 4$],
      [$0, 4, 8$],
      [$2, 4$],

      [$"SET:" O=4$], [$1$], [$0$], [$0$], [$1$], [$5, 6, 7$], [$0, 4, 6, 8$], [$0, 2, 3, 4$], [$0, 4, 8$], [$4$],
      [$"ALLDIFF"$], [$1$], [$0$], [$0$], [$1$], [$5, 6, 7$], [$0, 6, 8$], [$0, 2, 3$], [$0, 8$], [$4$],
      [$<C_3, R, O>$], [$1$], [$0$], [$0$], [$1$], [$5, 6, 7$], [$0, 6, 8$], [$0, 2, 3$], [$8$], [$4$],
      [$"ALLDIFF"$], [$1$], [$0$], [$0$], [$1$], [$5, 6, 7$], [$0, 6$], [$0, 2, 3$], [$8$], [$4$],
      [$<C_2, C_3, U, W> and "ALLDIFF"$], [$1$], [$0$], [$0$], [$1$], [$5, 6, 7$], [$6$], [$3$], [$8$], [$4$],
      [$<C_1, C_2, T, O>$], [$1$], [$0$], [$0$], [$1$], [$7$], [$6$], [$3$], [$8$], [$4$],
    )
  ]

  Solution:

  $
    &quad &quad 7 &quad 3 &quad 4 \
    &quad + &quad 7 &quad 3 &quad 4 \
    = &quad 1 &quad 4 &quad 6 &quad 8
  $
]

=== Question 6.11

6.11 用 AC-3 算法说明弧相容对图 6.1 中问题能够检测出部分赋值 $"WA"="GREEN", "V" = "RED"$, 的不相容.

#ans[
  #table(
    columns: (auto, auto, auto, auto, auto, auto, auto, auto),
    stroke: blue,
    align: center,
    [], [WA], [NT], [Q], [NSW], [V], [SA], [T],
    [], [G], [R G B], [R G B], [R G B], [R], [R G B], [R G B],
    [WA, SA], [G], [R G B], [R G B], [R G B], [R], [R B], [R G B],
    [WA, NT], [G], [R B], [R G B], [R G B], [R], [R B], [R G B],
    [V, SA], [G], [R B], [R G B], [R G B], [R], [B], [R G B],
    [V, NSW], [G], [R B], [R G B], [G B], [R], [B], [R G B],
    [SA, NSW], [G], [R B], [R G B], [G], [R], [B], [R G B],
    [SA, Q], [G], [R B], [R G], [G], [R], [B], [R G B],
    [SA, NT], [G], [R], [R G], [G], [R], [B], [R G B],
    [NT, Q], [G], [R], [G], [G], [R], [B], [R G B],
  )

  注意到此时 $Q="NSB"="GREEN"$, 破坏约束, AC-3 算法可以检测出这种不相容.

]

=== Question 6.12

6.12 用 AC-3 算法求解树结构 CSP 在最坏情况下的复杂度是多少？

#ans[
  树结构中每个弧最多会被检查一次, 因此 AC-3 最坏情况下复杂度为 $O(E D)$, 其中 $E$ 为弧的数量, $D$ 为定义域的大小.

  // 对应的算法考虑如下：

  // - 对于每个节点$X_i$, 当前的取值范围 $D_0$
  // - 遍历子节点 $X_j$, 记录 $<X_i, X_j>$ 允许的 $X_i$ 的取值范围 $D_(i,j)$
  // - 取所有 $D_(i j)$ 的交集 $D_1$
  // - 获得 $D_i = D_0 sect D_1$ 作为 $X_i$ 新的取值范围
  // - 遍历子节点 $X_j$, 记录 $<X_i, X_j>$ 允许的 $X_j$ 的取值范围 $D_(j)$, 记录到子节点上, 向下递归

  // #box[
  // 对应伪代码：(Python-style)
  // ```python
  // class Node:
  //   D: set[Value]
  //   father: Node
  //   children: [Node]

  // Constarint = [(Node, Node): [Value, Value]]

  // def AC3_Tree(cur: Node, C: Constarint) -> bool:
  //   D0 = cur.D
  //   Ds = [(v[0] for v in C[(cur, child)]) for child in children]
  //   D1 = intersect(Ds)
  //   cur.D = intersect(D0, D1)
  //   if len(cur.D) == 0:
  //     return False

  //   for child in children:
  //     child.D = [v[1] for v in C[(cur, child)] if v[0] in cur.D]
  //     if not AC3_Tree(child, C):
  //       return False

  //   return True

  // AC3_Tree(root)
  // ```
  // ]

]