2011-8 第4問 (5)

ニューラルネットワークとは、脳の神経回路による計算をコンピュータで再現したものである。
ニューラルネットワークの学習モデルとして現在最も良く用いられるものの一つがバックプロパゲーションである。
バックプロパゲーションでは、入力から前向きにニューラルネットワークをたどりながら出力を求め、その結果と期待される出力の差が小さくなるように後ろ向きにニューラルネットワークをたどりながら各ニューロンの重みを更新する。

2011-8 第4問 (4)

モンテカルロ法とは、乱数を用いて問題の近似解を求める手法の一つである。
モンテカルロ法は多項式時間で終了することを保証するが、得られた解が必ずしも正しいとは限らない。
モンテカルロ法を用いた数値計算の例としては、円周率の計算が有名である。
これは、[0, 1]x[0, 1] の範囲の乱数を多数生成し、そのうち原点を中心とする円の内部に含まれるものの割合を計算することで π/4 の値を近似的に求めるというものである。

2011-8 第4問 (2)

カルマンフィルタとは、誤差のある離散的な観測値から時間変化するシステムの現在の状態を推定する手法。システムの現在の観測値と1ステップ前の推定値から、システムの現在の状態の推定値と1ステップ先の予測値を与える反復型の予測を行う。
カルマンフィルタは各ステップごとに予測と更新の二つを行う。予測では前ステップの推定値から現在の推定状態を計算し、更新では現在の観測値を利用して推定値を補正してより正確な値に近づける。

2011-8 第4問 (1)

フィードバック制御は、連続動作するシステムにおいて、前回の入力に対する出力を入力要素の一つとすることで、より精密な出力を得る手法。制御を乱す外的要因(外乱)による影響を自動的に修正できるが、外乱による影響を検出してからでないと修正ができないという欠点が存在する。
フィードフォワード制御は、外乱による影響が現れる前に外乱を検知して修正を行う制御方式。対象となる外乱の影響を最小限にできるが、予期しない外乱に弱く、また一定の状態を維持するといったことができない。
そのため、通常はフィードバック制御とフィードフォワード制御を併用する。

2011-8 第3問 (5)

w_x = h_x - l₃cosh_θ
w_y = h_y - l₃sinh_θ

なので、(w_x, w_y) ≠ (0, 0) のとき、
(3)で示した手続きによりθ₁およびθ₂を求めることができる。

このとき、θ₃ = h_θ - θ₁ - θ₂ より、
残りのθ₃も求めることができる。

また、(w_x, w_y) = (0, 0)のとき、
θ₁およびθ₂は一意に決まらない。

2011-8 第3問 (4)

h_θ = θ₁ + θ₂ + θ₃
h_x = w_x + l₃cosh_θ = l₁cosθ₁ + l₂cos(θ₁ + θ₂) + l₃cos(θ₁ + θ₂ + θ₃)
h_y = w_y + l₃sinh_θ = l₁sinθ₁ + l₂sin(θ₁ + θ₂) + l₃sin(θ₁ + θ₂ + θ₃)

2011-8 第3問 (3)

直線OWとX軸のなす角をθ_wとし、
l_w = sqrt(w_x² + w_y²)

余弦定理より、
l₂² = l₁² + l_w² - 2l₁l_wcos(θ_w - θ₁)

加法定理より、
l₂² = l₁² + l_w² - 2l₁cosθ₁ * l_wcosθ_w - 2l₁sinθ₁ * l_wsinθ_w

関節Eの座標を(e_x, e_y)とすると、
l₂² = l₁² + l_w² - 2e_xw_x - 2e_yw_y
2e_yw_y = l₁² - l₂² + l_w² - 2e_xw_x

両辺を二乗して、
4e_y²w_y² = (l₁² - l₂² + l_w²)² - 4e_xw_x(l₁² - l₂² + l_w²) + 4e_x²w_x²

