M.Hiroi's Home Page

Guest Book Log

[ Home ]

120.完全ハッシュ関数の逆関数

投稿者:高橋謙一郎 - 2000年 12月 21日 20時 32分 53秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.5; Windows 98; Win 9x 4.90)
メールアドレス:takaken@ic-net.or.jp


広井さん、deepgreenさん、鎌田さん こんばんは。
お久しぶりです。コンピュータ&パズルの高橋です。
完全ハッシュ関数は面白いですね。とても勉強になりました。

ところで、完全ハッシュ値から逆算して元の状態を復元できる
逆関数があれば「局面を保存する場所は不要」になりますね。
メモリが不足する場合などには便利に使えると思います。
さっそく作ってみたのが下のコードですが、組合せ型の最後の
2行は若干の不安が残ります。

/* 順列型の完全ハッシュ逆関数(広井さんのコードより) */
void change_board(int value, char *board)
{
  int i, j;
  for (i=0; i<SIZE-1; i++) {
    board[i] = value / fact_table[i];
    value -= fact_table[i] * board[i];
  }
  board[i] = 0;
  for (i=SIZE-2; i>=0; i--) {
    for (j=i+1; j<SIZE; j++)
     if (board[i] <= board[j]) board[j]++;
 }
}
/* 組合せ型の完全ハッシュ逆関数(鎌田さんのコードより) */
void ncr2inv(int n, int r, int value, char *p)
{
  int c;
  n--;
  c = ncr(n, r); /* nCr */
  while (n>=r && r>0) {
   if (value / c) {
     value -= c;
     c = (c * r) / (n - r + 1); /* nC(r-1) */
     r--;
     *p++ = 1;
   } else {
     *p++ = 0;
   }
   c = (c * (n - r)) / n; /* (n-1)Cr */
   n--;
  }
  for (n++; n; n--)
    *p++ = (n > r)? 0: 1;
}

119.KaMemo

投稿者:M.Hiroi - 2000年 12月 21日 18時 42分 00秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geicoties.co.jp

xyzzy の作者である亀井さんのホームページでは、
リンク先ホームページの紹介のほかに、コメントがつく場合が
あります。これを KaMemo [(C) Toy] といいます。

このたび、私のところにもついに KaMemo が書いてありました。
よっしゃー! さて内容はなんだろうと読んでみたら、

あうあう、そうでした。defmacro はそれが使えるのね(笑)。

ということで、「xyzzy Lisp:マクロ」を更新しました。
亀井さんに感謝です!

118.うさぎと犬

投稿者:M.Hiroi - 2000年 12月 12日 22時 16分 22秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

>少し前のCマガに「うさぎと犬」というゲームの問題がありました。
>丁度、状態の数が少ないので使えそうです。

Cマガジン10月号ですね。なるほど、組み合わせが使えそうです。
解答発表は次号(12/18発売予定)なので、どんなプログラムが掲載
されるか楽しみです。

思考ゲームといえば、ミニマックス法+αβ枝刈りが定番アルゴリズム
ですが、例題にぴったりのゲームがあります。8行8列に+と-の数字
が配置されていて、その数字を取り合うもので、名前が「MinMax」だっ
たはずです(笑)。これは簡単にプログラムできるので、そのうちに
紹介したいと思います。

117.re^8:組み合わせ

投稿者:deepgreen - 2000年 12月 12日 21時 00分 48秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

こんばんは、deepgreenです。

少し前のCマガに「うさぎと犬」というゲームの問題がありました。
(先手必勝なのでその手順をもとめよというもの)
丁度、状態の数が少ないので使えそうです。それに、α・β枝刈りも解説が
ありましたし、ぴったりの問題かもしれませんね。

116.re^7:組み合わせ

投稿者:M.Hiroi - 2000年 12月 10日 18時 04分 43秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

鎌田さん、deepgreen さん、こんばんは。

せっかく良い方法を教えてもらったのですから、
実際のパズルの解法に応用してみたいですね。
逆に、そのようなパズルを考えてみるのも
面白いかもしれません(笑)。

115.re^6:組み合わせ

投稿者:deepgreen - 2000年 12月 09日 21時 43分 34秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

kamadaさん、広井さん こんばんは。 deepgreenです。

どうもありがとうございます。意外と簡単にできましたね。
チャンスがあれば、どこかで利用してみます。

114.re^5:組み合わせ

投稿者:M.Kamada - 2000年 12月 09日 15時 48分 17秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.01; Windows 98)
メールアドレス:m_kamada@nifty.com
ホームページ:http://homepage2.nifty.com/m_kamada/index.htm

広井さん、こんにちは。

