経路探索について

質問

基本的には迷路の探索のようなものなのですが、広い空間があるのです。その空間をすべて通るかどうかを調べて表示したいのです。

普通の迷路だったら左手法とかでいけるのだと思うのですが、同じようにやってもうまくいかなくて。。。通ったとこを壁にしていって、行けなくなればバックトラックするようにしようとしてもうまくいかなかったんです。何かヒントいただければと思いました。よろしくお願いします。

回答No.5

noocyte

ちょっと考えてみました．この問題は，グラフ理論でよく知られている
「ハミルトン路問題」を，若干弱めたものになっていると思います．

・ロボットが取り得る位置を，無向グラフの節点とする．
・ロボットが位置Ａから，その隣の位置Ｂに移動可能 (壁がない) ならば，
　節点Ａと節点Ｂを辺で結ぶ．

「一筆書き」は「すべての辺を１回ずつ通る」という問題ですが，
「ハミルトン路問題」は「すべての節点を１回ずつ通る」という問題です．
だから今回の問題で「最大２回まで」という条件ではなく，「必ず１回」
であればハミルトン路問題になります．

ハミルトン路問題は，効率的なアルゴリズムが存在しない (NP完全) であることが
知られています．したがって制約のない一般のハミルトン路問題で，Ｎがある程度
大きい場合には実用的な時間内でプログラムが終了しなくなります．

今回の問題の場合は，１つの節点に接続する辺が最大４本しかないことを利用すれば，
効率的なプログラムが書けるかもしれません．あと，最適化をどこまで妥協するかも
ポイントでしょうね．

↓の26～27ページを参照
アルゴリズム設計 (9) グラフアルゴリズム (続き)
http://www.logos.t.u-tokyo.ac.jp/www/home/chik/algorithm-design/09%20Graph%20Algorithms.pdf

ハミルトン閉路問題をなぜ始めたか (ほか)
http://www.geocities.com/babalabo/HamiltonJ/DraftIndexJ.html

「+ハミルトン +グラフ +アルゴリズム」で Google 検索
http://www.google.co.jp/search?sourceid=navclient-ff&ie=UTF-8&rls=GGGL,GGGL:2006-34,GGGL:ja&q=%2B%E3%83%8F%E3%83%9F%E3%83%AB%E3%83%88%E3%83%B3+%2B%E3%82%B0%E3%83%A9%E3%83%95+%2B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

回答No.4

noocyte

> できればアドバイスお願いできないでしょうか？

面白そうなので考えてみるつもりです．(笑)
回答には何日か時間をいただくかもしれませんが…．

Ｎ×Ｎというサイズは当然，事前に与えられていると思いますが，壁の位置はどうでしょうか？
事前に (「掃除」＝移動を始める前に) 知らされているんでしょうか？
それとも移動しながら自分で調べないといけないんでしょうか？
市販のお掃除ロボットのようなものであれば，知らされていないわけですが．

どちらの場合かで，アルゴリズムは全然異なります．
事前に壁の位置がわかっていれば，移動を始める前にコンピュータ内で
シミュレーションして最適経路を求め，それに従って移動することができます．
そうでなければ，移動しながら壁の位置を見つけなければならず，
最適にはなりません (２回通らなければならないマスが増えてしまうかもしれません)．

それから，移動終了後の位置に関してリクエストはあるんでしょうか？
例えば，スタート位置に戻れ，とか．

補足

ありがとうございます。

壁の位置は事前に与えられています。移動終了後の位置に指定はありません。ただすべての空間をとおり、その通った順を表示したいのです。ちなみにC言語でやっています。

回答No.3

noocyte

> お掃除をしてくれるロボットといったとことでしょうか。
> そのためにすべての空間をとおる必要があるのです。

> すべての空間を一回しかとおれない場合、または最大二回まで
> 通れる場合ですべてのマスを通れるかどうか調べたいのです。

ふーむ，「任意図形の塗りつぶし」と「一筆書き」を一緒にしたような
アルゴリズムになりそうですね．「一筆書きによる塗りつぶし」かな？

補足

そんなような感じです。一筆書きでできない条件もよくわからないんです。できればアドバイスお願いできないでしょうか？

回答No.2

Interest

No.1の方が仰るところの、マイクロマウス作ってます。
マイクロマウスで使われる迷路探索アルゴリズムの基本は、

http://www.informatics.tuad.ac.jp/tenji/tenji03/shiragami-lab/199970120/3.doc

の解説が秀逸。

マイクロマウスでないのでしたら、

> 広い空間があるのです。

空間はどのように定義しますか？
また、空間の広さの最大はどれくらい？
スタート地点とゴール地点（？）の与え方は？

> その空間をすべて通るかどうかを調べて表示したいのです。

全ての経路を網羅したかどうか確認したいということですか？
スタート地点からゴール地点までの最短経路が求まってしまうと、他の経路は通るだけ無駄ですよね。例えば袋小路とかは、行く意味が無い。

最短経路計画の定番は、数学的にはダイクストラ法とか、A*アルゴリズムとか。
http://research.nii.ac.jp/~uno/MP2/MP2_8shortestpath.ppt
これらは数学的に経路が最短であることを証明できます。

補足

自分のコトバ足らずだったようですいません…マイクロマウスとはまた違うんです。。。迷路という言葉を使った自分が悪いですね。あえて言うならば、お掃除をしてくれるロボットといったとことでしょうか。そのためにすべての空間をとおる必要があるのです。

すべての空間および壁は、二次元配列でＮ×Ｎますのフロアとして定義しています。その中に壁を設定します。つまりスタートとゴールがあるというよりは、すべての空間を一回しかとおれない場合、または最大二回まで通れる場合ですべてのマスを通れるかどうか調べたいのです。ただスタートは一番左上のマスからです。

回答No.1

noocyte

マイクロマウスの話でしょうか？

> 迷路の探索のようなものなのですが、

道は一方通行 (有向グラフ) でしょうか，双方向 (無向グラフ) でしょうか？
普通の迷路探索であれば後者だと思いますが．

> その空間をすべて通るかどうかを調べて表示したいのです。

意味がよくわからないのですが，これは出発点とゴールが指定されていて，
それを結ぶ (１つの) 経路を見つけたいということでしょうか？

> 普通の迷路だったら左手法とかでいけるのだと思うのですが、
> 同じようにやってもうまくいかなくて。。。

合流点またはループがあるということですね？
だとしたら左手法 (右手法) は無限ループします．

ご質問の問題は，典型的な (無向または有向) グラフの深さ優先探索
(縦型探索ともいう) で解決できますが，マイクロマウスであれば色々な
探索法があるようですので，とりあえず↓

迷路を脱出する経路探索プログラムをＣ言語で作成するには？
http://oshiete1.goo.ne.jp/kotaeru.php3?qid=1553632

「+"左手法" +"迷路"」で Google 検索 (関連する探索法もあります．)
http://www.google.co.jp/search?q=%2B%22%E5%B7%A6%E6%89%8B%E6%B3%95%22+%2B%22%E8%BF%B7%E8%B7%AF%22&hl=ja&lr=&rls=GGGL,GGGL:2006-34,GGGL:ja&start=10&sa=N