T1 状态空间

(1) 结合逆序数奇偶性理论，判断以下初始与目标状态组合是否有解，并给出判断依据。

• 如果 N 是奇数（如本题的 3×3 棋盘），那么当且仅当初始状态和目标状态的逆序数奇偶性相同时，问题有解。

• 如果 N 是偶数，则还需要考虑空格（0）所在行的奇偶性。

状态组合 ①：初始 "157042836" → 目标 "236507481"

• 初始状态 "157042836" 棋盘表示：
展开为序列 (忽略0): 1,5,7,4,2,8,3,6 逆序数计算：
• 1: 0
• 5: (对于4, 2, 3) → 3
• 7: (对于4, 2, 3, 6) → 4
• 4: (对于2, 3) → 2
• 2: 0
• 8: (对于3, 6) → 2
• 3: 0
• 6: 0 初始状态总逆序数 = 0+3+4+2+0+2+0+0=11 (奇数)

• 目标状态 "236507481" 棋盘表示：
展开为序列 (忽略0): 2,3,6,5,7,4,8,1 逆序数计算：
• 2: (对于1) → 1
• 3: (对于1) → 1
• 6: (对于5, 4, 1) → 3
• 5: (对于4, 1) → 2
• 7: (对于4, 1) → 2
• 4: (对于1) → 1
• 8: (对于1) → 1
• 1: 0 目标状态总逆序数 = 1+1+3+2+2+1+1+0=11 (奇数)

• 结论： 状态组合 ① 有解。

状态组合 ②：初始 "745361028" → 目标 "581470362"

• 初始状态 "745361028" 棋盘表示：
展开为序列 (忽略0): 7,4,5,3,6,1,2,8 逆序数计算：
• 7: (对于4, 5, 3, 6, 1, 2) → 6
• 4: (对于3, 1, 2) → 3
• 5: (对于3, 1, 2) → 3
• 3: (对于1, 2) → 2
• 6: (对于1, 2) → 2
• 1: 0
• 2: 0
• 8: 0 初始状态总逆序数 = 6+3+3+2+2+0+0+0=16 (偶数)

• 目标状态 "581470362" 棋盘表示：
展开为序列 (忽略0): 5,8,1,4,7,3,6,2 逆序数计算：
• 5: (对于1, 4, 3, 2) → 4
• 8: (对于1, 4, 7, 3, 6, 2) → 6
• 1: 0
• 4: (对于3, 2) → 2
• 7: (对于3, 6, 2) → 3
• 3: (对于2) → 1
• 6: (对于2) → 1
• 2: 0 目标状态总逆序数 = 4+6+0+2+3+1+1+0=17 (奇数)

• 结论： 状态组合 ② 无解

(2) 请列写出操作符数目最少的操作符集，并说明每个操作符的应用条件。基于所设计的操作符集，当空格位于棋盘左上角时，说明此种情况下可以使用的操作符。

操作符数目最少的操作符集

• 空格在左上角：可向右 (R)、向下 (D) 移动。

• 空格在右上角：可向左 (L)、向下 (D) 移动。

• 空格在左下角：可向右 (R)、向上 (U) 移动。

• 空格在右下角：可向左 (L)、向上 (U) 移动。

每个操作符的应用条件（假设棋盘行列从0开始编号）：

• 向上移动 (U - Up)： 空格不在第0行（即空格的行索引 > 0）。

• 向下移动 (D - Down)： 空格不在第2行（即空格的行索引 < 2）。

• 向左移动 (L - Left)： 空格不在第0列（即空格的列索引 > 0）。

• 向右移动 (R - Right)： 空格不在第2列（即空格的列索引 < 2）。

当空格位于棋盘左上角时，可以使用的操作符：

(3) 基于(1)中有解的状态组合绘制从初始状态到目标状态所需操作的前两步的状态空间图，要求每一步的棋盘状态用字符串表示，每一步操作须标明对应的操作符。

T2 搜索问题

（1）深度优先搜索（DFS）

（2）广度优先搜索（BFS）

启发式函数判断、一致性代价搜索 (UCS) 和 A* 搜索

a) 判断启发式函数 h1 和 h2 是否满足可接受性 (Admissibility) 和一致性 (Consistency)

• 首先计算各节点到目标 F 的实际最小代价 ：

• 可接受性 (Admissibility: h(n)≤h∗(n)):
• h1:
• A: 10≤11 (OK)
• B: 9≤10 (OK)
• C: 8≤9 (OK)
• D: 5≤6 (OK)
• E: 3.5≤5 (OK)
• F: 0≤0 (OK)
• 结论: h1 是可接受的。
• h2:
• A: 11≤11 (OK)
• B: 10≤10 (OK)
• C: 9≤9 (OK)
• D: 6≤6 (OK)
• E: 5≤5 (OK)
• F: 0≤0 (OK)
• 结论: h2 是可接受的。

