こんにちは。

Nクイーン問題探索アルゴリズムは、
チェスのような基盤にクイーンを取られないように
何個配置できるかという問題だと思います。

同じようなものだと思うのですが、
アルゴリズム フェルナンデス、Fernandes問題
もしくはフェルナンデスの法則や定理を聞いたことがありますか?
知っていたら教えてください。

よろしくお願いします。

以上

このQ&Aに関連する最新のQ&A

A 回答 (1件)

Googleさんにお伺いしたところ2つばかり引っかかりました。



Quinn-Fernandesのアルゴリズム(周波数解析の手法?)
# http://kikkawa.cyber-ninja.jp/mt/Fourier_Extrapo …

Carlos I.G. Fernandez (1998) の研究(クラスタリング アルゴリズム)
# http://www.dsmweb-j.org/tutorial/clustering/inde …

参考までに。
    • good
    • 0
この回答へのお礼

ありがとうございました。

お礼日時:2011/01/28 18:14

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qチェスの駒を使うゲーム

チェス駒を使った、チェスゲーム以外の遊びはありますか?

将棋で言う将棋くずしのような感じで、駒を使うけどルールが違うゲームが他にないか探しています
変則チェスの一種に入るのでしょうが、出来れば使う駒は少ないゲームがないか調べています


ご存じの方はお願いします

Aベストアンサー

一人遊びに、エイト・クイーン配置パズル、ナイト・ツアーパズルがあります。

エイト・クイーン配置パズルは、盤上に八個のクイーンを互いに効き筋にならない配置を見つけるパズル。

ナイト・ツアーはナイトの駒一個で盤上の全マスを通過する初期配置と経路を見つけるパズル。

対戦ゲームに、近年考案されたアリマアというのがあります。ルールなどはインターネットで紹介しているサイトがあるのでそちらを参照してください。どうも動物将棋に似てますけど、動物将棋よりは凝ったルールになっています。


ほかにはチェス盤を利用してチェッカーというゲームを遊べます。

黒マスだけ使います。駒は互いに自陣側三列の黒マスに一個ずつ配置。動けるのは斜め前の黒マス一個ぶんか、斜め前に敵の駒一個があってその先のマスが空いてると飛び越して移動。飛び越した駒は盤上から除きます。敵陣の一列めに駒が到達後はその駒を斜め後ろのマスへも動かせます。普通はオセロの駒に似た平らな円盤型のものを使い、斜め後ろにも動かせるようになった駒を裏返しにして成り駒とわかるよう、裏表の区別のつくデザイン。チェスの駒を使って遊ぶには不向きです。詳しいルールをインターネットで紹介しているサイトがあります。

一人遊びに、エイト・クイーン配置パズル、ナイト・ツアーパズルがあります。

エイト・クイーン配置パズルは、盤上に八個のクイーンを互いに効き筋にならない配置を見つけるパズル。

ナイト・ツアーはナイトの駒一個で盤上の全マスを通過する初期配置と経路を見つけるパズル。

対戦ゲームに、近年考案されたアリマアというのがあります。ルールなどはインターネットで紹介しているサイトがあるのでそちらを参照してください。どうも動物将棋に似てますけど、動物将棋よりは凝ったルールになっています。
...続きを読む

QGA(遺伝的アルゴリズム)でNクイーン問題の解を求めるとき・・・

GAでNクイーン問題の解を求めるとなると、各Nにおける解の総数がわかっていないと解けないのではないかと思います。

普通GAでNクイーン問題を解くと言ったら、複数ある解の内の一つ(クイーンの配置)を示せばいいんでしょうか。

Aベストアンサー

もともと、一つ求めるのが目的ならそれでいいでしょうし、全て求めるのが目的なら全て求めなければならない、てことですが。

GAは確率的アルゴリズムなので、全て求めたいって場合には向いてないってのは確かでしょう。

Qボードゲーム(チェスや将棋など)の世界観が描かれた小説ってないでしょう

ボードゲーム(チェスや将棋など)の世界観が描かれた小説ってないでしょうか?
「鏡の国のアリス」のように、チェス駒が登場人物として出てきたりする感じを探しています。
ご存知の方、ぜひ教えてください。よろしくお願いします。

Aベストアンサー

北村薫「盤上の敵」

優れたミステリーだと思います。
主人公である自分を白のキング、奥さんを白のクイーンに見立てて事件が展開していきます。

QNクイーン問題のアルゴリズムについて

Nクイーン問題のアルゴリズムについて

http://www.itmedia.co.jp/news/articles/0410/06/news079.html