>最上位ビットが0の場合、ncr(7,4)=35 通りの組み合わせがあるので、
>0 - 34 の数値を割り当てる、1の場合は残りの組み合わせが
>ncr(7,3)=35 通りあるので、35 - 69 の数値を割り当てる、
>あとは各ビットに対してこれを繰り返せば求めることができる、
>というわけですね。

そうそう、そんな感じ。
パスカルの三角形の上の経路に番号を振っているだけです。

下の位からやったほうがncr(n,r)を計算しなくて済むぶん速いかも。
そうすればncr(n,r)の計算中のオーバーフローを気にしなくて済むし。

113.re^4:組み合わせ

投稿者:M.Hiroi - 2000年 12月 09日 14時 30分 24秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

鎌田さん、こんにちは。

>nCrの組み合わせを0~(nCr)-1の番号に変換する方法ですが、
>基数変換の応用で簡単にできます。

書き込み、ありがとうございます!

最上位ビットが0の場合、ncr(7,4)=35 通りの組み合わせがあるので、
0 - 34 の数値を割り当てる、1の場合は残りの組み合わせが
ncr(7,3)=35 通りあるので、35 - 69 の数値を割り当てる、
あとは各ビットに対してこれを繰り返せば求めることができる、
というわけですね。

なるほど、納得しました。さすが鎌田さんです。
目からウロコが落ちました(笑)。
素晴らしい方法を教えていただき、大感謝です。

112.re^3:組み合わせ

投稿者:M.Kamada - 2000年 12月 09日 04時 25分 32秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.01; Windows 98)
メールアドレス:m_kamada@nifty.com
ホームページ:http://homepage2.nifty.com/m_kamada/index.htm

広井さん、deepgreenさん、こんにちは。

nCrの組み合わせを0~(nCr)-1の番号に変換する方法ですが、
基数変換の応用で簡単にできます。

てきとーに書いたサンプルなので不完全and/or無駄があるかも知れませんが、
下のCの関数で
ncr2num(8,4,"00001111")==0
ncr2num(8,4,"00010111")==1
 :
ncr2num(8,4,"11110000")==69
になります。

--------
int ncr2num(int n, int r, char *p)
{
int c, a = 0;
n--;
c = ncr(n, r); /* nCr */
while (n >= r && r > 0) {
if (*p++ & 1) {
a += c;
c = (c * r) / (n - r + 1); /* nC(r-1) */
r--;
}
c = (c * (n - r)) / n; /* (n-1)Cr */
n--;
}
return a;
}

111.re^2:組み合わせ

投稿者:M.Hiroi - 2000年 12月 08日 22時 50分 30秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

>やはり、簡単な方法はないのでしょうか。
>ときどきでてくるパターンなので、よい方法あるといいなぁ
>と思っていました。

Google で検索してみましたが、やはり見つかりません。
よい方法を知っている方がいましたら、書き込みお願いいたします。

110.re:組み合わせ

投稿者:deepgreen - 2000年 12月 08日 20時 53分 26秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

広井さん、こんばんは。 deepgreenです。

>>しかし、不思議なことに組み合わせ nCkの完全ハッシュ関数を解説して
>>いるところはありません。

>たとえば、8個の中から4個を選ぶ組み合わせは70通りありますが、
>それを 0 から 69 の数値に変換する方法ならば、M.Hiroi もわかり
>ません。

そうそう、これが知りたかったのですが、やはり、簡単な方法はないの
でしょうか。ときどきでてくるパターンなので、よい方法あるといいなぁ
と思っていました。

109.組み合わせ

投稿者:M.Hiroi - 2000年 12月 08日 20時 03分 04秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

>しかし、不思議なことに組み合わせ nCkの完全ハッシュ関数を解説して
>いるところはありません。

たとえば、8個の中から4個を選ぶ組み合わせは70通りありますが、
それを 0 から 69 の数値に変換する方法ならば、M.Hiroi もわかり
ません。

ところで、組み合わせは次の方法で簡単に数値へ変換することができます。
たとえば、0 - 7 の数字の組み合わせを考える場合、0 - 7 を 0 bit から
7 bit に対応させます。すると、2,3,4,6 という組み合わせは 01011100
になるので 92 と表すことができます。

たしか、値が衝突しないハッシュ関数を完全ハッシュ関数、N個のデータ
を 0 から N - 1 に変換するハッシュ関数を最小完全ハッシュ関数と呼ん
でいたように記憶しています。すいません、記憶があやふやです(苦笑)。

そうだとすると、この方法でも値は衝突しないので、完全ハッシュ関数と
考えてよいと思うのですが、どうでしょうか。