• 一致性 (Consistency: h(n)≤c(n,n′)+h(n′)):
• h1: (需要检查所有边)
• A->B: h1(A)=10≤c(A,B)+h1(B)=1+9=10. OK.
• A->C: h1(A)=10≤c(A,C)+h1(C)=4+8=12. OK.
• A->D: h1(A)=10≤c(A,D)+h1(D)=6+5=11. OK.
• B->C: h1(B)=9≤c(B,C)+h1(C)=1+8=9. OK.
• B->D: h1(B)=9≤c(B,D)+h1(D)=5+5=10. OK.
• C->D: h1(C)=8≤c(C,D)+h1(D)=3+5=8. OK.
• C->E: h1(C)=8≤c(C,E)+h1(E)=5+3.5=8.5. OK.
• D->E: h1(D)=5≤c(D,E)+h1(E)=3+3.5=6.5. OK.
• D->F: h1(D)=5≤c(D,F)+h1(F)=6+0=6. OK.
• E->F: h1(E)=3.5≤c(E,F)+h1(F)=5+0=5. OK.
• 结论: h1 是一致的。
• h2: (需要检查所有边)
• A->B: h2(A)=11≤c(A,B)+h2(B)=1+10=11. OK.
• A->C: h2(A)=11≤c(A,C)+h2(C)=4+9=13. OK.
• A->D: h2(A)=11≤c(A,D)+h2(D)=6+6=12. OK.
• B->C: h2(B)=10≤c(B,C)+h2(C)=1+9=10. OK.
• B->D: h2(B)=10≤c(B,D)+h2(D)=5+6=11. OK.
• C->D: h2(C)=9≤c(C,D)+h2(D)=3+6=9. OK.
• C->E: h2(C)=9≤c(C,E)+h2(E)=5+5=10. OK.
• D->E: h2(D)=6≤c(D,E)+h2(E)=3+5=8. OK.
• D->F: h2(D)=6≤c(D,F)+h2(F)=6+0=6. OK.
• E->F: h2(E)=5≤c(E,F)+h2(F)=5+0=5. OK.
• 结论: h2 是一致的。

b)一致代价搜索UCS

节点名称	g(n)
A	0
B	1
C	2
D	5
E	7
F	11

c)A*搜索

• 使用h1(n)启发函数的A*搜索过程：
1. 拓展A(g+h=0+10=10)，得到B(1+9=10)、C(4+8=12)、D(6+5=11)
2. 拓展B，得到C(1+8=9)、D(5+5=10)
3. 拓展C，得到D(3+5=8)、E(5+3.5=8.5)
4. 拓展D，找到目标F(6+0=6)
最终搜索路径为A->B->C->D->F，总路径代价为11。

• 使用h2(n)
1. 拓展A(g+h=0+10=10)，得到B(1+10=11)、C(4+9=13)、D(6+6=12)
2. 拓展B，得到C(1+9=10)、D(5+6=11)
3. 拓展C，得到D(3+6=9)、E(5+5=10)
4. 拓展D，找到目标F(6+0=6)
最终搜索路径为A->B->C->D->F，总路径代价为11。

T3 纳什均衡

（1）双方支付矩阵

（2）纯策略纳什均衡

（3）

T4 CSP问题

1. 将以上问题描述为一个约束满足问题 (每门课程是一个变量)，指明课程变量教师安排情况的一元约束示例。

• 变量 : 每门课程是一个变量，代表该课程由哪位教师授课。

• 域 : 每个变量的论域是能够教授该门课程的教师集合。

• 一元约束
• C2∈{A}
• C3∈{B,C}
• C4∈{B,C}
• C5∈{A,B}

2

• C1 (8:00-9:00) 与 C2 (8:30-9:30) 时间重叠 (8:30-9:00)。约束: T(C1)=T(C2)。

• C2 (8:30-9:30) 与 C3 (9:00-10:00) 时间重叠 (9:00-9:30)。约束: T(C2)=T(C3)。

• C2 (8:30-9:30) 与 C4 (9:00-10:00) 时间重叠 (9:00-9:30)。约束: T(C2)=T(C4)。

• C3 (9:00-10:00) 与 C4 (9:00-10:00) 时间完全重叠。约束: T(C3)=T(C4)。

• C5 (10:30-11:30) 与其他课程均无时间重叠，因此没有基于时间冲突的二元约束涉及 C5。

T5 对抗搜索问题

根节点是位于最顶层的节点，它是树的起始点。

叶节点是位于树末端的节点。

（1）根节点处的效用数组

（2）能否剪枝？