↑このニュースにあるようなNクイーン問題の総数を求めるアルゴリズムは、どんな手法を使っているんでしょうか。
調べたところ、組み合わせ問題には「バックトラック法」が有効と出てきたのですが、世界記録を樹立したプログラムもそれを用いているんでしょうか。

ちなみにプログラムは以下のサイトからゲット出来ます。
http://www.arch.cs.titech.ac.jp/~kise/nq/index.htm


私にはさっぱりなので、どなたかわかる方ご教授ください。

Aベストアンサー

基本的には、こういう組み合わせの問題を真面目に(漏れなく)解こうとしたら、バックトラックでやるか、。もしくは、線形計画法(あるいは整数計画法)の問題に変形して解くか、まあ大きく分ければ2通りの方法しかないです。
バックトラックの場合は、いかにうまく枝狩りを行うかが非常に重要で、そのための方法がいくつも提案されています。
そういう意味では、単にバックトラックというだけでは、ものすごく広い概念で、そのプログラム独自の工夫というか優れている点を述べるには不十分です。

Qチェスと囲碁と麻雀では、どれが世界的にメジャーなゲームと言えますか?

世界的に普及しているゲームとして、チェスと囲碁と麻雀が挙げられると思いますが、この3つのゲームのうち、世界的に最もメジャーと言えるゲームはどれでしょうか。
日本では将棋がメジャーですが、世界的には普及していないので外しました。

Aベストアンサー

ちょっと気になったので、こんなサイトを見つけました。
http://www.igotube.net/jinkou.html

これによると囲碁はアジアでもそこまで一般には、普及はしていないようですね。
ただ、囲碁は戦略的思考が求められるとかで、戦術的思考の将棋や麻雀、チェス等に比べて、より知的なイメージがありますね。

麻雀に関して云えば、麻雀と言っても中国麻雀と日本の麻雀を別の競技としてとらえるかによって変わると思います。
中国人に限らず、中華系の人々はだいたい麻雀できるイメージがありますね。実際、知り合った中華系の人々は全員麻雀をするといっていました。
このことから麻雀の方が単純な人口がチェスよりも多いような気もします。

Qアルゴリズム(2分探索木)の問題について

2分探索木のアルゴリズムに関する問題について質問させていただきます。

[問題]

集合Sに対する2文探索木とは、ラベルつきの2分木で、
その頂点vにはSのある要素l(v)がラベルとしてつけられている。
l(v)は次の性質を満たす。

1.vの左部分木の頂点uに対して l(u) < l(v)
2.vの右部分木の頂点uに対して l(u) > l(v)
3.Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。

図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。
いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、
そうでなければ"いいえ"を出力するアルゴリズムを考える。
このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。
ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。
含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。

・アルゴリズム

procedure SEARCH(a,v):
if a = l(v) then return "はい"
else
if a < l(v) then
if vが左の子wを持つ then return SEARCH( ア )
else return "いいえ"
else


以下の問題に答えよ。

