このカテゴリーでいいのでしょうか。
 魔法陣の作り方は、教えて!gooでも解説があります。一般的な解法があるようですが、そういった解法を使わないで、魔法陣をつくるアルゴリズムは、どのようにしたらいいでしょうか。
 全ての場合をしらみつぶしに調べていくという方法では、nxnの魔法陣では、(nxn)!通りに比例する程度のステップを繰り返すことが必要になりそうで、nが少し大きくなると、実用の範囲内の時間でみつけるのは難しそうです。
 一般的な解法を用いないで魔法陣を解く、実用的なアルゴリズムを教えてください。
 

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

A 回答 (2件)

えーと、5×5のような奇数の場合にだけ使える方法です。


文字だけで説明するのはちょっと難しいですが、5×5であるとして
はじめに5×5の枠(図の■)をかきます。その外に下の図のように枠を足します。(図のB。なお□は図をそろえる為のものです)

□□□□B
□□□BBB
□□■■■■■
□B■■■■■B
BB■■■■■BB
□B■■■■■B
□□■■■■■
□□□BBB
□□□□B

そこへ一番上の頂点から斜めに数字を1から書くのですが、
□□□□1
□□□2□6
□□3■7■11
□4■8■12■16
5□9■13■17□21
□10■14A18■22
□□15■19■23
□□□20□24
□□□□25
もとの5×5の枠からはみ出ている数字を反対側の■に書き込みます。
つまり、上の図で1はAに入れるというようにします。そうすると
  3,20,7,24,11
  16,8,25,12,4
  9,21,13,5,17
  22,14,1,18,10
  15,2,19,6,23
という魔法陣が完成して、縦・横・斜めどこも和は65となります。
文字で書くと難しいかも知れませんが、紙に書くとすぐ判ります。

こんな方法でよろしいかと思うのですが。
    • good
    • 0

単純に計算すると、4×4 の時ですら、(4^2)! = 20,922,789,888,000 ですから、この時点で実用的でないですよね。

最初の一行のうちの3つの数字の和が 18 未満のものと 34 以上になるものを省き、1つ足して、最初の一行の和が 34 にならないものを省き・・・と繰り返していけば、ずいぶん減って実用の範囲内に収まるかもしれません。
それでも 5×5 は無理っぽいです。

何か方法があるとすれば、囲碁のAIなども人間を遙かに超えているだろうから、無いと考えるのが無難なのじゃないかと思います。
    • good
    • 0

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

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

このQ&Aを見た人はこんなQ&Aも見ています

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

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

Q大滝みや子先生の「アルゴリズム解法」で

大滝みや子先生の
基本情報技術者 「かんたんアルゴリズム解法」流れ図と擬似言語で
ページ49
第2章 基本例題
第1部アルゴリズムと流れ図
5 1次元配列へのデータ格納 の
表2で、
umaxnの要素"4"と"5"
及び
statusの要素"空き"が
○(まる)で囲まれている理由が、解りません。

ご存知の方、教えて下さい。
宜しくお願いします。

Aベストアンサー

●statusの要素"空き"が ○(まる)で囲まれている理由

「status:部屋の状況が格納された配列」の要素の内容が "空き" のものだけが利用可能だから。

●umaxnの要素"4"と"6"が ○(まる)で囲まれている理由

「umaxn:部屋の最大利用可能人数が格納された配列」の要素の内容が,入力されたデータ「利用人数=4」以上のものだけが利用可能だから。

●rankの要素がすべて ○(まる)で囲まれていない理由

「rank:部屋の階級が格納された配列」であり,入力されたデータ「部屋の階級=0」は「部屋番号の階級を問わない」という意味だから。
(すべての行が条件に合致することになるので,本来ならrankのすべての要素を○で囲んでもよいと思います)

Q実践的な遺伝子的アルゴリズムの作成法

素人ですが、遺伝子的アルゴリズムを考える上で、大きな問題に直面しています。
1)最適化の対象を如何にコーディングするか?
2)交叉点を如何に設けるか?
これらは組合せの対象の要素間に何らかの曖昧な複数の相関関係がある場合に難しくなります。

