パネしり
部活です。 データ量の話。 現状分かっている最大値は206点なので、これを使ってみようと思ったんですが 結局11点,10点を大量に消費してしまうのであまり効果がないみたいですね。 (計算は省きます) ここはスルーして毎回計算したほうがいいのかも･･･？
部活です。 データ量の話です。 ワイルドカードを除いた各パネルの最高点の分布は以下のとおりです。 15点：1枚 14点：4枚 13点：9枚 12点：8枚 11点：14枚 10点：22枚 9点：21枚 8点：11枚 7点：8枚 6点：1枚 この枚数がC(n,r)のnになり、rは1からmax(n, 19…
部活です。 リストアップした組み合わせを保存するために、まずデータ量を計算します。 C(n,r)のとき、データはr個選ばれています。そのため、C(n,r)*r個のデータが存在すると分かります。 少し脱線しますが、C(n,r)*r = C(n, n-r+1)*(n-r+1)であることを証…
部活です。 任意のn, rに対してC(n, r)をリストアップするについて。 適当にググったところ、以下のページに実装がまるっと乗っていました。 選択順が前々回の説明と逆になっていますが、順序を考える必要がないため問題ありません。強いて挙げるとすれば、…
部活です。 前回の続きで、任意のn, rに対してC(n, r)をリストアップするについて。 再帰的にC(n, r)を求められることについては、前回お話しました。 再帰の停止条件についてについては、以下のとおりです。 ①rが0になったとき ②nとrが同値になったとき ①に…
部活です。 ネタはあるけど、書く時間がないですね。別のことして遊んでるだけなんですけど。 だいぶ戻って、部活8の③「決まった同値類の組から、パネルの組を求める」について。理論は高校数学の範囲ですが、順を追っていきます。 パネルの最高点ごとに同値…
部活です。 前回の欠陥について。 正解は、「かぶりを考えていない」です。 例として233点の場合を挙げます。 233点になるパターンは、以下の2パターンあります。 Sa = { 15^1 + 14^4 + 13^9 + 12^4 + 11^1 } Sb = { 15^1 + 14^4 + 13^8 + 12^6 } Saから導け…
部活です。 テーマは変わらず。 19枚の同値類の組を、和が-1になるように選択しなおすについて。 長いのでさっさといきます。 **************************************************************************************** #define PANEL_SEL 20 // パネルの…
部活です。 テーマは変わらず。 はてなだと二重パーレンで注釈になるんですね、Markdown記法というらしい。 知らなかった。 さて、19枚の同値類の組を、和が-1になるように選択しなおすについて。 実は前提条件が抜けていて、和を-1する前に「99枚のパネル群…
部活です。 テーマは変わらず。 99枚のパネルを最高得点の同値類に分け、各得点ごとに枚数をカウントするの実装内容はこんな感じ。一部変数定義は省略。 ①～⑥は、前回・前々回の番号を参照してください。 前回説明したとおり、枚数をインデックスとして使用…
部活です。 テーマは変わらず。 前回記事について「分からない」とご意見いただきましたので簡単に説明します。 (いつもご清覧ありがとうございます。) まず、おさらい。 ①枚数カウント配列を「0」で、同値類配列を「-1」でそれぞれ初期化する ②パネルPのす…
部活です。 テーマは変わらず。 実装について。 まずは 99枚のパネルを最高得点の同値類に分け、各得点ごとに枚数をカウントする について。 リスト構造を使ってもいいのですが、次の2つの理由から配列にします。 ・2次元配列にすると同値類の検索が多少楽に…
部活です。 お題は変わらず。 現在実装中。 他の趣味の空き時間でちょこちょこ書いているので、進みはよくありません。 昔は再帰大好きML人間だったのですが、一応Cで書いてます。 よく言われるのですが、私はコードが汚くて、パッと見何がしたいかわからな…
部活です。 お題は変わらず。 予告どおり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なコードを書いたら目も当てられない時間がかかるので枝刈りとかバックトラックとか入れた…
