- ベストアンサー
迷路の解を見つけるアルゴリズム
toginoの回答
- togino
- ベストアンサー率75% (97/129)
基本的には、「解がない」ことを調べるには 「全探索」するしか方法がありません。 しかし、幾分か「枝狩り」することが出来ますので 少し高速にすることはできると思います。 （例）ス→ゴ に行く迷路があるとします。 ┏ス┳━━━┓ ┃↓┃←←←┃ ┃↓┗━━↑┃ ┃▲→★→●┃ ┃↓┃↓┃↓┃ ┗━┻━┻ゴ┛ まず、最短経路は ・▲で右に行く ・★で右に行く ・●で下に行く ですが, 全探索すると、 まず▲で下か右に枝分かれします。 ここで右を選んだ場合、 次に★で下か右に枝分かれしますが、 ここで下を選んだ場合、 『壁にぶつかります』 そうすると、「ス→▲→★→壁」によって 左下の区画は絶対にゴールにたどり着けない ことが判明します。 つまり、最初の▲で下に行く探索は無意味です。 この枝狩りを効率よくプログラムに組み込んで 見てください。 # RedHat のスクリーンセーバーにこの探索の # 様子を分かりやすく表示してたものがあって # 見てて楽しかったのですが・・・
関連するQ&A
- 迷路をたくさんしたい！！
幼稚園の子どもが迷路をやりたがるのですが、 市販の迷路ブックはあっという間に書き終えちゃうのに１冊１０００円近くしますし、 比較的安いものは単純すぎる迷路が多い気がします。 子どもに少しやり応えのあるレベルで、たくさんの迷路が印刷できるサイトはありませんでしょうか。 よろしくお願いいたします。
- ベストアンサー
- その他(暮らし・生活お役立ち)
- 最短距離でいく経路の場合の数を教えてください。
最短距離でいく経路の場合の数を教えてください。 図のような道路で、点Pから点Qまで最短距離でいく経路のうち、次の経路は何通りあるか。 問1.すべての経路 問2.Rを通る経路 答案1. 横道路が4本、縦道路が6本 最短距離でいくから階段状に行くのはいいけど、矩形上にジグザグにいくのはダメですよね。 和の法則＝「同時に起こらない場合｣＝排反事象 ある試行において、一方が起これば 他方は決して起こらないときの、それぞれの事象。 今回全くわかりません。 横道路4本のうち4本とも行くことが出来るので4C4 ? 縦道路6本のうち6本とも行くことが出来るので6C6 ? たとえば 横1縦6 横1縦5横4 縦1横4 縦1横3縦6 規則は必ず横1か縦1を通る。 最後は横4か縦6を通る。 わかりません。 答案2. 考え方から全くわかりません。
- ベストアンサー
- 数学・算数
- 迷路生成
たびたび質問して申し訳ありません。 迷路生成を穴掘り法を使って作ろうと思ったのですが うまくいきません。 ROAD=0,WALL=1 /*迷路の構造体*/ typedef struct Mazestruct{ /*迷路のサイズ（size[0]:横のサイズsize[1]:縦のサイズ）*/ int size[2]; /*スタートの座標(st[0]:横座標st[1]:縦座標(一番左上を(0,0))*/ int st[2]; /*ゴールの座標(goal[0]:横座標goal[1]:縦座標*/ int goal[2]; /*壁と通路のデータ*/ int maze_d[wid_max][len_max]; }Mazestruct; void wall_make(int x,int y,Mazestruct *maze) { int x1,y1,px,py; int gx[2]={1,-1},gy[2]={1,-1}; while(maze->maze_d[x][y]==ROAD){ while(1){ x1=x; y1=y; while(1){ px=rand()%2; py=rand()%2; if(maze->maze_d[x1+gx[px]*2][y1+gy[py]*2]==WALL){ maze->maze_d[x1+gx[px]][y1+gy[py]]=maze->maze_d[x1+gx[px]*2][y1+gy[py]*2]=ROAD; x1=x1+gx[px]*2; y1=y1+gy[py]*2; } else if(maze->maze_d[x1+1][y1]==ROAD&& maze->maze_d[x1-1][y1]==ROAD&& maze->maze_d[x1][y1+1]==ROAD&& maze->maze_d[x1][y1-1]==ROAD){ goto quit; } } } } quit:; } (px,py)を回転させるというところと 四方向をチェックするところをどのようにしたらよいか分りません。 回転させる方法が分らないので乱数をもう一度得るようにして四方向のチェックに関しては 四方向が道ならループをやめるようにしました。
- ベストアンサー
- C・C++・C#
- また降参。富士通パソコンの「ジャンケン迷路」
少し前に「富士通パソコン」の 「ジャンケン迷路」について答えを求めた者ですが またしても降参です。 「ステージ１７」まで進みましたが 「ステージ１７」は完敗です。降参です。 「ステージ１７」の やり方の答え、クリア方法を伝授してください。 また、この「ジャンケン迷路」は ステージいくつまで用意されているのでしょうか？ １７まで来たけれど、この先、いくつまで 頑張れば終了なのでしょうか？ （人に答えを聞いておいて頑張るもないけど・・・） 誰か助けてください。 よろしくお願いします。
- ベストアンサー
- その他(ボードゲーム)
- 医師のいう「迷路」とは。。
３年あまりうつ病の治療をうけています。最近、その主治医のすすめで分析的療法を始めて週２回５０分の時間をとって治療しています。 先日のことです。 主治医のある様子に驚いたという話をしたところ、医師はそのことについて深く掘り下げて聞こうとしてきました。そして「私じゃなくても、同じように心が揺れるほど驚きましたか？」と聞かれました。「自分と同じくらいの年齢や同じ性別（男性）の精神科医であれば同じように思ったのでは」というのが医師の推察でした。 でも私は「他の医師でも同じように必ずしもそうなったとは思わない。先生だからだと思う。」と答えました。私の軽い陽性転移的な感情がそう思わせたからだと思ったので、そう答えました。 これは私にとってはかなり勇気のいる答えでした。 医師はしばらく考えたあと、「誰にでも起こるわけでもないんだったらこれ以上聞くのは意味がないかな、、、」といい、続けて「ふたりで迷路に入ってしまっても大変なだけだから」といいました。 そしてそれ以降そのことは話題に出ません。 私は常々自分が迷路に入ったようだ、出口がないと言い続けてきましたが、 この医師のいう「２人で迷路に入ってしまう」という意味がわかりませんでした。 ただ、「意味がないかな」といわれたことと、「先生だからかも」といったことを避けられたようで、なにか気持ちが悪いものが残っています。 もし医師が私の言葉を「陽性転移」だと思ったのだとしたら、それを避けられたのは少しショックでもあります。私は治療に役立つのであればと勇気を出して話したのですが。。。 分析的療法の中では意味のないこと、言ったら笑われるようなことなどないのだから、思いついたことを話してください、と言われていたからよけいに違和感が残っています。 どうしてこのような言葉が返ってきてしまったのだと思われますか？ アドバイスなどあればお聞かせいただけますか？ 念のために追加させていただきますが、医師として好意や尊敬はありますが、その医師に恋愛感情などはありません。
- ベストアンサー
- 心の病気・メンタルヘルス
- ２次方程式の解を求めたいのですが、ややこしくて分かりません。
２次方程式の解を求めたいのですが、ややこしくて分かりません。 解き方教えてください。 (4-4x+x^2)(6*10^-6)=x^2(15*10^-6) の解を求めたいです。 解は、0.775となるらしいのですが、答えしか書いておらず 解き方がわかりません。 お願いします。 効率のいい計算方法を教えてください。
- ベストアンサー
- 数学・算数
- 解の存在範囲について
自分は解の存在範囲についての問題が出ると D(b~2-4ac) x軸 y切片 をいじるとできる。と暗記でやってるんですが これはDで形、x軸で横の位置、y切片で縦の位置を決めるということなんですか？ あと、たまに±の解を持つときy切片だけで求められる問題については y切片の位置さえ求めれば後が勝手に決まるということなんですか？ 混乱してます。回答お願いします。
- ベストアンサー
- 数学・算数
- 3次方程式の一つの解をθとし他の解をθの整式で表す
次の方程式の１つの解をθとおくとき，他の解をθの最低次の整式として表せ． (1) x^3-3x+1=0 (答) -θ^2-θ+2, θ^2-2 (2) x^3+x^2-2x-1=0 (答) -θ^2-θ+1, θ^2-2 (3) x^3+x^2-4x+1=0 (答)-θ^2-2θ+2, θ^2+θ-3 (4) x^3+x^2-6x-7=0 (答)-θ^2+4, θ^2-θ-5 いったいどうやればよいのでしょうか？ 3次方程式に限らず、n次方程式の一般形において、同様の問題の公式みたいなものはあるのでしょうか？
- 締切済み
- 数学・算数
- 二次方程式の解の存在範囲を解の公式で解こうとしているのですが解けません
二次方程式の解の存在範囲を解の公式で解こうとしているのですが解けませんどうしてでしょうか？ 問題 Ｘについての二次方程式Ｘ＾２＋２（Ａ－１）Ｘ＋Ａ＾２－３Ａ－１＝０が次のような解をもつための定数Ａの範囲を求めよ （１）2つの解（重解を含む）がともに1より大きい を解の公式の小さいほうの解√の前にマイナスが付いているほうが1より大きいと考えて式をたてて解こうとしたのですが、一応答えは出たのですが全く違っていました。回答を見て解き方はりかいできたのですが、なぜ自分の解の公式で解いた方法では答えが出ないのかが分りません教えてください。
- 締切済み
- 数学・算数
お礼
再起のことを自分自身がよく分っていないようで なかなかうまくいきません。 回答有難うございました。