(1) 上のアルゴリズムのア,イを埋めよ。
(2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。
削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。
(i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある

以上です。

設問(1)は解けました。
答えは

ア: a,w
イ: a > l(v) then
if vが右の子wを持つ then return SEARCH(a,w)
else return "いいえ"

になるのではないかと思います。
設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、
参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。

長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。

2分探索木のアルゴリズムに関する問題について質問させていただきます。

[問題]

集合Sに対する2文探索木とは、ラベルつきの2分木で、
その頂点vにはSのある要素l(v)がラベルとしてつけられている。
l(v)は次の性質を満たす。

1.vの左部分木の頂点uに対して l(u) < l(v)
2.vの右部分木の頂点uに対して l(u) > l(v)
3.Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。

図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。
いま、集合Sを表す2分探索木と要素a...続きを読む

Aベストアンサー

確かによくわからないですね。というのは、例示されている擬似言語で書けばよさそうなのですが、擬似言語では要素の削除や移動(または複写)の方法は定義されていないようです。
擬似言語における要素の削除等を勝手に定義して擬似言語で書くか、そうでなければ言葉で説明するくらいでしょうか。(言葉での説明ならかなり書きやすいと思いますがいかがでしょうか)

Qチェスでゲーム後の反省会ができるサイトを教えて

チェスの超初心者です。
サイトのCPU対戦で必ず負けるほど弱いのですが、ゲーム終了後に、ゲームの途中でどこをどうすれば良かったのか反省点を自動で教えてくれるサイトはありますか?

Aベストアンサー

そのようなサイトは恐らくありません。
が、ソフトとなれば話は別です。無料で使えるものがあります。
当然有料の、例えばFritzなどのソフトを使った方がよりよい棋譜解析が
出来ますが、無料でも十分使えるものがあるので、使い方を書いておきます。

まず、こちらをクリックしてください。Rybkaというソフトの無料版が落とせます。
http://www.rybkachess.com/Tarrasch/setup-tarrasch.exe

落とせたら展開してください。英語ですが、複雑な操作は必要ないので
すんなりいけると思います。Create a desktop iconには、
デスクトップから起動できるようにチェックを付けておいた方がいいですね。

デスクトップにアイコンができたら、それを起動します。

すると、上にインベーダーゲームの敵のようなアイコンがあると思います。
Kibitzer start/stopってヤツです。
分析したい局面でそこをクリックすれば、その局面を分析することができます。
下に出てくる手が候補手で、その左の数値がプラスに大きければ大きいほど白が、
マイナスに大きければ大きいほど黒が優勢であることを意味しています。
基本的には一番上に出てくる手がそのエンジン(ソフトの頭脳)が導き出した最善手です。

ここはどうすれば良かったんだろう?という局面まで自分で手を進めるか、
setup positionから局面の駒の配置を入力するかして分析したい局面を
再現してからKibitzer start/stopボタン、が基本的な使い方です。
棋譜を全部入力して1手目から最終手まで分析していくというやり方もアリですね。

使い方の説明はこれでは不十分なのですが、色々試しているうちに慣れてくると
思います。加えて、実はこのソフトは頭脳を他のものと入れ替えることが出来ます。
このソフトに最初から入っている頭脳はRybkaのフリー版ですが、ネット上では
これよりも強い、例えばFirebird、Stockfish、Houdiniといった頭脳が
無料で落とせます。後はそれを落として入れ替えてやればいいわけです。
(合法なので何の心配も要りません)Rybkaのフリー版よりも
もっと強い頭脳が欲しい!と思ったなら、探してみてもいいと思います。
ここに挙げた3つのソフトならば、グランドマスターを倒すほどに強いので。

また、チェス関連の掲示板などで棋譜を丸ごと載せて、「反省点を教えてください」
と書けば、返答が来ることがあります。
人間には出来てコンピュータにはできない局面評価もありますから、
コンピュータに頼りっきりにならないようにした方がいいと思います。

そのようなサイトは恐らくありません。
が、ソフトとなれば話は別です。無料で使えるものがあります。
当然有料の、例えばFritzなどのソフトを使った方がよりよい棋譜解析が
出来ますが、無料でも十分使えるものがあるので、使い方を書いておきます。

まず、こちらをクリックしてください。Rybkaというソフトの無料版が落とせます。
http://www.rybkachess.com/Tarrasch/setup-tarrasch.exe

落とせたら展開してください。英語ですが、複雑な操作は必要ないので
すんなりいけると思います。Create a desktop icon...続きを読む

Q二分探索アルゴリズムの終了条件について

いつもお世話になっています。

現在他人のプログラムを読解する力をつけようと
訓練しています。

以下の文はとあるアルゴリズム本の2分探索の個所を
抜粋したものです。

int bs(*array, size, mokuteki)
{
  ue=size-1, sita=0;

  while(1){
    naka=(sita+ue) / 2;
    if(array[naka] == mokuteki)
      return ARU;
    else if(sita > ue) //・・・・・・★
      return NAI;
    else {
      if(array[naka] < mokuteki)
        sita = naka+1;
      else
        ue = naka-1;
    }
  }
}


ここで★部分の終了条件なのですが、なぜ
  sita >= ue
でいけないのか自分では理解できません。

要はsitaとueが同じ値になり、目的値が見つからなかった
のに再度ループする必要があるのか?、ということです。

特に明確な答えはいりませんがぜひ
ご意見を聞かせてください。

ちなみに作者は
「ue==sitaの状態ならば、幅1の範囲がありますから
 ループをもう一回実行する必要があります。」
と書いています。私には理解できません。


ちなみにこの本は「Javaで学ぶアルゴリズムとデータ構造」
という本です。だいたい一通り読みましたが読んでて
楽しいしわかりやすいし良書だと思います。高価ですが・・・。

いつもお世話になっています。

現在他人のプログラムを読解する力をつけようと
訓練しています。

以下の文はとあるアルゴリズム本の2分探索の個所を
抜粋したものです。

int bs(*array, size, mokuteki)
{
  ue=size-1, sita=0;

  while(1){
    naka=(sita+ue) / 2;
    if(array[naka] == mokuteki)
      return ARU;
    else if(sita > ue) //・・・・・・★
      return NAI;
    else {
      if(array[naka] < mokuteki)
       ...続きを読む

Aベストアンサー

再度ループさせる必要な無いしょう。
size が 0 であるリストを探索することもありますから、どちらにしても、先にarray[naka]を判定をするのは良くないです。

少し飛躍しますが、見つからなかった時にリストに追加しなければならない場合がありますよね?
soakunさんの例だと、ループを抜けた後に、l がそのまま挿入インデックスになるので都合がいいです。

個人的な趣味だと、break しているところは、return が好きなんですけど。

Qチェス盤、ウォッカとウィスキーの駒のゲーム

テレビのニュースで「今、ロシアで今流行っている」
として以下の様なゲームが紹介されていました。
- 1対1で対戦
- チェスの盤を用いる。
- 片方の駒はウォッカグラス十数杯
- もう片方の駒はウィスキーグラス十数杯
- 駒を取られるとグラスの中身を飲み干す

このゲームの名称と
ルール(駒の動かし方や勝利条件等)を
ご存知の方教えてください。

名称は紹介されたのですが記憶しそこないました。
「ショーシキ」とかそんな感じの名前です。
ルールについてアナウンサーは
「チェスともチェッカーとも違う」
といってました。
(チェッカーと同じようにも見えますが)

Aベストアンサー

名称は「シャーシキ」のようです。

調べてみましたがルールまで解説されている
サイトは日本ではないようです。

ロシア好きな方のサイト等で
聞いてみた方がいいかもしれませんね。

参考URL:http://www.google.co.jp/search?q=cache:s93PTGBttaQJ:newstopics.dion.ne.jp/pubnews/videonews/story/%3Fvid%3D1067110%26gen

Qアルゴリズムと問題解決に関する問題

二つの正の整数A,Bの最大公約数を求めるユークリッドの互除法のアルゴリズム

互除法(A,B)
入力正の整数A,B
1 もしA<Bならば
2 BをAで割ったあまりをCとせよ
3 もしC=0でないならAを出力して終了
4 そうでないならば
5 GCD=互除法(A,C)とし、GCDを出力し終了
6 そうでないならば
7 AをBで割ったあまりをCとせよ
8 もしC=0ならばBを出力して終了
9 そうでないならば
10 GCD=互除法(B,C)とし、GCDを出力し終了

互除法(48,84)を行ったときのうえのアルゴリズムの動作(再帰呼び出しの途中に現れるCやGCDの値)を求めよ

これを一応といてみましたが表現方法がいまいちわからないので良い回答の仕方教えてください。

自分で解いた答え
1 A<BなのでB/Aのあまり36をCとする
2 C=36
3 Cは0でない
4、5 GCD=(A,C)=(48,36)

1に戻る A=48,B=36とする
1 A<Bでない
6 A/BのあまりをCとする
7 48/36のあまり C=12
8 Cは0でない
9,10 GCD=(36,12)

1に戻る A=36,B=12
1 A<Bでない
6,7 36/12 C=0
8 C=0 B=12

二つの正の整数A,Bの最大公約数を求めるユークリッドの互除法のアルゴリズム

互除法(A,B)
入力正の整数A,B
1 もしA<Bならば
2 BをAで割ったあまりをCとせよ
3 もしC=0でないならAを出力して終了
4 そうでないならば
5 GCD=互除法(A,C)とし、GCDを出力し終了
6 そうでないならば
7 AをBで割ったあまりをCとせよ
8 もしC=0ならばBを出力して終了
9 そうでないならば
10 GCD=互除法(B,C)とし、GCDを出力し終了

互除法(48,84)を行ったときのうえのアルゴリズムの動作(再帰呼び出しの...続きを読む

Aベストアンサー

トレースはきちんと出来ていますね。

ただ問題の出来がひどすぎます。

1.項番5と項番10のGCDの出力は絶対に通らないようになっています。
GCDには値も入りません。
必ず項番3と項番8でしか出力しません。
問題を出した人が再帰が良くわかっていないようです。
これをきちんとするには「RETURN:CALL先の次へ戻る」を入れる必要があります。
それをしないとこのプログラムはおそらく暴走するでしょう。

2.項番3は「もしC=0なら」のミスでしょう。

一応このままやってみると
1 48:84だからA<B
2 C=84%48=36
3 C≠0で次へ
4,5 48,36で互除法を呼ぶ 
1 48:36だからA<Bではない
6,7 C=48%36=12
8 C≠0で次へ
9,10 36,12で互除法を呼ぶ
1 36:12だからA<Bではない
6,7 C=36%12=0
8 C=0なのでb=12を出力して終了

てなとこでしょうか。


人気Q&Aランキング

おすすめ情報