そこで、
1)「遺伝子的アルゴリズム」をタイトルにした一般の技術系の和書に書かれている以外に、実例を調べる手段?
2)社会人が遺伝子的アルゴリズムの開発の実際を学ぶための公共の機関、例えば聴講生として学べる場所?
3)遺伝子的アルゴリズムを組み込んだソフトを作る上で、普段使用しているC++などの汎用プログラム言語と、SchemaやLISPなどの知能プログラミング言語とでは、どちらが便利なのでしょうか? これらの人工知能プログラム言語には、コーディングや交叉のための専用のコマンドが提供されているのでしょうか?

自分は、情報工学の出身ではないため、C++言語と「遺伝子的アルゴリズム」の技術書籍以外には、バックグラウンドがありません。よろしくお願いいたします。

Aベストアンサー

実は私も素人ですが・・・・

>1)最適化の対象を如何にコーディングするか?
>2)交叉点を如何に設けるか?
いわゆるモデリング(コーディング)手法ですね。

ここは、誰もが必ずぶつかるところだと思います。
もっとも根本的なことでありながら、きちんと(論理的に)説明されている書籍・論文、あるいは、きちんと整理できている人・技術者・学者先生に、お目にかかったことがありません。
ある大学教授にいたっては、堂々と「GAのコーディングは、カンと経験」と明言しておられます。

#私の考えでは決してそれに賛成していませんが・・・私自身、整理して説明ができるわけではないので、表立って反論はできません。
#ただ、「根本的にできないこと」ではなく、「まだ、やり方が整っていない」だけだと思っています。

前置きはこれくらいにして・・・
>1)・・(略)・・・以外に、実例を調べる手段?
 コーディングに関しては、3~4年前のシステム制御関係の学会誌、あるいは、Cマガジンはじめ、ちょいと硬派なプログラマ向け雑誌などで解説を見つけることができます。
 巡回セールスマンとか、パズルに関しては、おっしゃるような「技術系書籍」がいいと思います。
 (確か、北先生のがわかりやすかったと思います)
  ただ、「実例」となると、企業での利用が多いでしょうから、具体的内容を詳しく知るのは難しいかも・・・・
  また、逆に、「あ~、これとこれで、こうやっているのね」と容易に推定できるものもあります。
  たとえば、離散系シミュレータの「Witness」というソフトの求解に使われていますが、カタログに出ている画面イメージからでもおよそのコーディングと組み込まれ方が想像つきます。
  ただ、「こうなんですね」と聞いても、正確に答えてくれる人はいないようです。

>2)社会人が・・・(略)・・・・学べる場所?
 おそらくお仕事で利用しようとされているかと思いますので、学求的に高度な(実践的でないような)ことではないですね。
 数年前から比べるとずいぶん聞かなくなったような気がします。(いい意味で定着したのか、絶滅したのか)
 あまり、詳しくないので推測ですが、大阪の場合、産業技術研究所でかなり以前やっていたと思います。
 公的機関なので、無料で開催されたりするようですし、関係の学会などで、先生とお友達になって、(個人的に)講義に混ぜてもらうという手もあるかもしれません。

>3)・・・・・C++などの汎用プログラム言語と、SchemaやLISPなどの知能プログラミング言語とでは、どちらが便利なのでしょうか?
>  これらの人工知能プログラム言語には、コーディングや交叉のための専用のコマンドが提供されているのでしょうか?
 私としては、遺伝アルゴリズム自体を研究するのでなく、利用する立場でしたので、C言語がよいと思います。
 Schemaは知りませんし、LISPもここ10年くらい遠ざかってます。
 処理系の入手性の問題、参考書・解説書(時にはサンプルプログラム)の多さからして、C、C++、VB、Javaでしょう。
  また、LISPには、専用コマンドというわけではありませんが、遺伝子をインプリメントしやすい線形リストが言語仕様のベースですし、リストをあれこれいじりまわす命令は充実していますので、その部分に限っては便利と思います。
 #リストがベースだから”LISP”、ってのはご存知のとおり。

 が、しか~し、Cでもリスト構造は比較的簡単に実現できますし、特に遺伝子を配列で表現してもいいわけなので、その点はそんなに重要ではありません。
 実践で利用するなら、入出力やコンパイラ自体の扱いやすさ、入手性、メンテ性、周辺システムとのインターフェースで、通常のプログラム言語のほうが、(あなた自身が使い慣れているもののほうが)格段に勝ります。LISPなどには、ガベジコレクションやメモリ消費などの問題もありますね。