108.単なる興味の質問:組み合わせ nCk の完全ハッシュ関数は?

投稿者:deepgreen - 2000年 12月 08日 00時 01分 26秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

こんばんは、deepgreenです。

単なる興味ですが、8パズルの解法でn個の順列の完全ハッシュ関数の
説明がありました。この方法は他のサイトでも目にしたことがあります。
しかし、不思議なことに組み合わせ nCk の完全ハッシュ関数を解説して
いるところはありません。(私が知らないだけでしょうけど)
もし、ご存知でしたら教えてください。

107.Vivisimo Search

投稿者:M.Hiroi - 2000年 12月 07日 20時 54分 24秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

Memo に書いた Vivisimo Search の続きです。

M.Hiroi's Home Pageを検索すると、「anime, sakura」という
カテゴリに分類されるHPがあります。これは、どうやら作家(?)
の広井王子氏に関連したホームページのようです。
sakura は「CCさくら」ではなくて、「サクラ大戦」みたいで
す。なるほど、きちんと分類されているんですね。

Vivisimo Search、ただ者ではないようです(笑)。

106.Re.Prolog:平面上の蛙とびゲーム&ペグ・ソリテア

投稿者:M.Hiroi - 2000年 11月 29日 21時 38分 05秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

> ついでに、平面上の蛙とびゲームをPrologで解いてみました。

46手と長い手数かかりますが、それを Prolog で解くとは、さすが
deepgreen さんですね。お見事です。

> 広井さんの枝刈り(グループ化)を追加した場合、以下のような
> 結果となりました。

さっそく試していただき、ありがとうございます。
なるほど、deepgreen さんの枝刈りと組み合わせた場合でも、
効果は出ていますね。おかげさまで、有効な枝刈りであることを
確かめることができました。

幅優先探索の場合、枝刈りの効果は少ないですが、それだけ無駄な
状態を生成していないのでしょう。双方からの幅優先探索の効果は
絶大であることを、あらためて実感しました。

105.Prolog:平面上の蛙とびゲーム&ペグ・ソリテア

投稿者:deepgreen - 2000年 11月 29日 01時 26分 26秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

こんばんは、deepgreenです。

ついでに、平面上の蛙とびゲームをPrologで解いてみました。
やはり、最短手数は46手です。直線の場合と違って、解はたくさんあります。

  探索時間:525秒  ノード数:45297


それから、広井さんの枝刈り(グループ化)を追加した場合、以下のような
結果となりました。
          前回      今回  前回/今回
  反復深化  2384秒   1683秒    1.42 
  (ノード数)1,083,994 840,926    1.29

  幅優先    727秒    642秒    1.13 
  (ノード数)  94,396      88,514    1.07
   

104.Re.Prolog:変形三角盤(ペグソリティア)

投稿者:M.Hiroi - 2000年 11月 23日 20時 27分 04秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

> 割り算を1桁間違えていました。約280倍でした。

はい、そうでしたね。M.Hiroi も後から気がつきました(笑)。
280 倍でも大きな違いであることは、かわりありません。

> 反復深化の方の結果がでました。
> 探索時間:約40分 ノード数:1,083,994

おめでとうございます!
いやー、凄いです。M.Hiroi は、1時間以上かかるだろうと思ってい
ましたが、40 分とはとても速いです。

deepgreen さんの枝刈りは凄いですね。探索ノード数が拙作の約半分
なのを見て、目が点になりましたよ(笑)。must と need に分けて
管理する方法は素晴らしいと思います。

プログラムの公開、ありがとうございます。
Prolog に興味のある方は、ぜひ参考にしてください。
とても勉強になります。

103.Re.Prolog:変形三角盤(ペグソリティア)

投稿者:deepgreen - 2000年 11月 23日 02時 12分 57秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
ホームページ:http://www2.tokai.or.jp/deepgreen/shortnotes/pegida.txt

こんばんは、deepgreenです。

> ノード数は、(目安ですが)約2800倍の差があります。

すみません。割り算を1桁間違えていました。約280倍でした。

反復深化の方の結果がでました。下記のURLにあります。

枝刈りの着眼点は同じですが、実装は少し違うようです。
     A B
      C 
     D E
    F G H
   ・ ・ ・ ・
