任务 8

背景（Context）：
在统计机器翻译（Statistical Machine Translation）中，一个常见的子问题是词序排列（Word Ordering）。给定一个“词袋”（即一组被打乱顺序的单词），你需要重建原始句子的顺序，以最大化该序列的概率。

设 \(W = \{w_1, w_2, \dots, w_N\}\) 为由 \(N\) 个唯一单词组成的集合。
给定一个 二元语言模型（Bigram Language Model） \(P(w_j | w_i)\)，它给出单词 \(w_j\) 在单词 \(w_i\) 之后出现的概率。
存在两个特殊符号：\(⟨\text{S}⟩\)（起始）和 \(⟨\text{E}⟩\)（结束）。句子必须以 \(⟨\text{S}⟩\) 开始，并以 \(⟨\text{E}⟩\) 结束。

目标（Objective）：
寻找单词集合 \(W\) 的一个排列 \(\pi\)，使得句子概率最大化：
\[
P(\pi) = P(w_{\pi_1} | ⟨\text{S}⟩) \times \left( \prod_{i=1}^{N-1} P(w_{\pi_{i+1}} | w_{\pi_i}) \right) \times P(⟨\text{E}⟩ | w_{\pi_N})
\]

为了应用 A* 算法，我们将该最大化问题转化为最小化问题，通过将单词 \(u\) 到单词 \(v\) 的转移代价定义为负对数概率：
\[
C(u, v) = -\ln(P(v | u))
\]

第 A 部分：状态空间形式化（State Space Formalization）
 将该问题形式化为适用于 A* 算法的状态空间图搜索问题。具体定义：

    1. 状态（State） \(n\) 的结构。
    2. 起始状态（Start State） 和 目标状态（Goal State）。
    3. 后继函数（Successor Function）（如何生成状态转移）以及累计代价 \(g(n)\)。

[3 分]

第 B 部分：启发式函数设计（Heuristic Design）
 问题的核心难点在于搜索空间具有阶乘规模（\(N!\)），使得简单的启发式函数（例如 \(h=0\)）在输入规模稍大时（例如 \(N > 15\)）计算上不可行。
设计一个非平凡的启发式函数 \(h(n)\)，用于估计完成句子所需的剩余代价。你的启发式函数必须满足以下条件：

    1. 必须是可采纳的（admissible）。
    2. 必须是单调的（monotonic，也称一致性 consistent）。

用数学形式定义你的启发式函数。此处无需证明其性质，但必须解释你的设计思路。

提示：考虑尚未被放置的单词集合。在一个合法的完整句子中，这些单词中的每一个都必须恰好有一条入边。

[5 分]

第 C 部分：理论证明（Theoretical Proofs）
 基于你在第 B 部分中定义的启发式函数 \(h(n)\)，给出以下性质的形式化证明：

    1. 可采纳性（Admissibility）：证明 \(h(n) \le h^*(n)\)，其中 \(h^*(n)\) 为到达目标状态的真实最小代价。
    2. 单调性（Monotonicity）：证明 \(h(n) \le cost(n, n') + h(n')\)，其中 \(n'\) 是 \(n\) 的一个后继状态。

[5 分]
[总计 13 分]