e_x² + e_y² = l₁²なので、
4w_y²l₁² - 4e_x²w_y² = (l₁² - l₂² + l_w²)² - 4e_xw_x(l₁² - l₂² + l_w²) + 4e_x²w_x²

e_xについて整理して、
4(w_x² + w_y²)e_x² - 4w_x(l₁² - l₂² + l_w²)e_x + (l₁² - l₂² + l_w²)² - 4w_y²l₁² = 0

w_x² + w_y² = l_w²なので、
4l_w²e_x² - 4w_x(l₁² - l₂² + l_w²)e_x + (l₁² - l₂² + l_w²)² - 4w_y²l₁² = 0

この2次方程式の判別式をD_xとすると、

D_x/16 = w_x²(l₁² - l₂² + l_w²)² - l_w²((l₁² - l₂² + l_w²)² - 4w_y²l₁²)

展開して整理すると、

D_x/16 = (w_x² - l_w²)(l₁² - l₂² + l_w²)² + 4w_y²l₁²l_w² 

w_x² - l_w² = - w_y²なので、
D_x/16 = w_y²(4l₁²l_w² - (l₁² - l₂² + l_w²)²) 

因数分解して、
D_x/16 = w_y²(l₂ - l₁ + l_w)(l₂ + l₁ - l_w)(l₁ - l₂ + l_w)(l₁ + l₂ + l_w)

l₁ + l₂ + l_w > 0なので、D_x > 0となるのは
w_y ≠ 0 かつ l₁ + l₂ > l_w かつ l₁ + l_w > l₂ かつ l₂ + l_w > l₁のとき、
つまり、
WがX軸上に存在せず、三点OEWが一直線上に並ばないときである。

このとき、DをD_x/16 = w_y²Dとすると、
e_x = (w_x(l₁² - l₂² + l_w²) ± w_{y *} sqrt(D)) / 2l_w²

e_x² + e_y² = l₁²より、
e_x = (w_x(l₁² - l₂² + l_w²) + w_y * sqrt(D)) / 2l_w² のとき e_y = (w_y(l₁² - l₂² + l_w²) - w_x * sqrt(D)) / 2l_w²
e_x = (w_x(l₁² - l₂² + l_w²) - w_y * sqrt(D)) / 2l_w² のとき e_y = (w_y(l₁² - l₂² + l_w²) + w_x * sqrt(D)) / 2l_w²

また、(w_x, w_y) ≠ (0, 0) で、関節WがX軸上に存在する場合、
e_x = w_x(l₁² - l₂² + l_w²) / 2l_w² = (l₁² - l₂² + w_x²) / 2w_x
e_y = ±w_x * sqrt(D) / 2l_w² = ±sqrt(D) / 2w_x

同様に、(w_x, w_y) ≠ (0, 0) で、関節WがY軸上に存在する場合、
e_x = ±sqrt(D) / 2w_y
e_y = (l₁² - l₂² + w_y²) / 2w_y

また、(w_x, w_y) ≠ (0, 0)で、三点OEWが一直線上に並ぶ場合、
e_x = w_x(l₁² - l₂² + l_w²) / 2l_w²
e_y = w_y(l₁² - l₂² + l_w²) / 2l_w²

よって、(w_x, w_y) ≠ (0, 0) のとき、
θ₁, θ₂はこれらのe_x, e_yを用いて、

θ₁ = atan(e_y, e_x)
θ₂ = atan(w_y - e_y, w_x - e_x) - θ₁
と表せる。

また、(w_x, w_y) = (0, 0) のとき、
θ₁, θ₂は一意に決まらない。

2011-8 第3問 (2)

atan(y, x) = tan^-1(y/x) ( x > 0 のとき )
atan(y, x) = ( y / |y| ) * π / 2 (x = 0 のとき )
atan(y, x) = tan^-1(y/x) + ( y / |y| ) * π ( x < 0, y ≠ 0 のとき )
atan(y, x) = π ( x < 0, y = 0 のとき )