隅のA,B,Cのパターンに着目すると、
 (1)A,Bにピンがある場合は、そこが始点になる必要がありますので
  これをmustカウントとします。
 (2)A,Bにピンがあり、Cの位置にピンがないときは、Cの位置にピンが
  こなければなりません。これをneedカウントとします。
 (3)A,Bにピンがなく、Cの位置にピンがあるときは、Cの位置が始点に
  なる必要があります。これはmustカウントとします。この場合連続
  跳びで別の隅のneedカウントをさげる可能性があるため、need
  カウントは-1にします。
  
  C B A  must  need
  0 0 0    0     0
  0 0 1    1     1
  0 1 0    1     1
  0 1 1    2     2
  1 0 0    1    -1
  1 0 1    1     0
  1 1 0    1     0
  1 1 1    2     1
  
 下限値は、3つの隅について、上記のmustの合計+needの合計とな
 ります。ただし、needの合計が負のときは0にします。また、最終手の
 位置の考慮も必要です。
  
  探索時間:約40分  ノード数:1,083,994

102.Re.Prolog:変形三角盤(ペグソリティア)

投稿者:M.Hiroi - 2000年 11月 22日 22時 58分 46秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

> 私も、IDAサーチの方は、この方法でやっています。この枝刈りは、ちょっと
> 面倒なところがあります。今までは、それ以前の探索制御でトラブッていました。

いやー、実は M.Hiroi もトラブってしまいました。
連続跳びの途中で枝刈りを行うとダメなことに気づかず、
最初は何で動かないんだ? と混乱してしまいました(苦笑)。
詳しいことは、Puzzle DE Programming でプログラムを公開するときに
説明する予定です。

それで、結果は Memo に書きましたが、うまくいきません(泣)。
そのほかの枝刈りも試しましたのですが、探索ノード数は減っても、
幅優先探索の約95000個には及びません。

うーん、残念です。なにか効率的な枝刈りがありましたら、
教えてくださいませ。>ALL

101.re:Re.Prolog:変形三角盤(ペグソリティア)

投稿者:deepgreen - 2000年 11月 22日 21時 22分 15秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

広井さん、こんばんは。deepgreenです。

>コーナーペグが移動するためには、自分で跳ぶしかありません。この
>時、跳び越すペグが必要になります。つまり、この位置にペグが無い
>場合は、そこにペグを移動させてから、コーナーペグを移動させることに
>なります。つまり、それだけ手数がかかるわけです。この条件も下限値と
>して利用すれば、もっと効率的に枝刈りができると思われます。

私も、IDAサーチの方は、この方法でやっています。この枝刈りは、ちょっと
面倒なところがあります。今までは、それ以前の探索制御でトラブッていました。
ようやく、それがわかったので少し前進です。これで答えがでてくれると
Happyですが、。。。

100.Re.Prolog:変形三角盤(ペグソリティア)

投稿者:M.Hiroi - 2000年 11月 21日 20時 13分 01秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

Prolog ソースプログラムを公開していただき、ありがとうございました。
いやー、M.Hiroi が考えていた以上のアイデアが盛り込まれていて、
もはや脱帽するしかありません(笑)。

> ノード数は、(目安ですが)約2800倍の差があります。

おおっと、そんなに差がありましたか。幅優先探索の場合、スタート
からの探索と平行に、ゴールからも探索すると、探索する局面数(ノード数)
を劇的に減らすことができます。
(詳しい説明は、「変形版:おしどりの遊び」で行う予定です。)

となると、抜本的に枝刈りを見直さないと、反復深化で解くのは難しい
ですね。そこで、次のような方法を思いつきました。

コーナーペグが移動するためには、自分で跳ぶしかありません。この
時、跳び越すペグが必要になります。つまり、この位置にペグが無い
場合は、そこにペグを移動させてから、コーナーペグを移動させることに
なります。つまり、それだけ手数がかかるわけです。この条件も下限値と
して利用すれば、もっと効率的に枝刈りができると思われます。

とりあえず、Cプログラムを改造して試してみるつもりですが、探索
ノード数が劇的に減少しないと、別の枝刈りを考えないといけませんね。

それではまた。

99.Re.Prolog:変形三角盤(ペグソリティア)

投稿者:deepgreen - 2000年 11月 20日 23時 42分 47秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp
ホームページ:http://www2.tokai.or.jp/deepgreen/

広井さん、こんばんは。deepgreenです。

Prologソースは、量が多いので私のHPの掲示板にupしました。

               探索ノード数     探索時間
 幅優先探索(prolog) 約95000ノード  726秒
 反復深化(広井さんのC)  約28Mノード     81秒

ノード数は、(目安ですが)約2800倍の差があります。

98.Re.Prolog:変形三角盤(ペグソリティア)

投稿者:M.Hiroi - 2000年 11月 20日 21時 20分 00秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

> やっと、Prologで変形三角盤(ペグソリティア)が解けました。
> 探索方式は幅優先探索(双方向)で、約12分かかりました。

