部活3

部活です。

テーマは前回と同様最高点についてです。

今回は1回目でも触れた局所最適解について。

動的計画法などでは局所最適解を利用してボトムアップで解を求めると思います。

これについてパネしりで1つ単純な例を考えてみると・・・

パネルを1枚選ぶとき、各先頭文字に対する最長の読みが最適解となるはずです。この解を利用して、2枚、3枚と長いものを繋げていく...という具合です。

しかし、これは成立しません。同じパネルが2回使えないからです。

一番簡単な反例として、「なわ」のパネルを挙げます。

「なわ」のパネルには「市中引き回し」の13点読みがあります。

これは先頭文字「し」のパネル1枚での最長の読みです。

末尾文字も「し」ですが、もう「なわ」のパネルは使えないため、「し」1枚からなる最適解が全く意味をなさないことになります。

ということで局所解を利用するのであれば、選択済みのパネルの部分集合を用いた方針になると思いますが、探索中の選択をすべて記憶する必要があるため、メモリ使用量との戦いになると考えられます。

今日はここまで。

次回は枝刈りについて書く予定。