1-前言

为了应对大学院考试，我们来学习相关人工智能相关知识，并做各种练习。

通过学习，也算是做笔记，让自己更理解些。

3-问题题目训练

第1問（相似：A*探索）

次の有向グラフにおいて、辺ラベルは移動コスト、各ノードの括弧内はヒューリスティック値 (h(n)) を表す。開始ノードを (S)、目標ノードを (G) とする。A*探索（評価関数 (f(n)=g(n)+h(n))）を用いる。ここで、OPEN から取り出す優先順位は (f) が最小、同値の場合は (g) が小さい方を優先、それでも同値の場合は アルファベット順とする。取り出したノードは CLOSED（訪問済み）に入れ、必要なら (g) を更新する（グラフ探索）。

• ノード：
  (S(6), A(4), B(4), C(2), D(1), E(3), G(0))

• 辺（コスト）：
  (S\to A:2,; S\to E:2)
  (A\to B:2,; A\to C:2)
  (E\to C:2,; E\to G:8)
  (C\to D:2,; C\to G:6)
  (D\to G:2,; B\to G:6)

(1) CLOSED に入る順（取り出し順）を、(S) から (G) が取り出されるまで全て書け。
(2) A*が返す経路と、その総移動コストを求めよ。
(3) 上の (h(n)) が 許容的（admissible）かどうかを判定し、根拠を 1 行で述べよ。

罠：同値タイ処理／(g) 更新（グラフ探索）／許容性の判定（「どこか1点でも過大」なら不可）

---

第2問（相似：粒子フィルタ / SIR）

自己位置推定に粒子フィルタを用いる。時刻 (t) における粒子は ({x_t^{(i)}, w_t^{(i)}}_{i=1}{5}) で表される。観測尤度に比例して未正規化重み (\tilde{w}_t^{(i)}) が得られたとする。

[
(\tilde{w}_t^{{(1)},\tilde{w}_t}{(2)},\tilde{w}_t^{{(3)},\tilde{w}_t}{(4)},\tilde{w}_t^{(5)})
= (0.20,;0.10,;0.05,;0.05,;0.60)
]

(1) 正規化重み (w_t^{(i)}) を求めよ。
(2) 有効サンプルサイズ (N_{\mathrm{eff}} = \frac{1}{\sum_{i=1}^{5}(w_t{(i)})^2}) を求めよ。
(3) しきい値を (N_{\mathrm{th}}=2.5) とするとき、SIR（Sampling Importance Resampling）を実行すべきか判定せよ。
(4) 粒子フィルタが「確率分布をサンプル集合で近似する」ことの名称を 1 つ答えよ。また、SIR で行う「再抽出」の名称を 1 つ答えよ。

罠：正規化しないままESSを計算／ESS式の分母・二乗ミス／「モンテカルロ近似」「リサンプリング（再標本化）」が出ない

---

第3問（模擬：Q学習の数値更新）

Q学習を考える。更新式は
[
Q(s,a)\leftarrow Q(s,a)+\alpha\left[r+\gamma \max_{a’}Q(s’,a’)-Q(s,a)\right]
]
とする。学習率 (\alpha=0.5)、割引率 (\gamma=0.9)。行動は各状態で 2 通り (a_1,a_2)。初期値はすべて (Q(\cdot,\cdot)=0)。

次の 3 ステップの経験列が得られた（同一状態が再訪されることに注意せよ）：

1. (s_0) で (a_1) を選び、報酬 (r=2)、次状態 (s_1)
2. (s_1) で (a_2) を選び、報酬 (r=-1)、次状態 (s_0)
3. (s_0) で (a_1) を選び、報酬 (r=2)、次状態 (s_1)

(1) 各ステップ後の (Q(s_0,a_1)) と (Q(s_1,a_2)) を求めよ（更新の途中式も示せ）。
(2) 上の更新で用いた (\max_{a’}Q(s’,a’)) が意味するものを 1 行で説明せよ。

罠：2回目の (s_0,a_1) 更新で「前回更新済みのQ」を使わず初期値扱い／maxを同じ行動で固定してしまう／(\alpha) と (\gamma) を取り違える

4-练习（日语版本）解析

【第1問】A*探索 ― 満点テンプレ

① 定義を書く（これがあると一気に評価UP）

A*探索では評価関数を
f(n) = g(n) + h(n)
とし、OPEN集合から f が最小のノードを取り出す。

② 初期状態を明示

初期状態：
OPEN = { S },  g(S)=0, f(S)=0+h(S)=6
CLOSED = ∅

③ 各展開を「表 or 箇条書き」で

（※ 採点者はここを一番見ます）

S を展開：
A: g=2, f=2+4=6
E: g=2, f=2+3=5
→ f 最小の E を選択

E を展開：
C: g=4, f=4+2=6
G: g=10, f=10+0=10

🔴 罠対策

• 同じノードに別経路が来たら
  **「g が小さい場合のみ更新」**と明記

④ CLOSED順は「列挙」

CLOSED に入る順：
S → E → A → C → D → G

⑤ 経路とコストは最後にまとめる

得られた経路：
S → A → C → D → G

総移動コスト：
2 + 2 + 2 + 2 = 8

⑥ 許容性の判断（超重要）

全ノードで h(n) ≤ 実際の最短距離が成り立つため、
このヒューリスティック関数は許容的である。

✔ これで満点構成

---

【第2問】粒子フィルタ（SIR）― 満点テンプレ

① 概念を一言で押さえる

粒子フィルタは確率分布を有限個のサンプルで近似する
モンテカルロ近似手法である。

② 正規化は必ず式で

重みの総和：
Σ wi = 0.20 + 0.10 + 0.05 + 0.05 + 0.60 = 1.00

よって正規化後も同一である。

🔴 罠
正規化を書かない答案は高確率で減点

③ 有効サンプルサイズ（ESS）

Neff = 1 / Σ (wi)^2
     = 1 / (0.04 + 0.01 + 0.0025 + 0.0025 + 0.36)
     = 1 / 0.415
     ≈ 2.41

④ 判定を「比較」で書く

Neff = 2.41 < Nth = 2.5 より、
リサンプリングを実行すべきである。

⑤ 用語は名詞でピタッと

分布近似：モンテカルロ近似
再抽出：SIR（リサンプリング）

---

【第3問】Q学習 ― 満点テンプレ

① 更新式を最初に書く（必須）

Q(s,a) ← Q(s,a) + α [ r + γ max_a' Q(s',a') − Q(s,a) ]

② Stepごとに「数値代入」

Step1:
Q(s0,a1) = 0 + 0.5[2 + 0.9×0 − 0] = 1.0

Step2:
Q(s1,a2) = 0 + 0.5[−1 + 0.9×1.0 − 0] = −0.05

Step3:
Q(s0,a1) = 1.0 + 0.5[2 + 0.9×0 − 1.0]
         = 1.5

🔴 最大の罠

• Step3で 「更新後のQ(s0,a1)=1.0」を使わない答案

③ max の意味を文章で

max_a' Q(s',a') は、
次状態において最も高い価値を持つ行動の推定値を表す。

---

5-总结

知识一点点记录吧，最后应对考试，打下基础