principle of invariant imbeddingとは何？わかりやすく解説 Weblio辞書

不変埋没原理

読み方：ふへんまいぼつげんり
【英】：principle of invariant imbedding

概要

動的計画法の基本原理の1つ. ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考える. これを「埋め込み」という. ただし, それぞれの問題の「構造」は不変である. このとき, 問題の大きさは小さいものから大きいものまであり, 「1番大きい」問題が与問題である. 相隣る問題間の関係式を導き, これを解くことによって, 与問題の「解」を求める. 埋め込み方に工夫を要する.

詳説

　ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考えることを「埋め込み」(imbedding)という. すなわち, 与問題をある問題群の１つと見做すことである. このとき, 問題の大きさは小さい(易しい)ものから大きい(難しい)ものまであり, 一番大きい(解きたい)問題が与問題である. しかし, 問題の「構造」は不変である. さらに, 相隣る問題間の関係式を導き, これを解くことによって, 与問題の「解」を求める. このような方法で解に至るまでを, 不変埋没原理 (principle of invariant imbedding)による方法という [1] [4] [5].

　たとえば,「1から10までの自然数の和を求める」問題を考えてみよう. 以下ではいつも「1から」(前向きの方法で)考えることにして, この問題を ${\rm P}(10)\,$ で表わし, 「解」(この場合, 和)を $S(10)\,$ としよう. このとき, 「1から $n\,$ までの自然数の和を求める」部分問題 ${\rm P}(n)\,$ からなる群 $\{ {\rm P}(n); n=1, 2, \ldots , 10\}\,$ を考える. このこと自体が埋め込みである. 部分問題 ${\rm P}(n)\,$ の解( $=\,$ 和)を $S(n)\,$ とする. 最後の(一番大きい)問題 ${\rm P}(10)\,$ の解 $S(10)\,$ が求める解である. このとき, 最初の (一番易しい) 問題の解は $S(1) = 1\,$ であり, 相隣る問題の解 $S(n)\,$ と $S(n+1)\,$ の間に漸化式

$S(n+1) = S(n) + n+1 \quad n=1, 2, \ldots , 9; \quad S(1) = 1\,$

が成り立つ. 漸化式を $S(1), S(2), \ldots\,$ の順に前向きに逐次解くことによって, $S(10) = 55\,$ を得る. 他方, 「 $n\,$ から(いつも！)10までの自然数の和を求める」部分問題 ${\rm Q}(n)\,$ の族を考えても, 上述と同様に解くことができる. これを後向きの埋め込みという.

　一般の問題では, どのような大きさの問題群に埋め込むか, 関係式が導けるか, 解けるか, 解き易いかなど, 埋め込み方に工夫を要する. たとえば, 多段階の最適化問題

$\mbox{max.} ~~ \psi(g_{1}(x_{1},x_{2}) \circ g_{2}(x_{2},x_{3}) \circ \cdots \circ g_{N}(x_{N},x_{N+1}) \circ k(x_{N+1})) \,$

$\mbox{s. t.} ~~~ x_{n+1} \in A_{n}(x_{n}) \quad (1 \le n \le N), \,$

の最大値 $u_{1}(x_{1})\,$ と最大点 $x^{*} = (x_{1}, x_{2}^{*}, \ldots , x_{N+1}^{*})\,$ を求めるには, 新たなパラメータ $\lambda_{n} (\in \Lambda_{n}(x_{n}))\,$ を含む部分問題群 ${\mathcal P} = \{ {\rm P}_{n}(x_{n};\lambda_{n}) \}\,$ :

${\rm max.}~~ \psi(\lambda_{n} \circ g_{n}(x_{n},x_{n+1}) \circ \cdots \circ g_{N}(x_{N},x_{N+1}) \circ k(x_{N+1})) \,$

$\begin{array}{l}\mbox{s. t.} ~~~ x_{m+1} \in A_{m}(x_{m}) \quad (n \le m \le N), \\ ~~~~ x_{n} \in X_{n}, \; \lambda_{n} \in \Lambda_{n}(x_{n}), ~ (1 \le n \le N+1), \end{array} \,$

に埋め込むと, パラメータ空間列 $\{\Lambda_{n}(\cdot)\}\,$ は前向きの再帰式

$\Lambda_{1}(x) = \{ \tilde{\lambda}\},~~x \in X_{1}\,$ $(\tilde{\lambda}\,$ は結合演算 $\circ\,$ の左単位元 $)\,$

$\begin{array}{lr} \Lambda_{n+1}(y) = & \{\, \lambda \circ g_{n}(x,\,y) \, | \, \lambda \in \Lambda_{n}(x),~y \in A_{n}(x) \, \} \\ & y \in X_{n+1},~~ n=1, 2, \ldots , N \end{array}\,$

で生成され, 最適値関数 $u_{n} = u_{n}(x_{n};\lambda_{n})\,$ は次の後向き再帰式を満たす：

$u_{n}(x; \lambda) = \max_{y \in A_{n}(x)}u_{n+1}(\,y\,; \lambda \circ g_{n}(x,\,y))\,$

