迷路探索のシミュレーター

[rarikkuma]

迷路探索のシミュレーターを作成しているのですが、最短経路を導出しようとしたのですがうまくいかず詰まってしまいました。
自分なりに原因を考えてみたのですが、よくわかりませんでした。
nezuEX.cppの戻りルーチンが正しく機能していないんだと思われます。
自分の知識では正しく導出することが出来なかったので、質問させていただきました
作成環境は、Windows XP, Microsoft Visual C++ 2010 Expressです。
Ｃ++にて作成しています
どなたか助けていただけませんでしょうか。
http://firestorage.jp/download/28c64d1f ... e01a8c4133

コード:

[beatle]

是非フォーラムルールをお読みください。
あなたの質問は「回答者が困る質問例」に当てはまっております。

「うまくいかない」というのはほとんど言う価値がありません。もっと具体的に説明しましょう。
例えば、「変数aは・・・の時点で100になっていて欲しいが、0のままです」とか、
「関数fはループの中で呼び出されるはずなのですが呼び出されません」とか。

まずあなたが考えた迷路探索アルゴリズムを説明なさるといいかもしれません。

[rarikkuma]

抽象的な質問失礼しました。
うまくいかないというのは、迷路の探索アルゴリズムは完成したのですが、
最短経路の導出をする際に本当の経路と違う経路をたどってゴールしてしまいます
最短経路をわかりやすく表示しようともしましたが、その間違えた経路に出力されています。
経路を導出する際に、分岐点に達したときに優先度を左に設定しています。
その左の優先度が依存して、本来まっすぐ進むはずだった道を左に曲がってしまいます。

　経路の導出は、スタート位置である左下の角の区画を1として、評価値が定められている区画の上下左右が1度以上通過済みの区画であり、その方向に検知済みの壁が存在しない場合に、その方向の区画に+1したものを評価値として定め、それをゴールに評価値が定められるまで繰り返し、評価値のより高い方向を進むことで経路を導出することが出来る。
というものです。
評価値の計算は、正しく行われているのですが、左側が優先としているために分岐点で同値の評価値になると左以外が本当の経路だとしても左に進んでしまいます

コード:

[beatle]

評価値の計算は、正しく行われているのですが、左側が優先としているために分岐点で同値の評価値になると左以外が本当の経路だとしても左に進んでしまいます

これはアルゴリズムの欠陥ではないかと思うのですけれども、どうでしょうか。

[rarikkuma]

アルゴリズムに欠陥ですか…
アルゴリズムを考え直してみます。

質問ですが、評価値の計算はあってると思うので、求めた評価値を用いてゴールから逆算をして進むルートを固定してから走らせる、ということは可能なのでしょうか。

[beatle]

rarikkumaさんの仰っている「評価値」というのがまだよく分からないです。
迷路は2次元であり、格子状に区切ってあるということでよろしいですか？
その格子1つ1つに何らかの値が割り振られるんでしょうか。

　経路の導出は、スタート位置である左下の角の区画を1として、評価値が定められている区画の上下左右が1度以上通過済みの区画であり、その方向に検知済みの壁が存在しない場合に、その方向の区画に+1したものを評価値として定め、それをゴールに評価値が定められるまで繰り返し、評価値のより高い方向を進むことで経路を導出することが出来る。

この説明をもっと分かりやすくお願いできますか？無理やり1文に詰め込まなくていいですから。
例えば、「通過済み」とありますが、何が通過するのでしょうか。
それから、「区画に+1」という表現がありますが、なんでこんな単位が違うもの同士を加算できるのか不思議です。

分かったのは次の2点です。

• 自分の周りの格子を調べて一番評価値の高い格子へ移動する。
• もし、最も高い評価値を持つ格子が2つ以上ある場合、それらの格子の中で最左格子を選択する。

評価値というのは多分進むべき方向だとより高い値になるのですよね。
で、その値が等しいというのは、どちらに進んでも最短経路になるということじゃないのですか？
進むべき方向と進むべきでない方向の評価値が等しくなってしまうのだとすれば、
それは評価値を算出するアルゴリズムの欠陥だろうと僕は思ったわけです。

[rarikkuma]

返信が遅くなり、申し訳ありません。
リンクhttp://firestorage.jp/download/a8763de96916f79d785aa75c25345d716e0a8533
に参考画像をアップ（jpeg）したので、その画像を見てくださることを前提にお話します^^；

左下がスタート地点であり、迷路を探索したあとに経路の導出を行います。
経路の導出を行なう際、進める方向に値を１加えた数字を評価値として定めます。
画像の通る道に振ってある番号が評価値です。
探索後画像の１５のところで経路が分岐するのですが、ここでの進める評価値が上と右が同じ16であるので
左優先ですので誤った経路である上へ進んでしまいます。
さらに誤った経路44のところでも同じ現象が起こっています。


迷路探索後　の画像のゴールである真ん中の評価値が50であり、そのゴールからの評価値を低いほうに辿っていけば
評価値１であるスタート地点に戻れるはずなんで、まずゴールからスタート地点までの最短経路を導出し
それからスタート地点から出発しゴールから求めた経路を記憶させ、実行させることが出来ればきちんとした経路で進めるのではないか
と思ったのですがどうでしょうか。

[beatle]

返信が遅くなり、申し訳ありません。
リンクhttp://firestorage.jp/download/a8763de96916f79d785aa75c25345d716e0a8533
に参考画像をアップ（jpeg）したので、その画像を見てくださることを前提にお話します^^；

分かりやすい絵をありがとうございます。

迷路探索後　の画像のゴールである真ん中の評価値が50であり、そのゴールからの評価値を低いほうに辿っていけば
評価値１であるスタート地点に戻れるはずなんで、まずゴールからスタート地点までの最短経路を導出し
それからスタート地点から出発しゴールから求めた経路を記憶させ、実行させることが出来ればきちんとした経路で進めるのではないか
と思ったのですがどうでしょうか。

はい。可能だと思います。ゴールから低い方低い方へ移動しつつ、通ったマスのx,y座標を記憶し、それを逆順に再生すればスタートからゴールまで行けますね。

[rarikkuma]

早速の返信ありがとうございます

その方法でがんばってみることにします。
わかりにくい説明の中、理解していただきありがとうございます
やっと完成のめどがたちました
自分の不手際にも関わらず迅速、丁寧な対応ありがとうございました。
ここに相談して正解でした。
beatle さんに感謝いたします。