ホームページへ戻る  書き込みリストへ戻る
「コンピュータ&パズル」訪問者の自由メッセージコーナー

お気づきの点や感想要望などなんでもOK!


至急お願いします 投稿者:kal  投稿日:06月03日(日)21時39分50秒

1+(1+2)+(1+2+3)+・・・+(1+2+3+・・・+n)→ANS という計算を2重ループを使ってフローチャートで表せ。という問題なんですが分かりません。誰か教えてください。おねがいします。


初めまして。 投稿者:ROKIKI  投稿日:05月23日(水)12時27分25秒

こんにちは。
パズルは面白いですね。

http://rokiki.hoops.ne.jp


re:いっしょにどうですか 投稿者:塗り壁  投稿日:04月20日(金)01時44分45秒

今晩は、塗り壁です。高橋謙一郎さん、deepgreenさん、
残念ですがしょうがないですね。何か面白い話が有りましたら、
ここで紹介させてもらいます。
>この世界はCマガ電脳クラブを通して我流で勉強した程度なので知識的
>      にあまりに無能な自分をわきまえることにしました。
大分謙遜していらっしゃいますが、問題は知識よりも理解力と、論理の構成力
だと思いますので、かき回して欲しかったのに。


15Puzzle(下限値枝刈りのスキップ化) 投稿者:高橋謙一郎  投稿日:04月19日(木)21時27分53秒


昨日は重箱の隅をつついた様な理論を書きましたが今回はその実験編を報告します。
ただし、気力も薄れてきたのでいろいろなケースについてテストした結果ではあり
ませんので、ここでの報告には改善も改悪もいろいろあると思います。

そもそもこのダメ押しは悪魔の配置を攻略するのが目的で、究極問題のチェッカー
ソルバーとしては悪魔の配置とは程遠いタイプがほとんどなのでここでのノウハウは
たぶん不要だと思われます。私のテストした限りではID(InvertDistance)も捨てて
WD(WalkingDistance)だけで解かせた方が究極問題のチェッカーソルバーとしては
良好な結果が出ています。IDは親局面からの差分のみで求められるものの計算が
ちょっと重いのだろうと思います。


さて、私がテストに用いたDBは下図のLDB(LocalDataBase)タイプの2つです。
悪魔の配置をもろに意識した形になっていて、としひでさんのOD(ObliqueDistance)
と、とても類似しています。実のところ私の理想はとしひでさんのODなのですが
ODだと完全ハッシュ値を求める方法が私には判らなかったので(どなたか分る人はいま
せんか)、やむなくこのようなLDBを用いることにしただけのことです。

     [DB1]             [DB2]
     BAAA          AAAB
     CBBA          ABBC
     CBBA          ABCC
     CCC□          BCC□
     MAX=56            MAX=58

やはりWDの性能がとても良いのでIDは捨てています。さらに、探索開始時あるいは
探索途中に、このLDBから得られる下限値がWDの下限値を下回ってしまった場合も
動的にLDBの使用を捨てるようにしています。だから悪魔の配置に類似している問題
の場合にしか使われることのない制御構造ですが、悪魔の配置と類似していない問題で
の性能が低下することを恐れたためです。

残念ながら実行結果は「依然として遅い」ということになりましたが21時間は大きく
下回っているので取り合えずは「よし」としておきました。

  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  (約3時間27分)
 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


15Puzzle(下限値枝刈りのスキップ化) 投稿者:高橋謙一郎  投稿日:04月18日(水)21時00分58秒


この考えは15パズルというよりも反復深化と下限値枝刈りの関係について考察
したもので「PDB等を参照するという重い処理」で下限値枝刈りをする場合の
コストの軽減化に関するものです。枝刈り判別式は、

       depth + LowBound > MAX_DEPTH
                                  depth     = 現在の深さ
                                  LowBound  = 以後最低限必要な手数
                                  MAX_DEPTH = 今回の深さ制限

です。さて、初期状態でLowBound=40だったとします。MAX_DEPTHは何度か反復
を繰り返し、次ぎの探索での深さ制限はMAX_DEPTH=50だったとします。
では最初にとても重要な着目点を明記しておきます。

 「下限値は親局面に対して−1〜+1の値しか取れない」