>これらは組合せの対象の要素間に何らかの曖昧な複数の相関関係がある場合に難しくなります。
冒頭に書いたとおり、私は素人ですが、遺伝子コーディングするときは、「曖昧な複数の相関関係」など悩まずに、素直に(何も考えずに)やって、進化過程で、制約として淘汰して殺すという方法でも、まずまず準最適結果(らしきもの)が得られています。
 ↑こんな考え方は、アルゴリズムをギンギンにチューニングして、限界最適値を超高速で求めようという場合には、ダメなんでしょうが、結果を程よく収束できればいいや、くらいでは、十分です。

実際の問題をインプリメントすると、ほんの数100行になったりします。そのプログラムがそれらしい結果を出してくれると、なんか神がかりのような気分を味わえます。

「なんで、これで解が出るんだ~!!」って感じ。

がんばってくださひ。
では・・

実は私も素人ですが・・・・

>1)最適化の対象を如何にコーディングするか?
>2)交叉点を如何に設けるか?
いわゆるモデリング(コーディング)手法ですね。

ここは、誰もが必ずぶつかるところだと思います。
もっとも根本的なことでありながら、きちんと(論理的に)説明されている書籍・論文、あるいは、きちんと整理できている人・技術者・学者先生に、お目にかかったことがありません。
ある大学教授にいたっては、堂々と「GAのコーディングは、カンと経験」と明言しておられます。

#私...続きを読む

Q遺伝的アルゴリズム

遺伝的アルゴリズムで組み合わせ問題の解決に取り組んでいるのですが、どのくらいの個数からGAは有効っていえるのでしょうか?
全通りを調べる方法より早く見つかれば有効と言えるのでしょうか??
どなたかご存知の方いられましたら、教えてください。
お願いします!!

Aベストアンサー

いままで分かっているGAを使った方法より、速ければ有効である。・・・かな?
全通りを調べる方法より速く見つかっても、隣の大学で去年やった方法と同じなら、あんまり意味無いですね。

差を出すなら、突然変異の確率とか交配?の度合いをダイナミックに変える方法を試してその吟味とか。
その組み合わせにもよるけど、各パラメーターをGAが変えられるというルールの研究でも良いと思います。
(学会誌等で過去の論文を見るのは必要です)

Q遺伝的アルゴリズムって

実用レベルでは何か成果をあげているのでしょうか?
遺伝的アルゴリズムをビジネスに結びつけている例があれば、教えてください。

Aベストアンサー

カーナビで利用する研究がなされているという話を聞いてます。

http://www.google.com/search?hl=ja&lr=lang_ja&ie=UTF-8&oe=UTF-8&q=%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0+%E3%82%AB%E3%83%BC%E3%83%8A%E3%83%93&num=50

Q日本語を意味的に分割するアルゴリズムが知りたいです。

日本語を意味的に分割するアルゴリズムが知りたいです。

吾輩は猫である。名前はまだ無い。どこで生れたかとんと見当がつかぬ。

吾輩



ある

名前
...
というように、日本語を最小単位で分割する方法が知りたいのですが、こういうのは簡単にはできないのでしょうか?

PerlやVBAで使いたいのですが参考になるサンプルや書籍などございましたら、教えてください。

Aベストアンサー

 「形態素解析」で、検索してみてください。色々と難しい話が出てきますが、基本的な知識として覚えておくのもよいかも!!

 実際には、KAKASI,ChaSenなどの有名なソフトを利用するのが良いでしょう。
  http://kakasi.namazu.org/
  http://chasen.naist.jp/hiki/ChaSen/

また、perlで使用するならText::Kakasiが良いかも

  http://search.cpan.org/dist/Text-Kakasi/

参考URL:http://search.cpan.org/dist/Text-Kakasi/


このQ&Aを見た人がよく見るQ&A

このカテゴリの人気Q&Aランキング

おすすめ情報