第１講～第９講

2014.03.23 第１１講追加

第１講　計算パズル集　　　　レポート（抜粋）　

□ 小町算
    この手の問題は、逆ポーランド記述のストリングをスタックを使って評価するのが普通と考えています。
    しかし、本問題では、括弧の使用が無いため、簡単な再帰関数で解くことができました。
　　　　　ソースプログラム ： les01-ex01-komachizan
　　　　　実行結果　　　　　： les01-ex01-komachizan-log　

□ ナルシスティック数（ナルシスト数）
    ナルシスト数は有限個しか存在しない(最大６１桁）ことは簡単に証明できます。
    意外と簡単にすべてのナルシスト数を求めることができました。（簡単な枝刈と多倍長演算処理が必要）
　　　　　ソースプログラム ： les01-ex03-HPI
　　　　　実行結果　　　　　： les01-ex03-HPI-N61-log　

□ スターリングの公式
    単純な計算では、オーバフローやアンダーフローが発生して精度良く求めることが難しく、工夫が必要です。（これが出題の意図）
　  多倍長演算ライブラリを使うのが普通ですが、ちょっと別のアプローチをしてみました。
　　　　　ソースプログラム ： les01-ex04　　　　　  les01-ex04-99（近似式版）
　　　　　実行結果　　　　　： les01-ex04-log　　　 les01-ex04-99-log　

第２講　平方根計算法　　　　レポート（抜粋：その１、その２）　

　　平方根を求める漸化式には、良く知られたニュートン法の漸化式（２次のオーダーで収束）があります。
　　これより、収束の速い漸化式は作れないのだろうかということで、少し考えて得られたのが、レポートに記載した方法です。
　　このアプローチは、一般のｎ次方程式の根を求める漸化式を導くことができます。

     また、授業では、ニュートン法の２次関数近似を用いた漸化式（３次のオーダーで収束）を学びました。
　　この方法は、２次方程式を解くため平方根を求めます。そのため、初期値によっては虚数になることもありちょっと面倒です。

□ 平方根を求める漸化式
    ３次のオーダーで収束する新しい漸化式です。それとニュートン法の漸化式との比較をおこないました。
　　　　　ソースプログラム ： les02-ex99
　　　　　実行結果　　　　　： les02-ex99-log　

□ 立方根を求める漸化式
    平方根と同じアプローチで３次のオーダーで収束する新しい漸化式を作ってみました。
　　それとニュートン法（２次のオーダーで収束）の漸化式との比較をおこないました。
　　　　　ソースプログラム ： les02-ex98
　　　　　実行結果　　　　　： les02-ex98-log
　　　　　ソースプログラム ： les02-ex04 (ニュートン法による２次関数近似）
　　　　　実行結果　　　　　： les02-ex04-log　

□ 方程式 X**3 - X + 1 = 0 の根を求める漸化式
    同じアプローチで３次のオーダーで収束する漸化式を作ってみました。
　 それとニュートン法（２次のオーダーで収束）の漸化式との比較をおこないました。
　　　　　ソースプログラム ： les02-ex97
　　　　　実行結果　　　　　： les02-ex97-log　

補足：M.HiroiさんのＨＰ（2013.09.29のMemorandum)で平方根の話があり、仙波先生のＨＰを参考文献にあげられています。
そのとき、M.Hiroiさんから漸化式に関する論文（ｄｅｅｐｇｒｅｅｎと同じ漸化式）を教えていただきました。また、計算量という観点から、新しい漸化式とニュートン法（１次近似）とを比較すると、ニュートン法が優位という指摘をいただきました。この点はdeepgreenも納得です。

deepgreenは、floating演算を使うのは大学の演習以来で数十年ぶりです。当時を懐かしく思いだしたりしました。

第３～６講　部分集合生成問題、順列生成の開発Ⅰ、Ⅱ、Ⅲ　　　　レポート（抜粋：その１、その２）　

　　このあたりの講義は、Solver開発で良く使われる関数なので目新しい話はありません。ほんの少し補足しておきます。

□ 部分集合生成問題
    Solverでよく使われるのは、部分集合の要素の数で大分類をして次に個々の要素を並べるという関数です。
　　作り方は易しいので割愛します。

□ 順列生成問題、組合せ生成問題
　　ずいぶん昔になりますが、順列型ハッシュ関数、組合せ型ハッシュ関数およびその逆関数の作り方をM.HiroiさんのHPで教えていただきまし　　　た。　これらの関数は、Solver開発には大変便利な関数で、いまでも重宝しています。

         順列型ハッシュ関数の例 ： hash
 
　　組合せ型ハッシュ関数の使用例として、Hyper-Robot問題(GPCC-2011の課題のひとつ）のSolverを公開します。

　　Robotが４体の場合、すべてのRobotの配置をメモリ上で管理することができるので、それ程難しい問題ではありません。
　　しかし、Robotが５体の場合、すべてのRobotの配置を管理するにはDiskを使わなければならないので、単純に処理することはできません。
    （その都度Diskへのアクセスが入っては性能上大問題です）　 探索アルゴリズムを少し工夫する必要があります。
　　ちょっと面白い問題ですので興味のある方は挑戦してみてください。

　　Hyper-Robot Solver（４体）
　　　　簡単な説明        ： Hyper-Robot-Solver
         ソースプログラム ： HR-max-goal
　　    実行結果　　　　　： HR-max-goal-summary


第７～９講　マッチ棒問題Ⅰ、Ⅱ、発表会　　　　レポート（抜粋：発表資料、詳細）

　　　講義の折り返しということで、各自の解法を発表することになりました。


□ マッチ棒の配置問題
    M 行 N 列に配置されたマッチ棒から ｒ 本のマッチ棒を取り除くとき、孤立点ができないような配置がいくつあるかを求める問題です。
　　発表課題にはなっていませんが、状態遷移行列を作ることができるので高速に解くことができます。
　　この場合、状態遷移行列のメモリ使用量の制約からどこまで解けるかが決まることが多いです。（今回もそうなりました）
　　また、孤立点を判定するビット演算 （setsuzoku) もおもしろいと思います。

　　状態遷移行列を用いた解法プログラム
        ソースプログラム ： les07-ex02-HPI
　　    実行結果　　　　　： les07-ex02-HPI-log

□ マッチ棒問題(課題）
　　課題 ： M 行 N 列に配置されたマッチ棒から ｒ 本のマッチ棒を取り除くとき、s個の正方形が残るような配置の数をもとめよ
　　　　 　　注１：長方形の数は無視する (あってもなくてもよい）
　　　　　　 注２：パラメータが r, s の２つあるのがちょっと面倒です。

    ２週間と少し時間があったので、いくつかの解法を試みました。

    [1] base model
        とりあえず、題意を満たすプログラムを作りました。このプログラムは後続のプログラムの検証用という位置づけです。
　　　 マッチ棒の接続性テストと正方形の数を求める関数をビット演算にしました。

        　　ソースプログラム ： les07-ex03-base
　　    　　実行結果　　　　　： les07-ex03-N5-log

    [2] LBE(Lower Bound Estimater)を用いた高速化
　　　パラメータが r, s と２つあるので、LBEをどのようにつくるのか難しい問題です。もっとも短絡的なのは、ｓ を無視する方法（LBE0)ですが、
　　　やはり、結果は思わしくありません。ちょっと修正しただけで、４．８倍となったのだからOKという見方もあるかもしれませんが。

　　　RSband ： r と s は相反するパラメータです。そこで、σ = ｒ + ｓ という制約を考えました。詳細はレポートを参照されたい。
　　　　　　　　　 （σのような訳の分らない量を使うのは初めてですが、結果的には良好でした）
                      σには、いくつかのバリエーションが考えられます。実際に評価したのは、以下のパターンです。
　　　　　　　　　　　　　LBE1 ：　ｒ＋ｓ
　　　　　　　　　　　　　LBE2 ： 2r+ s
                      　　　LBE3 ：　LBE1 + LBE2 (合わせ技）　

　　　　LBE３を実装したプログラム
         　　ソースプログラム ： les07-ex03-mod14
　　         実行結果　　　　　： les07-ex03-mod14-N6-log

    [3] 部分解合成法(HalfJoin)を用いた高速化
　　　　deepgreenが好きなアプローチです。実装が大変なので気安く取り組めないのが難点です。
        今回はRSbandというLBEの新たな試みと比較する意味で開発してみました。やはり、HalfJoinは強力です。

　　　　HalfJoin最新版
         　　ソースプログラム： les07-ex03-mod160
　　    　　実行結果　　　　　： les07-ex03-mod160-N7-log

   
補足：先生のご興味は、s=0 のとき、ｒ をいくつにすると、解が見つかるかという事でした。　4 x 4 の場合、ｒ = 9 で、１６個の解となります。
        もし、最初から課題がそのようにされていたら、RSbandというアイデアは生まれなかったでしょう。　　　
       deepgreenにとって、RSbandという新しい考え方を得ることができたのは大きな収穫でした。

        s = 0 に限定して探索した結果
　　　　    [ M,N]    (s,  r)         解の数　　　　　　　探索時間
        ---[ 6, 6] / ( 0,19)  :        16   (    1761)          20 msec
        ===[ 6, 6]                                  total    　   104 msec

        ---[ 7, 7] / ( 0,26)  :       544   (  163767)      1617 msec
        ===[ 7, 7]                                  total         2197 msec

        ---[ 8, 8] / ( 0,33)  :        16   (    5413)         960 msec
        ===[ 8, 8]                                  total        5556 msec

       ---[ 9, 9] / ( 0,42)  :       672   ( 1107541)    94491 msec
       ===[ 9, 9]                                  total      134411 msec

      ---[10,10] / ( 0,51)  :        16   (   12242)     29815 msec
      ===[10,10]                                  total     377526 msec

     先生は、M,Nが偶数のとき解の数が１６になっていることを気にしておられました。何か必然性がありそうな感じです。

　　第１０講　カタラン数　　　・ ・ ・  特になし

第１１講　畳敷詰問題Ⅰ、Ⅱ　　　　レポート（抜粋）

　　
□ 状態遷移行列を用いた解法
    あまり多くはないのですが、状態遷移を行列で表現できる場合があります。その場合、問題を高速に解くことができます。
　  今回の問題はそのようなケースです。　おそらく、通常の探索法では２０ｘ２０の畳敷詰問題を解くことができないでしょう。

　　Solverを作る時、選択枝の１つとしてちょっと考えてみるのも面白いでしょう。　  

　　    畳敷詰問題のSolver(状態遷移行列を用いた解法プログラム)
              ソースプログラム ： les11-ex99-BSE
　　         実行結果　　　　   ： les11-ex99-BSE-log

Home
Up
Back
 Next