メモ化探索における大小関係 (ID:72850)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文 >（要するに「どうメモする」か，ではなくそれ以前に「どう評価するか」という話であって， >それは問題依存なのではないかと．） もしかしたら私の疑問は良さの評価関数をどう扱うかということなのかもしれませんね。 色々な場合を考えてしまいます。 例えばナップザック問題のメモカで、x,y,zというパラメータを持つ物がありそれを組み合わせるとします。 ｚがナップザック問題における重さの役割を果たし、ｘ、ｙの組をf(x,y)という評価関数でよさを評価できる時,f(x,y)が線形方程式ならいいのですが非線形方程式だと、単純にｆ（x,y）が最大になる値をｚの配列に入れていくことができない。 等ということになるのかも？ 参照透過性がなりたたず、メモ化で記録した内容を再代入して次のメモ化の記録を決定する場合なども難しそうですね。 ナップザック問題風に zが重さでxが適当な変数で、zの各々の重さに対して最良の値を入れていきます。 z[i]=nでｎが一番大きくなるようにメモ化していくとします。 z[3]=11が３の時最もいい値になるとします。 z[3]を元に色々な値を代入して、ナップザック問題風にz[7]の値が決まるとします。 z[3]=7の時z[7]=f(z[3],a)とします。 z[7]=f(7,a)=20 z[7]=f(11,a)=4 というふうになるような場合、z[3]=11をメモしては駄目でメモ化が単純に決まらないような感じがします。 色々な場合どうなるのか想像もつかず整理できない状態なのですが、こんなふうに色々な疑問が出てきたりするのです。 >ホウジョウウサギさんありがとうございます。 リンク先問題の解き方私も同じ考えでした。 一応確認。 1〜6番までの蔵を通って7番の蔵に行くという経路を通った場合。 1234567 3124567 、、、 色々な経路がありますが、どの経路を通っても、7番についた時持ってる１０００両箱の重さはどんな順番でも同じ。 7番の次に行く蔵を決める時、１〜7までの蔵以外の蔵を選ぶ。 という部分も同じになります。 すると1〜6までの蔵を通って7に行くという条件を満たす全てのルートはどれか一つの経路だけが正解として残り他は枝がり出来る。 ということになります。 これは２次元のメモ化になるので、今いる蔵の位置*入った蔵のリスト という15*2＾15個程度のメモ領域を用意し、どのメモ要素も次の蔵1〜15個までを調べるだけでいいのでその計算量は大雑把にいって。 15*2＾15*15よりは小さくなる。 これは深さ優先探索の最悪の計算量15！、幅優先探索の最悪の計算量14！に比べて圧倒的に小さい上に計算量も安定するので多分いい方法だと考えています。