それは凄いです! たしか、deepgreen さんのPCは Pentium 133 MHz
だったと思いますが、それで12分というのは、そうとうに速いのでは
ないですか。ぜひ、プログラムを拝見したいものです。

> 反復深化もトライしていますが、時間的にちょっと無理のようです。
> Prologのデバッグは大変でこちらはまだ解けていません。
> うまい方法があればアドバイスをお願いしたいなぁ。。。

私も挑戦してみますね。うまい方法が見つればいいのですが、
力及ばずギブアップするかもしれません。
今のところ、盤面の操作はビット演算かな、という方向で
考えています(笑)。Prolog 好きの方は、チャレンジして
みてください。

97.Prolog:変形三角盤(ペグソリティア)

投稿者:deepgreen - 2000年 11月 19日 23時 44分 22秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

こんばんは、deepgreenです。

やっと、Prologで変形三角盤(ペグソリティア)が解けました。
探索方式は幅優先探索(双方向)で、約12分かかりました。

反復深化もトライしていますが、時間的にちょっと無理のようです。
Prologのデバッグは大変でこちらはまだ解けていません。
うまい方法があればアドバイスをお願いしたいなぁ。。。

96.re^2:白黒n個ずつの蛙跳びゲーム

投稿者:M.Hiroi - 2000年 11月 16日 00時 10分 59秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

> わかってしまえば、簡単な手順ですけど、なかなかそこまではいけない。

西山氏の移動手順を見ると簡単なように思えますが、自分で考えるとなると、
なかなか難しいことですね。まあ、そこがパズルの面白いところなのでしょ
うが、自力で解けないとやっぱりくやしいですね(笑)。

> Prologでペグソリチア(3)をやって遊ばれてます。(なかなか
> うまくいかないけど、こちらの方ははなんとかしたい。。。)

うーん、変形三角盤を Prolog で解くのは大変ではないですか。
それでも、deepgreen さんなら、なんとかなるかもしれませんね。
うまくいったら、教えてください。

95.re:白黒n個ずつの蛙跳びゲーム

投稿者:deepgreen - 2000年 11月 15日 21時 01分 22秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

こんばんは、deepgreenです。

広井さん、ありがとうございます。いつもながらすばやいうごきですね。
わかってしまえば、簡単な手順ですけど、なかなかそこまではいけない。

Prologでペグソリチア(3)をやって遊ばれてます。(なかなか
うまくいかないけど、こちらの方ははなんとかしたい。。。)

94.白黒n個ずつの蛙跳びゲーム

投稿者:M.Hiroi - 2000年 11月 13日 19時 43分 36秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

蛙跳びゲームを検索したところ、白黒n個ずつの移動手順を
具体的に示し、その手順から移動回数を求めているホームページが
ありました。このほかにも、数学関連や数理パズルで面白い
ホームページがありましたので、Memorandom にて紹介しました。
興味のある方はご覧くださいませ。

93.Re.蛙跳びゲームの最短手数は?

投稿者:M.Hiroi - 2000年 11月 12日 23時 19分 47秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

deepgreen さん、こんばんは。

> この説明は、もし解が存在する場合にはこうなるといっているだけで、
> 本当に解が存在するかどうかはわからないようにおもいましたが、
> いかがでしょうか?

ご指摘ありがとうございます。たしかに、そのとおりだと思います。

参考文献にあげた「ゲームにひそむ数理」を読み直してみましたが、
移動のルールを2つ示して、「それに従えばn個ずつのときも確実に
成功する」という記述しかなく、n個ずつでも解が存在することを
厳密に証明していないように思いました。

さて、実際に証明するとなると、M.Hiroi はお手上げです(笑)。
証明できた方は、書き込みよろしくお願いしますね。

92.Re.蛙跳びゲームの最短手数は?

投稿者:deepgreen - 2000年 11月 12日 21時 05分 48秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 4.01; Windows 95)
メールアドレス:deepgreen@thn.ne.jp

deepgreenです。

一言、多いようなきがしますが、この説明は、もし解が存在する場合には
こうなるといっているだけで、本当に解が存在するかどうかはわからない
ようにおもいましたが、いかがでしょうか?

91.Re.蛙跳びゲームの最短手数は?

投稿者:M.Hiroi - 2000年 11月 12日 20時 43分 44秒
ブラウザ:Mozilla/4.0 (compatible; MSIE 5.0; Windows 95; DigExt)
メールアドレス:m_hiroi@geocities.co.jp

問題の解答です。

白黒n個ずつの移動回数は n*n+2n となります。

説明は Puzzle DE Programming:蛙飛びゲーム を
ご覧くださいませ。

[ Home ]