いつ家を買うか。 - にゃんしーの。

勉強の合間にちらっと休憩がてら。

誰しも、あれじゃないですか。
家の購入については必ず考えるじゃないですか。
おそらく。

そんで、こう考える。

「いつ家を買うのが適切か？」

30歳？40歳？
難しいですからね。
最近は地震とか天災にも敏感やし
それでなくても転勤とかあるかもしれない。

何が起こるか予測できない問題に対して
一般に良いとされる解を与えるのが「オンライン問題」です。

オンライン問題では、まずその問題をどう解決するかのアルゴリズムを与えます。
次に、そのアルゴリズムを取った場合のワーストケースでのコスト（WST）を考える。
次に、そのワーストケースにおける最良のアルゴリズムのコスト（OPT）を考える。
WST/OPTを競合比として定義すれば、
これが小さければ小さいほど良いアルゴリズムと云うことができます。
（最小の競合比は１）

今回の家を買う問題では、まず問題を下記のように定義します。

家を借りた場合の年間の家賃は100万円
家を買った場合の購入費は2000万円
家はなんらかの理由により手放さなければならない可能性がある
年数は50年とする

最初に思いつくアルゴリズムとして、下記があります。

（アルゴリズム１）すぐに家を買う

ワーストケースですが、これは家を買うたびにすぐ手放さないといけない場合。
この場合のコストは、2000万円が50年分かかりますので、
WST=2000*50=100000万円となります。
最良のアルゴリズムは、家を全く買わないこと。
この場合のコストは、賃料の100万円×50年分ですので
OPT=100*50=5000万円
競合比は、100000/5000=20

すぐに家を買う場合の競合比は20。
一般に見て、これは非常に悪い数字です。

（アルゴリズム２）常に家を借りる

ワーストケースですが、家を手放すイベントが全く起こらなかった場合。
この場合のコストは、100万円が50年分かかりますので、
WST=100*50=5000万円となります。
最良のアルゴリズムは、すぐに家を買うこと。
この場合のコストは、2000万円だけで済みます。
OPT=2000万円
競合比は、5000/2000=2.5

常に家を借りる場合の競合比は2.5。
改善されましたが、あまりいい数字ではありません。

（アルゴリズム３）y年後に家を買う

ワーストケースですが、y年後に家を手放すイベントが起こった場合。
この場合のコストは、家の費用2000万円と、
さらに賃料の100万円も50年分かかります。
（買った家がすぐ無駄になるわけなので）
WST=2000+100*50=7000万円となります。

最良のアルゴリズムは、yの値について分けて考えなくてはなりません。

・0≦y≦20

比較的早めに家を手放すイベントが起こる場合は、
それまでは借家で過ごし、イベント後すぐに家を買うのが最適です。
つまり
OPT=100*y+2000

競合比は7000/(100*y+2000)で、
y=0のとき3.5
y=10のとき約2.7
単調減少で
y=20のとき1.75で最小となります

・30≦y≦50

比較的遅めに家を手放すイベントが起こる場合は、
いきなり家を購入し、イベント後は借家で過ごすのが最適です。
つまり
OPT=2000+(50-y)*100

競合比は7000/{2000+(50-y)*100}
y=30のとき1.75
y=40のとき約2.7
単調増加で
y=50のとき3.5で最大となります。

・20≦y≦30

中間のケースにおいては、
最初に家を購入し、家を手放すイベント後にも家を購入するのが最適です。
つまり
OPT=2000+2000=4000

競合比は7000/4000=1.75

このアルゴリズムにおいては、20年から30年後に家を購入するのが
競合比1.75で最適ということになります。

（アルゴリズム４）複数回家を買う

アルゴリズム３では、１回だけ家を購入しましたが、
複数回家を購入する場合はどうでしょうか？
20年後と、40年後に購入するとか。

この場合のワーストケースは、
購入するたびに家を手放すイベントが発生する場合です。
コストとしては、家２回購入分の費用（2000万円×2）と、結局50年分の賃料がかかります。
WST=2000*2+100*50=9000

最適なアルゴリズムについては、明確には検証しませんが、
どんなにコストがかかっても、常に借家で済ませる場合のコストよりも
悪くなることはありません。
つまり
OPT≦100*50=5000

ですので、競合比は9000/5000=1.8以上になります。

以上より、20年から30年後に家を買うのが
競合比1.75で最適ということになります。

問題の年数を50年としましたが、これはつまり30歳時点で見た場合のモデルプランです。
つまり、50歳から60歳時点で家を購入するのが最適ということになります。
これより早いほど、あるいは遅いほど、オンライン問題の計算上は最適値から離れていきます。

あくまで「オンライン問題」の範疇のことですので
遥かに複雑な、実際の人生プランにまで解を与えられるものではありません。
ただ、ひとつの考え方としては、なかなか興味深いものだと思います。

さて、勉強に戻ろ。