読者です 読者をやめる 読者になる 読者になる

糸電話式のアレ

プログラミングのこと。毎日のこと。書いています。

Haskellでお題を解こうとしたらわりかし難しい件について(その2)

Haskell プログラミング

状況が改善したので報告です。
あるいは、コレで完成かもしれません。

戦略がある(キリッ)と言っていたのは結局ダメでした

前回の報告の最後で、戦略がある(キリッ)と言っていたのは結局ダメでした。

前回の処理

前の報告のプログラムでは、
「正方形に並んだセルのリスト(以下フィールド)」を作る方法として、
以下の処理を行なっています。


  1. 「最初にフィールドを、全ての経路への移動を許可されたダミーセルで満たす」

  2. 「ランダムに移動を不許可にしたランダムセルを一つ、同じ位置にあるダミーセルと入れ替える」

  3. 「全てのセルから全てのセルへ移動できるかどうか」を判定する

  4. 「もし、判定が成功すれば、セルはフィールドに残す。判定が成功しなければ、ランダムセルを選びなおし3へ戻る」

  5. 「ダミーセルがあるかぎり1へ戻る」


ということをやっています。
コレだと、一個ずつを確定させている必要があるので、処理時間がめちゃんこかかってダメでした。

ダメだった戦略


で、戦略がある(キリッ)とか言っていたのは、メモ化です。
4の部分が一番計算量が多いので、この部分の演算結果をひたすら
メモリに貯めようとしたのですが、(これは演算方法が悪い為ですが)
不成功な計算でもメモしなくちゃならんのでリソース不足になってしまいました。

正解にたどり着ける戦略、それは運を味方につけること

そこで、あまりスマートな方法ではないため最初敬遠していた方法を取りました。


  1. 「最初にフィールドをランダムセルで埋める」

  2. 「全てのセルから全てのセルへ移動できるかどうか」を判定する

  3. 「もし、判定が成功すれば、計算終了。判定が成功しなければ1へ戻る」


ぶっちゃけ運まかせです。


ただし、この方法だと運が良ければ一発で計算が終了します。
そして、試してみると大抵の場合において、最初の方法よりも効率がよくフィールドが決定できます。

なお、下記のプログラムで10×10を求めるのは、
PCによっては現実的な計算時間では終わらないのでご注意ください。

プログラム全体