メモ化探索を行う場合、あるメモ領域にどの情報を記録するか選別するにはメモに入れるデータ同士の優先順位の大小比較ができないと、どのデータを優先してメモに入れていくかが決定できないように思えます。
メモに記録するデータが２変数以上になると、２変数を考慮してメモに入れるデータを決定するには複素数と同じで大小関係が決定できなくなります。
例えば、メモに入れるのが自然数だけで、メモのある領域を新しいデータで更新するかしないかは数字の大小だけで済むというなら話は簡単です。
しかし、メモに入れる物がクラスになりクラスの要素が２変数以上になると私はとたんにお手上げになってしまいます。
具体的にいえばリンク先にあるような問題など難しい。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0146
背負ってる荷物の重さと到着時刻と今まで通ってきた蔵の番号のリスト。
という３変数を考慮することになり何か難しく思えます(もしかしたらコロンブスの卵的発想一つの問題かもしれませんが)。
私は素朴で低レベルなアルゴリズムしか知らないためにこういった問題に出会うとすぐにおて当て上げ状態になってしまいます。
２変数以上が関わるメモ化はどのように考えればよいのでしょうか？
多数の変数を代入して一つの値を返す評価関数が作れたり、変数を従属変数に変形できるならいいのですが、メモするものが多数の独立変数で成り立っているデータの場合メモ化はどのように行うのでしょうか？
「メモ化」って何語？初耳なんだけど。オレオレ語なら意味を解説してほしい。
提示例題については結局のところ総当りして最小を求める問題なので
入力されたデータは、入力順に覚えればいい。
入力された個数が n であるとき n! 個あるルートを総当りする（しかないだろう）
# 枝狩りはできるね
"メモ化探索"で検索すると出てくるみたいです．
（内容がいまいち不明ですが
途中経路まで探索した結果を保存しておいて
あとでその経路を含む経路の計算を行うときにそれ結果を使う こと？）
リンク先の問題に対して"メモ化探索"を行うと
具体的にどういった処理の流れになるのか をもう少し説明されてみては
いかがでしょうか？
なるほどね、「同一入力に対して同一結果を返す」関数に限定して
過去の計算結果を「メモする」ことで計算速度を向上させる手法、っと。
でもこの問題に対しては向かないんぢゃないかな・・・
そもそも計算過程で同一入力が現れる機会が極めて少ないと思われるので。
しかし
メモが何らかの大小比較によって更新される
という話にも見えるから検索結果出てくるようなものとは違う話なのかも
うーん、私の言葉の使い方が間違ってましたか？
イメージとしてはこんな感じなんです。
例えば、ナップザック問題などで重さに対して金額が戻り値になります。
重さにたいする金額を決めるために、探索の途中で同じ重さでより金額の大きい組み合わせが見つかったら、そちらに金額を更新しますよね？
この時のよりよい値で更新する場合が疑問なのです。
単純なナップザック問題だと重さに対する金額という一つの基準だけだから簡単です。
同じ重さなら金額の大きい方を優先すればいいだけです。
これが体積や形や金銭以外の価値(食料、水、防寒着、成分)等色々な価値基準でナップザックに詰め込むものを評価しないといけない時どうメモ化していくか。
重さに対してどうナップザックの中身を設定するか？
というイメージなのです。
今度はイメージ伝わるでしょうか？」
言葉の定義はよくわかりませんが，
ある同じ条件で以前よりも良い結果が得られたら条件に対応する結果情報を更新する
ということでしょうか．
ある問題において「最も良い」答えを探索しようという場合，
結局，その問題において「良い評価」を得られるものが何か，が与えられていると思いますし，
それが与えられないならば「最も良い」ものを探索する，という話自体ができないように思いますが…
（要するに「どうメモする」か，ではなくそれ以前に「どう評価するか」という話であって，
それは問題依存なのではないかと．）
で，少なくとも例示された問題においては，良さ＝経過時間の短さ であることははっきりとしているわけで，
例えば
条件＝「ある蔵Aから 途中で蔵{B,C,D}を経由して 蔵Dまで行くための経路」とすれば
途中の行き方が異なる経路間での相対評価は可能であるので
この条件（が問題へのアプローチとして良いかどうかは別として）
の元でならば"メモ"は可能かと考えます．
ホウジョウウサギ さんの書かれている通りで、
メモ化云々とは別問題の評価の話かと思います。
検索に限らずmemoizationという語は使われますが、これ自体は
http://ja.wikipedia.org/wiki/メモ化
「メモ化は関数の時間コストを領域コストに交換して、
時間コストを低減させる手段である。」
に過ぎないので、
大小以外の途中結果をメモ化していってもいいわけですし、
実行時間さえ気にしなければメモ化しなくても評価できます。
(というかメモ化なしで無理なものはメモ化しても変わらない)
「参照投下性をどう確保するか」という話でなければ、
基本的にはそれは単に評価方法の話であってmemoizationとは関係ないかと。
まずメモ化云々を考えずに力技の検索処理を書くと想定して、
その評価が式にできますか。その結果がメモ化の有力候補です。
>（要するに「どうメモする」か，ではなくそれ以前に「どう評価するか」という話であって，
>それは問題依存なのではないかと．）
もしかしたら私の疑問は良さの評価関数をどう扱うかということなのかもしれませんね。
色々な場合を考えてしまいます。
例えばナップザック問題のメモカで、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！に比べて圧倒的に小さい上に計算量も安定するので多分いい方法だと考えています。
>z[3]とz[7]の話
は，重さZ=3という条件下での最適解が
重さZ=7という条件下での最適解を作る時の部分要素(?)に必ずしもならない
ということでしょうか．
であれば，そもそも
「z[3]を記録してあとでz[Z>3]の計算時に使いまわす
というアプローチ自体が通用しない類の問題である」
ということなのではないでしょうか？
>f(x,y)が非線形方程式
だったりする場合，それは
f(x,y)を最大化するようなパラメタ値x,yを求める 非線形最適化問題
になってしまうような気がします．
非線形最適化問題（…の分野には全然詳しくないので間違っているかもしれませんが）
では一般には，こうすれば必ず最適解が求まる」という方法は無いと思うので，
与えられた問題の上で何かしら工夫できないのであれば，
パラメタ初期値(x,y)=(x0,y0)から出発して
f(x,y)の勾配情報等に基づいて(x,y)空間上をさ迷い歩くような探索方法(Newton法とか)
を採るしかないかもしれません．
とりあえず作ってみた
http://codepad.org/LA1kHGTa
単純総当り方式。複雑な「メモ」などしていないし、枝刈りも単純。
ホウジョウウサギさんありがとうございます。
色々な疑問があるのですが、一番簡単な疑問を表現するならこんな問題になります。
田舎の冒険家のＡさんは露出した鉱脈を探し当てた。
そこそこ珍重される鉱石がごろごろしている。
これを背中に背負ったナップザックで持って帰るのだが、鉱石はたくさん持って帰りたいがあまり多いと値崩れして価値が下がってしまう。
鉱石は自然の造形が美術品として珍重されるのでＡさんが割って持って帰るわけにはいかない。
一つ一つ塊でナップザックに入れるしかないのだ。
売上はAさんが持って帰る鉱石の価値の総計xで決まり,-ax(x-b)となっている。
Ａさんの住んでいる地域は治安が悪いので盗まれる恐れもあり一度に売りさばきたい。
転がっている鉱石の数Ｎ個
転がっている鉱石の各々の重さＷiと価値Ｖｉ、ナップザックで持って帰れる重さの限界W、定数aとｂの値が情報として与えられる。
ナップザック問題の拡張として上記問題をとくにはどうすればよいだろうか？
という感じです。
非線形最適化問題について調べてみます。
この辺は難しそうなので学習も牛歩の歩みになりそうです。
tetrapodさんのソース今から読んでみます。
リンク先問題は何も考えずに解くと15！の探索ということになりメモ化探索や工夫なしでは時間切れで不正解になるのですがその辺大丈夫でしょうか？
”ナップザック問題”の厳密解を高速に求める方法（があるのかどうかも含めて）を存じ上げないので
全く的外れかもしれませんが，
仮に，売上f(x)=x である場合を解ける方法Mが存在するとすれば…
提示の売上評価関数 f(x,a,b)=-ax(x-b) について，
f()が極大値あるいは極小値となるx=xlを求めれば，
xlを境界として，f()を
・xの増加に対して評価が右肩上がりで増加する領域（f(x)=xと見なして解いて良い）
・xの増加に対して評価が右肩下がりで減少する領域
の２つに分けて考えることができるから，それぞれの領域に対して方法Mを個別に
（減少する領域ではf(x)=-xとして）使えないでしょうか？
お返事遅れましたすいません。
いままで別の勉強、初歩的なBit演算とメモ化探索を組みあわせた場合のアルゴリズムの勉強をしてましてお返事遅れ申し訳ありません。
ホウジョウウサギさんお返事ありがとうございます。
つまり全く入ってない場合からＸｌを上限として追加する。
全部入ってる状態からＸlが最高になる値を探。
ということで両方からナップザック法を試してみるということでしょうか？
それは上手くいきそうですね。
関数が凸であることを利用した方法ですね。
その方法は確実にベターな方法だと思いますが、最善なのか近似解なのか難しそうなのでよく考えさせてください。
もし最善の手法だとしたら、y=f(x)であらわされる関数にｎ個極値がある場合も同様にｎ個に分解して解くことができるのか？
というのが今の疑問です。
私はあまり頭がよくない方(私が人生最後に受けた最も高度な数学の授業は通信教育の数学Ⅱで40時間程度の授業しか受けてないうえ昔のこと)なので教えてもらった方法が妥当かどうかの判断すら出来ないかも知れませんができるだけ頑張って考えたり調べたりしてみます。
>すいません、書き間違えました。
1 全く入ってない場合から普通にナップザック法を適用する。
2 全部入ってる状態から中身を減らす方法でナップザック法を適用する。
1と２の結果から重さｗ以下の最高の売値を探す。
1と２は価値が極致を超えたらその先は計算しない。
ということですね？
私が書いた話は そもそも
「厳密解を求める方法Mが存在すれば」という仮定の上ですから，
>最善なのか近似解なのか
と言われれば，最善の解が得られるように思います（多分）．
少なくとも該仮定を満たす方法Mの候補としては「全探索」が存在しますから，とりあえずこの仮定を満足することは可能であり，
提示された問題を解くことはできると思います．
後は効率等を求めるならば，用いる方法Mをより良い方法M'に取り換えることを考えれば良いと考えます．
（あなたの言うところの「ナップザック法」がどのようなアルゴリズムかは不明ですが，
それが厳密解を求めることが可能な方法 であれば良い）
>関数にｎ個極値がある場合も同様にｎ個に分解して解くことができるのか？
分割数(n+1かな)が変わっても話は変わらないので，とりあえず解くことは可能かと思います．
…と，長々と書いておいてこんなことを言うのもアレなのですが…
この話題は内容が ある特定の問題を解くための方法 になってしまっており，
「VisualC++ Q&A」というこの場所をこれ以上借りて続けるにはそぐわないものになってしまっているように感じます．
（個人的には興味深い話題ですから他の方法で続けられるならば歓迎ですが…）
そうですか。
どうもありがとうございました。
ナップザック法よりナップザック問題で検索すれば出てくるとおもいます。
ご指摘の通り数学系の板を探して質問しなおすことにします。
数学系だと大学レベルの知識が要求されたり、厳密な定義をして質問しないと怒られるので少し苦手なのですが、そちらにしてみます。
http://www2.ezbbs.net/cgi/reply?id=dslender&dd=07&re=40800
こちらで質問を継続することにしてみました。
ホウジョウウサギさん宜しくお願いします。