不変埋没原理
【英】:principle of invariant imbedding
概要
動的計画法の基本原理の1つ. ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考える. これを「埋め込み」という. ただし, それぞれの問題の「構造」は不変である. このとき, 問題の大きさは小さいものから大きいものまであり, 「1番大きい」問題が与問題である. 相隣る問題間の関係式を導き, これを解くことによって, 与問題の「解」を求める. 埋め込み方に工夫を要する.
詳説
ある問題を解こうとするとき, この問題を含む部分問題からなる群(族)を考えることを「埋め込み」(imbedding)という. すなわち, 与問題をある問題群の1つと見做すことである. このとき, 問題の大きさは小さい(易しい)ものから大きい(難しい)ものまであり, 一番大きい(解きたい)問題が与問題である. しかし, 問題の「構造」は不変である. さらに, 相隣る問題間の関係式を導き, これを解くことによって, 与問題の「解」を求める. このような方法で解に至るまでを, 不変埋没原理 (principle of invariant imbedding)による方法という [1] [4] [5].
たとえば,「1から10までの自然数の和を求める」問題を考えてみよう. 以下ではいつも「1から」(前向きの方法で)考えることにして, この問題を で表わし, 「解」(この場合, 和)を
としよう. このとき, 「1から
までの自然数の和を求める」部分問題
からなる群
を考える. このこと自体が埋め込みである. 部分問題
の解(
和)を
とする. 最後の(一番大きい)問題
の解
が求める解である. このとき, 最初の (一番易しい) 問題の解は
であり, 相隣る問題の解
と
の間に漸化式
が成り立つ. 漸化式を の順に前向きに逐次解くことによって,
を得る. 他方, 「
から(いつも!)10までの自然数の和を求める」部分問題
の族を考えても, 上述と同様に解くことができる. これを後向きの埋め込みという.
一般の問題では, どのような大きさの問題群に埋め込むか, 関係式が導けるか, 解けるか, 解き易いかなど, 埋め込み方に工夫を要する. たとえば, 多段階の最適化問題
![]() |
![]() |
の最大値 と最大点
を求めるには, 新たなパラメータ
を含む部分問題群
:
![]() |
![]() |
![]() ![]() ![]() ![]() |
![]() |
![]() |
![]() |
![]() |
これを後ろから逐次解き, 最後の に
を代入すると求める最大値が得られる:
また, 非最適化問題としては, 木の総容量など, 多重和 (多重和の解法)
![]() |
![]() |
を求める問題があって, やはりパラメータを含む埋め込みによって解くことができる.
このようなパラメータを導入した埋め込みは非可分性に起因し, 単一評価系, 複合評価系の最適化, 期待値最適化, 多重和, 多重積分 (多重積分の解法) などで考えられる [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.
動的・確率・多目的計画: | マルコフ政策 一般政策 三面鏡理論 不変埋没原理 両帰式 両的計画 事前条件付き決定過程 |
「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(サンルーフ)』に対する英国の用語である
- principle of invariant imbeddingのページへのリンク