ホームページへ戻る  書き込みリストへ戻る
プログラミングパズル雑談コーナー

プログラミングパズルに関心のある人は雑談しましょう!


Re: 簡易ロト問題 投稿者:高橋謙一郎  投稿日:02月17日(木)22時15分49秒

続きです、

deepgreenさんのプログラムは幅優先なのでしょうか?それとも下限からの反復深化ですか。
反復深化かな〜でしょうね。下から攻めるか上から攻めるか迷ったのですが、よくよく考えて
みると普通に下からの反復深化で良かったような気がしてきました。

上から攻めた場合、上限値が甘すぎると地獄ですからね。(ラッキーな場合もありますが)
とくしんさん提案による、上と下から2分探索で絞り込むのもいい方法ですが、1回分の探索
時間があまりに長すぎるので何回も探索できる余裕がないんですよね。

で、上から攻めてラッキー過ぎたために書き込みミスをしたお詫びというか、証拠の品というか、
ソースコードを置きます。コンパイルして実行すると私のアホな事情が分かるかも知れません。

../../index.htmltemp/miniloto.c


Re: 簡易ロト問題 投稿者:高橋謙一郎  投稿日:02月17日(木)20時56分24秒

deepgreenさん、こんばんは。

「5個の数字から3個以上」の問題で、N=13の最適解は8個で間違いありません。

すみませんでした、久しぶりの書き込みなので、あせっていたようです。
私のソルバーも間違いなく8個という結果が出ていたのですが書き込みの時に単純コピー
によるミスがありました。というか、、、

記録をよく見ると、N=13での8個解は「欲張り法」ですぐに見つかったのですが、
あまりに簡単に見つかり過ぎたので気にもとめずに勘違いしていたようです。
(7個で解がないというは、一晩かかっています。)

うぅ、美味しいところを取られてしまった。(←はずかしながら、素直な気持ち)


Re: 簡易ロト問題 投稿者:deepgreen  投稿日:02月17日(木)19時58分29秒

 皆さん、こんばんは。deepgreenです。
 私も、誘惑には勝てず、久しぶりにSolverを作りました。

「5個の数字から3個以上」の場合、N=13には、8個の解があることが
 わかりました。7個の解は存在しません。

==== (13, 7) ====    Thu Feb 17 02:47:52 2005  −> 解なし

==== (13, 8) ====    Thu Feb 17 02:51:30 2005
==== Congratulation !!! ====    Thu Feb 17 05:00:52 2005

      1 2 3 4 5 6 7 8 9 0 1 2 3
      -------------------------
s1    1 1 1 1 1 . . . . . . . .
s2    1 1 1 . . 1 1 . . . . . .
s3    . . . 1 1 1 . . . . . 1 1
s4    . . . 1 1 . 1 . . 1 1 . .
s5    . . . . . 1 . 1 1 1 1 . .
s6    . . . . . . 1 1 1 . . 1 1
s7    . . . . . . . 1 . 1 1 1 1
s8    . . . . . . . . 1 1 1 1 1

 どこか勘違いしてるかな ???


Re: 上限問題 投稿者:三吉  投稿日:02月17日(木)01時07分09秒

N=9 の場合の説明ありがとうございました。
カークマンの15人の女学生の問題についてはたまたま
http://www.sampou.org/cgi-bin/haskell.cgi?blog%3aEveryday%3a2004-11-22&l=jp
のときに調べたことがありました。

「3個の数字から2個以上」で N=10 のとき
{(1,2,3),(1,4,5),(2,4,5),(3,4,5),(6,7,8),(6,9,10),(7,9,10),(8,9,10)}
の8個の解が見つかっているそうです。(上限8が確定)


Re: 簡易ロト問題 投稿者:高橋謙一郎  投稿日:02月16日(水)22時53分21秒

塗り壁さん、皆さんこんばんは。

数学的な議論は全く苦手なのですが、deepgreenさんの「3個の数字から2個以上」で
N=9の場合の上限解の求め方は良く理解出来ました。とても明解で感激しました。

ところで、この前の3連休の時に私も考えてみました。前回のサッカーくじと違って
今回は最適解にこだわったのですが、「5個の数字から3個以上」の本来の問題では、

N=10  2個
N=11  5個
N=12  6個
N=13  9個

までは結果を出せました。(欲張り法で上限解を求めてから、総当り法で最適解を確定)
久しぶりにパズルのプログラムを書いて楽しかったのですが、かなりの難問ですね。

三吉さん提案による「3個の数字から2個以上」にプログラムを書き替えてもみました。
N=9の場合の解は、欲張り法で9個、最適解は7個と一瞬で結果が出ていました。

最終的に最適解を得ようとするならば、総当り法をベースにしたアルゴリズムにおいて
対称性を考慮して同等のパターンを排除しながらの探索を行うプログラムが必要です。
加えて、2種類の枝刈り法も搭載したのですが、それはほとんど役に立っていません。

サッカーくじ同様に乱数を使って、近似的な最適解を求めるしかないような気がします。
ただ、あまり得意な分野ではないし時間もないので、どうにもならないのですが。。。

ところで、塗り壁さんにくどいような質問で申し訳ありませんが、以下の結果は最適解
と断定されたものなのでしょうか、それとも見つかった解の最小記録なのでしょうか。

