部活です。 お題は変わらず。 予告どおり99枚のパネルから最高得点の部分和がS-pとなるような19枚のパネル群を抽出することについて。ナップサック問題の特殊な例と考えることができます。 ①品物(パネル)は99個 ②各品物には価値(最高得点)と重さ(すべて1)が…

部活です。 テーマは変わらず。 今までそれらしい計算式でそれらしいことを並べてさて実装、なんて言っていましたが、根本的に間違っている点があります。それは、計算を削減すべき場所です。 以前99C19*43*20!という計算式を示しましたが、いままでの枝刈り…

部活です。 テーマは変わらず(省略)。 実装の前に、前回の枝刈りの有効性について。 どれくらいの効率化が期待できるかということについて少し計算してみます。 前回枝刈りの数字として出したのが「20枚で206点」ですから、ワイルドカードの6点を引き200、こ…

雑記です。 今更撮り溜めてたプラメモを消化しました。 いつのだよ、って言われると思うので言っておくと、ちょうど去年の今頃に終わったアニメです。 なんだか評判良くなかったけど、クソアニメ慣れしてるからなのか「言うほどか？」という感じでしたね。 …

部活です。 テーマは前回と同様最高点についてです。 予告どおり枝刈りについて。 枝刈りは、その名のとおり不要な(通っても無駄な)枝を切る(調査しない)ことで、計算量を減らすものです。 重要なのは不要だという判断はどのように行うかです。 この判断が間…

部活です。 テーマは前回と同様最高点についてです。 今回は1回目でも触れた局所最適解について。 動的計画法などでは局所最適解を利用してボトムアップで解を求めると思います。 これについてパネしりで1つ単純な例を考えてみると・・・ パネルを1枚選ぶと…

部活です。 テーマは前回と同様最高点についてです。 その前にパネしりの制約について述べておきます。 ①99枚のパネルから19枚がランダムに、1枚が常に選ばれる(計20枚)。 ②各パネルは最大43の読み(先頭文字、末尾文字、長さ(得点)、難度(3段階)の4要素)を持…

部活です。 今のテーマは 「パネしり」の最高得点は何点か？ です。 パネルを頂点とみなすと重みつき最長単純道問題でNP困難だと思います。 何のひねりもない再帰Likeなコードを書いたら目も当てられない時間がかかるので枝刈りとかバックトラックとか入れた…