お気づきの点や感想要望などなんでもＯＫ！
1+(1+2)+(1+2+3)+・・・+(1+2+3+・・・＋n)→ANS という計算を2重ループを使ってフローチャートで表せ。という問題なんですが分かりません。誰か教えてください。おねがいします。
こんにちは。 パズルは面白いですね。
今晩は、塗り壁です。高橋謙一郎さん、deepgreenさん、 残念ですがしょうがないですね。何か面白い話が有りましたら、 ここで紹介させてもらいます。 ＞この世界はＣマガ電脳クラブを通して我流で勉強した程度なので知識的 ＞ にあまりに無能な自分をわきまえることにしました。 大分謙遜していらっしゃいますが、問題は知識よりも理解力と、論理の構成力 だと思いますので、かき回して欲しかったのに。
昨日は重箱の隅をつついた様な理論を書きましたが今回はその実験編を報告します。 ただし、気力も薄れてきたのでいろいろなケースについてテストした結果ではあり ませんので、ここでの報告には改善も改悪もいろいろあると思います。 そもそもこのダメ押しは悪魔の配置を攻略するのが目的で、究極問題のチェッカー ソルバーとしては悪魔の配置とは程遠いタイプがほとんどなのでここでのノウハウは たぶん不要だと思われます。私のテストした限りではＩＤ(InvertDistance)も捨てて ＷＤ(WalkingDistance)だけで解かせた方が究極問題のチェッカーソルバーとしては 良好な結果が出ています。ＩＤは親局面からの差分のみで求められるものの計算が ちょっと重いのだろうと思います。 さて、私がテストに用いたＤＢは下図のＬＤＢ(LocalDataBase)タイプの２つです。 悪魔の配置をもろに意識した形になっていて、としひでさんのＯＤ(ObliqueDistance) と、とても類似しています。実のところ私の理想はとしひでさんのＯＤなのですが ＯＤだと完全ハッシュ値を求める方法が私には判らなかったので(どなたか分る人はいま せんか)、やむなくこのようなＬＤＢを用いることにしただけのことです。 [DB1] [DB2] ＢＡＡＡ ＡＡＡＢ ＣＢＢＡ ＡＢＢＣ ＣＢＢＡ ＡＢＣＣ ＣＣＣ□ ＢＣＣ□ MAX=56 MAX=58 やはりＷＤの性能がとても良いのでＩＤは捨てています。さらに、探索開始時あるいは 探索途中に、このＬＤＢから得られる下限値がＷＤの下限値を下回ってしまった場合も 動的にＬＤＢの使用を捨てるようにしています。だから悪魔の配置に類似している問題 の場合にしか使われることのない制御構造ですが、悪魔の配置と類似していない問題で の性能が低下することを恐れたためです。 残念ながら実行結果は「依然として遅い」ということになりましたが２１時間は大きく 下回っているので取り合えずは「よし」としておきました。 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0 (WD=40,DB1=54,DB2=0) LowerBound=54 [72 moves] time=12416sec (約３時間２７分) 15 14 13 9 10 13 14 11 13 14 11 15 12 13 7 8 13 7 14 6 8 3 4 13 7 14 6 8 5 10 8 6 3 4 2 5 6 3 4 2 5 6 3 4 15 11 9 8 4 9 8 4 10 3 2 7 14 15 9 10 3 2 7 9 10 7 6 5 9 10 11 12
この考えは１５パズルというよりも反復深化と下限値枝刈りの関係について考察 したもので「ＰＤＢ等を参照するという重い処理」で下限値枝刈りをする場合の コストの軽減化に関するものです。枝刈り判別式は、 depth + LowBound > MAX_DEPTH depth = 現在の深さ LowBound = 以後最低限必要な手数 MAX_DEPTH = 今回の深さ制限 です。さて、初期状態でLowBound=40だったとします。MAX_DEPTHは何度か反復 を繰り返し、次ぎの探索での深さ制限はMAX_DEPTH=50だったとします。 では最初にとても重要な着目点を明記しておきます。 「下限値は親局面に対して−１〜＋１の値しか取れない」 これはLowBound関数がどのような行程で作ったのかを考えれば一目瞭然です。 すると一番最初に枝刈りが発生する可能性のある地点は最悪の進路を辿った 場合であり、親局面の下限値に単純にプラス１していって、枝刈り判別式が 成立する最初の地点になります。 [Fig.1] depth + LowBound = 計算結果 0 40 40 1 41 42 2 42 44 3 43 46 4 44 48 5 45 50 6 46 52 <- ここでMAX_DEPTHを超えた 結局、depth=5以下での枝刈りは「絶対に有り得ない」ことになります。 だから、この範囲で下限値を求めて判別式を調べるという重い作業は全く 無駄であったということになります。 depth=6になった時に初めて下限値を調べて判別式を適用すれば良いのです。 そしてさらに、ここで実際の下限値がLowBound=42だったとすれば、 [Fig.2] depth + LowBound = 計算結果 6 42 48 7 43 50 8 44 52 <- ここでMAX_DEPTHを超えた となり、次に枝刈りを調べる価値のある地点はdepth=8になります。 このように「枝刈りを調べる地点はスキップ出来る」のです。従来のように 新たな局面を作るたびに枝刈りを調べる方法とこの方法は等価な結果を得ら れるので「ＰＤＢ等を参照するという重い処理」で下限値を求めなくては ならない場合には大変に有効な手段だと思われます。 次にLowBound関数には最大値があることに着目して下さい。使用している LowBound関数の最大値が44だったとすれば[Fig.1]はさらに改善されdepth=6 以下での枝刈りは「絶対に有り得ない」ことが分かります。 [Fig.1の改] depth + LowBound = 計算結果 0 40 40 1 41 42 2 42 44 3 43 46 4 44 48 5 44 49 6 44 50 7 44 51 <- ここでMAX_DEPTHを超えた 以上の方法を採用することによりＰＤＢやＬＤＢを導入しやすくなります。
塗り壁さん、こんばんは。バタバタして返事がおくれました。 「ゲーム情報学研究会」にはとても関心があります。 一発、乗り込んで掻きましてやろうかという気持ちもあったのですが、 この世界はＣマガ電脳クラブを通して我流で勉強した程度なので知識的 にあまりに無能な自分をわきまえることにしました。
蟻が１０さん、返事が遅れてすみません。 「ちっとだけぬけてるところがある」と言われるととても気になる のですが、蟻が１０さんの暗号文がまったく解読できません。 最初の文が「２」次の文が「３」に関係するのかなとは思ったので すが何ともその先に進めません。 「ぬけてるところ」って何なのかズバリ教えていただけませんか。
nomadさん、こんばんは。 ボードに市松模様を付ければ、荷押回数や歩数が偶数か奇数かく らいは判別出来るかも知れません。ただし、それで探索量を減ら せる方法があることは思い付けていません。 もしかしたら、この掲示板で最近話題になっている１５パズルの ように反復深化を使っているのだろうと思われたのでしょうか。 だとすれば、それは違います。私の倉庫番ソルバーは総て幅優先 をベースにしています。メモリを贅沢に使用する分だけ探索量は １／２とか１／４の比ではなく反復深化の何百倍も探索量を軽減 させていると思います。反復深化を採用するなら確かに偶奇性を 考慮することは常套手段でもあるし有効な方法だと思います。 しかし、幅優先タイプの探索を用いるなら解が偶数と判っていた としても奇数手目の配置は避けて通れない重要な集合グループな ので偶奇性を適用させるのは困難なことかなと思っています。 私の言っていることが全くマト外れの意見だとすれば、もっと詳 しい情報を是非とも教えて頂きたいと思います。いつかまた倉庫 番ソルバーの開発に帰る日が来ると思っていますので何でもいい からアイデアを拝聴いただければ嬉しいです。
はじめまして。 倉庫番を解く(Ver2.7) に質問があります。 私はＣ言語＆ｊａｗａには精通していないのでコードを見てもよく分からないのですが、 このＳｏｌｖｅｒでは、 『現在の局面が、荷物を奇数回押した状態なのか、偶数回押した状態なのかを考えていない』 ように思うのですが、違いますか？ もし考えていないんだったら、そこを改良する事で、探索量を１／４くらいには 減らせる様な気がするのですが・・・。 私がなぜそう思うのか、もう少し情報が必要ならお知らせください。 では。
当ＨＰのCGI関連(ゲームコーナーとこの掲示板)が週末の間ずっとサーバーの故障により 正常に動作しなくなっていましたが無事復旧したようです。私のCGIはHTML形式ファイル を直接作成する仕組みの他、怪しげに手の込んだ自己流の構造を持たせていた為にプロ バイダーのエンジニアの方をわずらわせてしまったようです。 15パズルソルバーに新たな展開があるのですが、実験結果も必要なので２・３日後に改 めて報告したいと思います。(ただ文章だけで説明できるかどうか....)