[PR]澱涅:芹臆f

Re:1千万解です。でも全解にはほど遠い。


[ インデックス ] [ ホームページ ]

In Reply to: 1千万解です。でも全解にはほど遠い。
投稿者:daichon - 投稿日時:2001年03月09日 20時58分40秒

> 1千万解、ようやく計算できました。

読んではいたのですが、なかなか返事を書く時間が取れませんでした。お疲れ様です ( −> PC? )

> 全解を見積もってみると、以下のようになります。
>
> 残りの15ピースのもつ方向の平均を6と仮定すると、残りの解の
> 可能性は以下になります。
>  6^15 = 4.70184984576E11

この15ピースは35個の内から任意に選べることが計算に入っていない様に思いますがいかがでしょうか?

  35個から任意の15個を抜き出す組合せ 
  (35x34x33x..x21) / (15x14x13x..x1) = 3.2E9

次ぎに、ある15個で特定のひとつの形を作る組合せは暇人さんの例では、2.6E3 あります。これが平均的なケースかはわかりませんが、現状ではとりあえずそう仮定します。

この15個でいくつの異型が作れるかは不明ですので M とします。

すると全解は
 3.2E9 * 2.6E3 * M * 2 * 1.0E7 * 1/2 = 8.3E19 * M

ということで、前回の見積り 1.65E20 * N に近い結果になります。

> 全解は、1.0E17 〜 1.0E19 (10京〜1000京)の間くらいではない
> でしょうか。今回7日かかった1千万解が、仮に1秒で解けたと
> 32年〜3200年かかる計算になります。
> ちょっとお手上げ(^_^;;

いずれにしても、枝刈り、プログラム的な高速化、複数CPUによる分割処理等での、力づく(CPUのパワーづく?)でのアプローチではせいぜいこの1万倍(1E11解?特に根拠はありません)程度が限界で、全解にたどり着けないのは明確になりましたね。

あとは、いかに同形を利用して実際の計算を削減できるかでしょうか?その為に
 ・最適な分割方法
 ・効率良く同形を見つける方法
等を探し、残りの9桁分(10億倍!!)の効率化が図れないと、推定の精度を上げることはできても全解は迷宮入りになってしまいますね。

いずれにしても、このHPを立ち上げて、もう少しで50日、アクセス1000、掲示板書きこみ件数100がそれぞれ近づき、次へのステップへの一区切りとしてはちょうど良いタイミングにも思えます。

ここまでの結果として、もう少し処理を進めたいと考えていますが、だいぶ長くなったのでここで一度切ります。


この投稿へのコメント

GeoCities

[PR]
舗縦丑餅lC嗣烱叺:餅閑惘I2980~