任務 8

背景：
在統計機器翻譯（Statistical Machine Translation）中，一個常見的子問題是詞序排列（Word Ordering）。你會得到一個「詞袋」（一組被打亂順序的詞），並必須重建原本的句子順序，以最大化該序列的機率。

令 \(W = \{w_1, w_2, \dots, w_N\}\) 為一組包含 \(N\) 個互異詞的集合。
給定一個 二元語言模型（Bigram Language Model），\(P(w_j | w_i)\)，其提供詞 \(w_i\) 之後接續詞 \(w_j\) 的機率。
另外有兩個特殊 token：\(⟨\text{S}⟩\)（開始）與 \(⟨\text{E}⟩\)（結束）。句子必須以 \(⟨\text{S}⟩\) 開始並以 \(⟨\text{E}⟩\) 結束。

目標：
找出 \(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 部分：狀態空間形式化
將此問題形式化為適用於 A* 演算法的狀態空間圖搜尋問題。
具體而言，請定義

    1. 狀態 \(n\) 的結構。
    2. 起始狀態與目標狀態。
    3. 後繼函數（如何生成轉移）以及累積成本 \(g(n)\)。

[3 分]

第 B 部分：啟發式函數設計
核心困難在於搜尋空間具有階乘結構（\(N!\)），使得平凡的啟發式（例如 \(h=0\)）即使在中等輸入大小下（例如 \(N > 15\)）也會在計算上不可行。
設計一個非平凡的啟發式函數 \(h(n)\)，用以估計完成句子所需的剩餘成本。你的啟發式必須符合下列條件：

    1. 必須是可容許的（admissible）。
    2. 必須是單調的（monotonic，亦即一致/consistent）。

以數學方式定義你的啟發式函數。你尚不需要證明這些性質，但必須解釋設計背後的邏輯。

提示：考慮尚未放置的詞集合。在一個有效的完整句子中，這些詞中的每一個都必須恰好有一條入邊。

[5 分]

第 C 部分：理論證明
使用你在第 B 部分定義的啟發式函數 \(h(n)\)，對下列性質給出形式化證明：

    1. 可容許性：證明 \(h(n) \le h^*(n)\)，其中 \(h^*(n)\) 為到達目標的真實最小成本。
    2. 單調性：證明 \(h(n) \le cost(n, n') + h(n')\)，其中 \(n'\) 為 \(n\) 的一個後繼狀態。

[5 分]
[總分 13 分]