$~~~~x \in X_{n}, ~~\lambda \in \Lambda_{n}(x),~~ n=1, 2, \ldots , N\,$

$u_{N+1}(x; \lambda) = \psi(\lambda \circ k(x))~~x \in X_{N+1},~~\lambda \in \Lambda_{N+1}(x).\,$

これを後ろから逐次解き, 最後の $u_{1}(x_{1};\lambda_{1})\,$ に $\lambda_{1} = \tilde{\lambda}\,$ を代入すると求める最大値が得られる： $u_{1}(x_{1}) = u_{1}(x_{1};\tilde{\lambda}).\,$

　また, 非最適化問題としては, 木の総容量など, 多重和 (多重和の解法)

$\mbox{S}_{1}(x_{1}):~~ {\sum \sum \cdots \sum} _{(x_{2}, x_{3}, \cdots , x_{N+1}) \in P_{1}(x_{1})} \psi(g_{1}(x_{1},x_{2}) \circ \cdots \circ g_{N}(x_{N},x_{N+1}) \circ k(x_{N+1}))\,$

$(P_{1}(x_{1}) := \{(x_{2}, \cdots , x_{N+1})\, |\, x_{n+1} \in A_{n}(x_{n})~~1 \le n \le N \})\,$

を求める問題があって, やはりパラメータを含む埋め込みによって解くことができる.

　このようなパラメータを導入した埋め込みは非可分性に起因し, 単一評価系, 複合評価系の最適化, 期待値最適化, 多重和, 多重積分 (多重積分の解法) などで考えられる [2] [3]. 不変埋没原理は変数の離散と連続, システムの確定や確率やファジィ, 問題の最適と非最適を問わず, 歴史的には数学(微分方程式, 偏微分方程式の応用), 物理数学などで, また近年はコンピュータサイエンスで幅広く用いられている.

参考文献

[1] R. E. Bellman and E. D. Denman, Invariant Imbedding, Lect. Notes in Operation Research and Mathematical Systems, Vol. 52, Springer-Verlag, Berlin, 1971.

[2] S. Iwamoto and T. Fujita, "Stochastic Decision-making in a Fuzzy Environment," Journal of the Operations Research Society of Japan, 38 (1995), 467-482.

[3] 岩本誠一,「不変埋没によるファジィ動的計画法」, 日本オペレーションズ・リサーチ学会第33回シンポジウム, 25-33, 1995.

[4] E. S. Lee, Quasilinearization and Invariant Imbedding, Academic Press, 1968.

[5] 相良節夫, 杉坂政典,「Invariant Imbedding について」,『システムと制御』, 17 (1973), 596-601.

「OR事典」の他の用語

動的・確率・多目的計画：

マルコフ政策一般政策三面鏡理論不変埋没原理両帰式両的計画事前条件付き決定過程

Weblio日本語例文用例辞書

索引トップ用語の索引ランキング

「principle of invariant imbedding」の例文・使い方・用例・文例

Microsoftがβ版をランチするのは「NetShow streaming server」で動画や音声をオンデマンドで提供する。
《主に米国で用いられる》＝《主に英国で用いられる》 an admiral of the fleet 海軍元帥.
篏入的 r 音《英音の India office /ndiərfɪs/の /r/の音》.
＝《口語》 These kind of stamps are rare. この種の[こういう]切手は珍しい.
(英国の)運輸省. the Ministry of Education(, Science and Culture) (日本の)文部省.
は of の誤植です.
を off と誤植する.
あいまい母音《about, sofa などの /ə/》.
副詞的小詞《on, in, out, over, off など》.
迂言的属格《語尾変化によらず前置詞によって示す属格; たとえば Caesar's の代わりの of Caesar など》.
çon of garlic [humor]. それにはガーリック[ユーモア]がちょっぴり必要だ.
《主に米国で用いられる》＝《主に英国で用いられる》 the Speaker of the House of Commons 下院議長.
《主に米国で用いられる》＝《主に英国で用いられる》 the Committee of Ways and Means 歳入委員会.
初めて読んだ英文小説は“The Vicar of Wakefield”
（違法罪―a sin of commission―に対する）怠惰罪
『each』、『every』、『either』、『neither』、『none』が分配的、つまり集団の中の1つのものを指すのに対し、『which of the men』の『which』は分離的である
『hot off the press（最新情報）』は『hot（最新の）』の拡張感覚を示している
『Each made a list of the books that had influenced him』における制限節は、リストに載った本を制限節で定義された特定の本だけに制限する
臨床的鬱病を治療するのに用いられる三環系抗鬱薬（商品名ImavateとTofranil）
『sunshine-roof』は『sunroof（サンルーフ）』に対する英国の用語である

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。

>> 「principle of invariant imbedding」を含む用語の索引
principle of invariant imbeddingのページへのリンク


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2024 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2024 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

principle of invariant imbeddingとは？ わかりやすく解説

不変埋没原理

概要

詳説

「principle of invariant imbedding」の例文・使い方・用例・文例

principle of invariant imbeddingとは？わかりやすく解説