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

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


re:グラフ理論?  投稿者:deepgreen  投稿日:07月05日(水)01時11分47秒

塗り壁さん、こんばんわ。
グラフ理論に強そうなので教えていただけると幸いです。
1年程前にアルカン(化学式:CnH2n+2)の構造異性体の数を求めるという
話題がありました。その時、グラフ理論を使って解く方法があることはわかりましたが、
具体的な方法は私には解かりませんでした。(本を探したが見つからなかった)
もし、ご存じでしたら教えていただけないでしょうか?


訂正 投稿者:塗り壁  投稿日:07月05日(水)00時04分06秒

訂正ばかりで申し訳ありません。先ほどの投稿に、ごみが混じってしまいました。
後ろの2行は無視して下さい。


re:グラフ理論? 投稿者:塗り壁  投稿日:07月05日(水)00時00分28秒

高橋さん今晩は (実は、私の本名も高橋なので、deepgreenさんの投稿の一行目で
どっきりしたりもしました)
記載のホームページ拝見しました。ただ、具体的なアルゴリズムが無いのが
ちょっと残念。
アルゴリズムによっては、LightsOutだけでなく8めぐりやその他もろもろの反転問題も
全く同じロジックで解けるはず。そのへんがグラフを扱う大きなメリットですね。
がっかりしました。
は意見しました。


re:グラフ理論?  投稿者:deepgreen  投稿日:07月03日(月)20時31分56秒

高橋さん、一言多いかもしれませんが、...
グラフ理論のアプローチでライツアウトを解いたという事実は貴重な情報だと思います。
この卒論へのリンクを追加していただいたほうがよいのではないでしょうか?


re:グラフ理論? 投稿者:高橋謙一郎  投稿日:07月02日(日)19時01分47秒

 塗り壁さん、はじめまして。

 貴重な情報をありがとうございます。ライツアウトの記事を書いた直後にネットサー
フィンで下記のURLを発見して、この人は間違い無く同じ方法で解いていると確信し
まして、こう言うアルゴリズムがグラフ理論の中にあるのだろうと思いこんでしまいま
した。

「多項式アルゴリズム」というのは「多項式時間計算可能アルゴリズム」と言う意味で
問題の大きさ(N)について探索時間が、N乗レベルで増大するものではなくNの定数乗
レベルで増大するアルゴリズムのグループを総称してそう呼ぶのだ。と言うことなので
すね。勉強になりました。(さっそく追記を削除したいと思います。)

http://www.yilab.tutics.tut.ac.jp/abstract/aoki.html


訂正 投稿者:塗り壁  投稿日:07月02日(日)01時43分13秒

前便で、最後の行が日本語としておかしいので次のように訂正します。

多項式云々と有りましたが、もしかすると多項式時間計算可能アルゴリズムの事でしょうか。
そうならば、これは特定のアルゴリズムでなくコンピューターで実行可能なアルゴリズムの
グループを表わします。(実行可能とは、常識的な範囲内で終了できるもの、実行に、
何億年もかかったりはしないようなアルゴリズムです)


グラフ理論? 投稿者:塗り壁  投稿日:07月02日(日)01時19分51秒

はじめまして、塗り壁と言います。パズル及びプログラミングに興味が有るので、
時々覗かせてもらってます。私はグラフ理論をベースにプログラミングをしているので、
ライツアウトの回答のところの追記が気になりました。記載のアルゴリズムは
連立方程式の話で、グラフ理論に関係しているようには見えないのですが。
多項式云々と有りましたが、もし多項式時間計算可能アルゴリズムの事でしょうか。


Puzzle Page 投稿者:Puzzle Page管理人  投稿日:06月27日(火)01時12分09秒

パズル・ゲーム・クイズのページです。毎日更新、誰でも遊べる。いつも新鮮な情報が有ります。

http://www2.odn.ne.jp/~cbp61410/


究極のナンプレ 投稿者:麦丸  投稿日:06月08日(木)23時57分32秒

昔、パズラー(世界文化社)という雑誌で、19個の問題は見た覚えがあります。

それ以下は、ちょっとないです。。

18個というと、各ブロックに平均で数字2つの割合ですよね。わたしには、
多分、作れないですね (-_-;;

存在するなら、ぜひ、解いてみたいなぁ。

http://motokiya.pobox.ne.jp/mugimaru/


麦丸さん、はじめまして 投稿者:高橋謙一郎  投稿日:06月08日(木)21時24分43秒

麦丸さん、はじめまして。

ナンプレ(数独)にかなり精通していようですね。9×9通常ナンプレでの初期ヒント数
(最初に数字が表示されているマスの数)で最小はどの程度なのか(究極のナンプレ問題)

18個,17個の具体例をご存知でしょうか。存在するそうですが未だ見た事がないのです。


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