2011-8 第3問 (1)

関節Eの座標を(e_x, e_y)とすると、

e_x = l₁cosθ₁
e_y = l₁sinθ₁

よって、

w_x = e_x + l₂cos(θ₁ + θ₂) = l₁cosθ₁ + l₂cos(θ₁ + θ₂)
w_y = e_y + l₂sin(θ₁ + θ₂) = l₁sinθ₁ + l₂sin(θ₁ + θ₂)

2011-8 第1問 (2-1) (2-2)

(2-1)

F(j, k) = max( F(j-1, k), F(j-1, k-aj) + cj )

---

(2-2)

j＼k	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1	0	0	14	14	14	14	14	14	14	14
2	0	0	14	14	22	22	36	36	36	36
3	0	0	14	14	22	22	36	36	44	44
4	0	0	14	14	23	23	36	36	45	45
5	0	0	14	14	23	26	36	36	45	48

以上より、
x1 = 1, x2 = 1, x3 = 0, x4 = 0, x5 = 1 のとき最大合計価値 48

2011-8 第1問 (1-2)

探索木
* P0
** P1 : x1 = 1
*** P2 : x2 = 1, x3 = 0
**** P3 : x4 = 1, x5 = 0 ダメ
**** P4 : x4 = 0
*** P5 : x2 = 0
**** P6 : x3 = 1, x4 = 0, x5 = 0 ダメ
**** P7 : x3 = 0 ダメ
**P8 : x1 = 0 ダメ

P0 : 問題 A1
>下界 : 45 (1, 1, 0, 1, 0) :: 暫定値
>上界 : 51 (1, 1, 1/2, 0, 0)

P1 : x1 = 1
>下界 : 45 (1, 1, 0, 1, 0)
>上界 : 51 (1, 1, 1/2, 0, 0)

P2 : x1 = 1, x2 = 1, x3 = 0
>下界 : 45 (1, 1, 0, 1, 0)
>上界 : 49 (1, 1, 0, 1, 1/3)

P3 : x1 = 1, x2 = 1, x3 = 0, x4 = 1, x5 = 0
>下界 : 44 (1, 1, 0, 1, 0)
>上界 : 44 (1, 1, 0, 1, 0) < 暫定値 45

P4 : x1 = 1, x2 = 1, x3 = 0, x4 = 0
>下界 : 48 (1, 1, 0, 0, 1) :: 暫定値
>上界 : 48 (1, 1, 0, 0, 1)

P5 : x1 = 1, x2 = 0
>下界 : 44 (1, 0, 1, 0, 0)
>上界 : 49.5 (1, 0, 1, 1/2, 0)

P6 : x1 = 1, x2 = 0, x3 = 1, x4 = 0, x5 = 0
>下界 : 44 (1, 0, 1, 0, 0)
>上界 : 44 (1, 0, 1, 0, 0) < 暫定値 48

P7 : x1 = 1, x2 = 0, x3 = 0
>下界 : 35 (1, 0, 0, 1, 1)
>上界 : 35 (1, 0, 0, 1, 1) < 暫定値 48

P8 : x1 = 0
>下界 : 43 (0, 1, 0, 1, 1)
>上界 : 47 (0, 1, 5/6, 0, 0) < 暫定値 48

以上より、
x1 = 1, x2 = 1, x3 = 0, x4 = 0, x5 = 1のとき最大合計価値 48

2011-8 第1問 (1-1)

分枝限定法 : 分枝操作 + 限定操作
分枝操作 : 問題を幾つかの子問題に分割
限定操作 : 子問題の目的関数の上界と下界を求め、上界が暫定解以下ならばその子問題を捨てる
暫定解 : それまでに解いた子問題の下界のうち最大のもの
上界 : 緩和問題(0or1 を [0, 1]にした問題)の解
下界 : 適当な実行可能解