N=14  10個
N=15  13個
N=16  16個


Re: 簡易ロト問題 投稿者:deepgreen  投稿日:02月16日(水)21時19分58秒

すみません。肝心の問題について抜けていました。

「3個の数字から2個以上」でN=9の場合について、
シンプルな解(12個)を具体的に求めた結果です。


Re: 簡易ロト問題 投稿者:deepgreen  投稿日:02月16日(水)20時56分03秒

初等幾何で考えてみました。

(1)9ケの数字を3x3の格子点に対応させる。

   7 8 9

   4 5 6

   1 2 3

(2)9ケの数字から3ケの数字を選択する。
   → 3x3の格子点上では3角形を特定(選択)したことになる。
    ([1,2,3]のようにつぶれているものも含む)

(3)2組の3ケの数字の間で、2ケの数字が一致する。
   → 2つの3角形が辺を共有するということ。
     ex.[2,3,4]と[3,4,5]は、辺[3,4]を共有している
 
(4)代表として、以下の12ケの3角形を選択する。

   a.傾きが0度の線分を網羅するもの
     [1,2,3] [4,5,6] [7,8,9]

   b.傾きが90度の線分を網羅するもの
     [1,4,7] [2,5,8] [3,6,9]

   c.傾きが45度の線分を網羅するもの
     [1,5,9] [2,6,7] [3,4,8]

   d.傾きが−45度の線分を網羅するもの
     [1,6,8] [2,4,9] [3,5,7]

   この12ケの3角形で、縦、横、斜めのすべての線分が網羅されていることがポイント。

(5)3x3の格子点上の任意の3角形は、少なくとも1辺として、縦、横、斜めのいずれか
   の線分をもつ。

   (説明) 1を頂点とする3角形を考える。他の2点として2,5のような自明な点を
        除外すると、残るのは、6,8のみである。この1,6,8の3点で構成さ
        れる3角形は、[6,8]という−45度の線分が含まれる。
        従って、1を頂点とする3角形は題意を満たしている。
        同様にして、他の点を頂点とする場合も成り立つ。(説明略)

(4),(5)より、3x3の格子点上の任意の3角形は、(4)の12ケの3角形のいすれか
と辺を共有していることがわかる。



上限問題 投稿者:塗り壁  投稿日:02月15日(火)22時29分13秒

yahoo掲示板では、ロト問題の最適解を直接求める
のが困難なため下記のような上限問題も議論されました。

上限問題「Nを与えられた自然数とする。また、1以上N以下の相異なる5個の
数字からなる集合、及び相異なる3個の数字からなる集合をそれぞれ5−集合、
3−集合ということにする。
このとき、次の条件を満たす5−集合の集合Xを考える。
条件C 任意の3−集合が、Xに含まれる何れかの5−集合に含まれる。
条件D Xは条件Cを満たす集合のうちで位数が最小である。
これらの条件を満たすXを具体的に求めよ」

この問題の解が、ロト問題の解の上限を与えることはすぐわかると思います。
この問題に対する掲示板での最良の結果は次のとおりでした。
N=8 8個
N=9 12個
N=10 17個

で、昨日の続きですが、
「3個の数字から2個以上」でN=9の場合の最適な個数は12個です。
を12個以下に訂正します。12個が最適だと言ったのは5,3を3,2に変えた
上限問題の場合の話でした。

この上限問題で12が最適であることは、有限幾何学における(有限)アフィン
平面を用いてわかります。

N次のアフィン平面とは、次のような集合から構成される幾何学的構造です。
1 N^2個の点を持つ集合A
2 Aの部分集合(直線と呼ぶ)からなるある集合Lで次の条件を満たす。
 条件E 全ての直線はN個の点を含む
 条件F 任意の相異なるAの2点を含む直線が唯ひとつ存在する。
また、N次のアフィン平面はN(N+1)本の直線を持つことも言えます。

従って、特に、3次のアフィン平面の直線全体は上限問題の解で、従って、最適解は
直線の本数である12ということが言えます。

昨日数学的に興味深いといったのは、こちらの上限問題の話でした。N=9の場合のそれは、カークマンの15人の女学生の問題(興味があれば検索してください)の簡略バージョンにもなっています。
なお、代数学(特に有限体)の知識がアフィン平面を具体的に構成するときに必要になりますが、そこまで触れるとほとんどの人が退いてしまいそう(とっくに退いているかも知れないが)なのでやめておきます。


Re: 簡易ロト問題 投稿者:三吉  投稿日:02月15日(火)04時33分20秒

> ただ、N=9の場合は数学的にかなり興味深い事実があります。

それは楽しみです。代数は大丈夫(なはず (^_^;))なので解説お願いします。


Re: 簡易ロト問題 投稿者:塗り壁  投稿日:02月15日(火)02時38分19秒

三吉様今晩は。
>「3個の数字から2個以上」についてはすでに何かしらの公式が
>見つかっていますか?
わかりませんが、多分無いと思います。
ただ、N=9の場合は数学的にかなり興味深い事実があります。
もう遅いので詳細は明日にして、この場合の結果だけ述べると最適な個数は12個です。
なお、この結果は、プログラムで検索したものでなく、純粋に理論的に得られたものです。
詳細を述べるためには、数学的(特に代数方面)な議論が必要になりますが、
この辺は如何でしょうか。


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