これはLowBound関数がどのような行程で作ったのかを考えれば一目瞭然です。
すると一番最初に枝刈りが発生する可能性のある地点は最悪の進路を辿った
場合であり、親局面の下限値に単純にプラス1していって、枝刈り判別式が
成立する最初の地点になります。

[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になります。
このように「枝刈りを調べる地点はスキップ出来る」のです。従来のように
新たな局面を作るたびに枝刈りを調べる方法とこの方法は等価な結果を得ら
れるので「PDB等を参照するという重い処理」で下限値を求めなくては
ならない場合には大変に有効な手段だと思われます。

次に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を超えた

以上の方法を採用することによりPDBやLDBを導入しやすくなります。


re:いっしょにどうですか 投稿者:高橋謙一郎  投稿日:04月17日(火)23時03分00秒

塗り壁さん、こんばんは。バタバタして返事がおくれました。

「ゲーム情報学研究会」にはとても関心があります。
一発、乗り込んで掻きましてやろうかという気持ちもあったのですが、
この世界はCマガ電脳クラブを通して我流で勉強した程度なので知識的
にあまりに無能な自分をわきまえることにしました。


re:蟻が10さん 投稿者:高橋謙一郎  投稿日:04月17日(火)23時02分10秒

蟻が10さん、返事が遅れてすみません。

「ちっとだけぬけてるところがある」と言われるととても気になる
のですが、蟻が10さんの暗号文がまったく解読できません。
最初の文が「2」次の文が「3」に関係するのかなとは思ったので
すが何ともその先に進めません。

「ぬけてるところ」って何なのかズバリ教えていただけませんか。


re:倉庫番を解く(Ver2.7) に質問。 投稿者:高橋謙一郎  投稿日:04月17日(火)22時10分15秒

nomadさん、こんばんは。

ボードに市松模様を付ければ、荷押回数や歩数が偶数か奇数かく
らいは判別出来るかも知れません。ただし、それで探索量を減ら
せる方法があることは思い付けていません。

もしかしたら、この掲示板で最近話題になっている15パズルの
ように反復深化を使っているのだろうと思われたのでしょうか。
だとすれば、それは違います。私の倉庫番ソルバーは総て幅優先
をベースにしています。メモリを贅沢に使用する分だけ探索量は
1/2とか1/4の比ではなく反復深化の何百倍も探索量を軽減
させていると思います。反復深化を採用するなら確かに偶奇性を
考慮することは常套手段でもあるし有効な方法だと思います。

しかし、幅優先タイプの探索を用いるなら解が偶数と判っていた
としても奇数手目の配置は避けて通れない重要な集合グループな
ので偶奇性を適用させるのは困難なことかなと思っています。

私の言っていることが全くマト外れの意見だとすれば、もっと詳
しい情報を是非とも教えて頂きたいと思います。いつかまた倉庫
番ソルバーの開発に帰る日が来ると思っていますので何でもいい
からアイデアを拝聴いただければ嬉しいです。


倉庫番を解く(Ver2.7) に質問。 投稿者:nomad  投稿日:04月17日(火)19時42分31秒

はじめまして。
倉庫番を解く(Ver2.7) に質問があります。

私はC言語&jawaには精通していないのでコードを見てもよく分からないのですが、
このSolverでは、
『現在の局面が、荷物を奇数回押した状態なのか、偶数回押した状態なのかを考えていない』
ように思うのですが、違いますか?

もし考えていないんだったら、そこを改良する事で、探索量を1/4くらいには
減らせる様な気がするのですが・・・。

私がなぜそう思うのか、もう少し情報が必要ならお知らせください。

では。


サーバが復旧しました。 投稿者:高橋謙一郎  投稿日:04月16日(月)22時00分40秒

当HPのCGI関連(ゲームコーナーとこの掲示板)が週末の間ずっとサーバーの故障により
正常に動作しなくなっていましたが無事復旧したようです。私のCGIはHTML形式ファイル
を直接作成する仕組みの他、怪しげに手の込んだ自己流の構造を持たせていた為にプロ
バイダーのエンジニアの方をわずらわせてしまったようです。

15パズルソルバーに新たな展開があるのですが、実験結果も必要なので2・3日後に改
めて報告したいと思います。(ただ文章だけで説明できるかどうか....)


 ホームページへ戻る  書き込みリストへ戻る